Любое число больше 7 можно разложить на сумму троек и пятерок

Программирование - Практика программирования

Наткнулся в интернете на школьную задачу: "Докажите, что любое число больше 7 можно представить в качестве суммы чисел 3 и 5". Представляю решение на 1С. (есть рекурсия, пример работы с событием ИзменениеТекстаРедактирования).

Само доказательство:

Проверим что числа от 8 до 19 действительно можно представить в виде сумм 3 и 5: x = 3n + 5к

    8=(3*1+5*1)
    9 =(3*3+5*0)   
    10=(3*0+5*2)
    11=(3*2+5*1)
    12=(3*4+5*0)
    13=(3*1+5*2)
    14=(3*3+5*1)
    15=(3*5+5*0)
    16=(3*2+5*2)
    17=(3*4+5*1)
    18=(3*1+5*3)
    19=(3*3+5*2)

Любое число больше 19 также можно представить с помощью цифр 8,9,10...19

20 = 10+10
21 = 11+10
22 = 11+11
....
29 = 19+10

Утверждение становится очевидным, если вспомнить формулу представления десятичных чисел: х = εrsr + εr -1sr -1 + … + ε1s1 + ε 0s0 + ε1s1 + ε -1s -1+ ε - 2s -2 + …
Для дальнейшего представления натуральных положительных чисел > 20 хватит и этого набора:

    10=(3*0+5*2)
    11=(3*2+5*1)
    12=(3*4+5*0)
    13=(3*1+5*2)
    14=(3*3+5*1)
    15=(3*5+5*0)
    16=(3*2+5*2)
    17=(3*4+5*1)
    18=(3*1+5*3)
    19=(3*3+5*2)

т.к. включает он в себя весь необходимый набор цифр 10Х(0,1,2,3,4,5,6,7,8,9).

P.S.
Доказательство, строго говоря, математически не корректно, но зато понятно.
С помощью матиндукции было бы правильнее, но... если кому надо, вспомню, напишу.

 
&НаКлиенте
Перем СоответсвиеПервых12,СоответсвиеПервых12плюс;

&НаКлиенте
Процедура Разложить(ЧислоДляРазложения)
    
    Если ЧислоДляРазложения<8 Тогда
        Объект.Ряд = "Меньше 8!";
        Объект.РядРекурсирвно = "Меньше 8!";
        Объект.РядБезУмножения = "Меньше 8!";
        Возврат;
    КонецЕсли;    
    
    Если ЧислоДляРазложения<20 Тогда        
        Объект.Ряд = СоответсвиеПервых12[ЧислоДляРазложения];        
    Иначе
        Остаток = ЧислоДляРазложения%10;
        Если Остаток = 0 Тогда
            Объект.Ряд = "" + ЧислоДляРазложения/10 +"*"+ СоответсвиеПервых12[10]
        Иначе
            Кратно10 = ЧислоДляРазложения - (10+Остаток);
            Объект.Ряд = "" + Кратно10/10 + "*" + СоответсвиеПервых12[10] + " + " + СоответсвиеПервых12[10+Остаток];            
        КонецЕсли;            
    КонецЕсли;
    Объект.РядРекурсирвно = РазложитьРекурсивно(ЧислоДляРазложения);
    Объект.РядБезУмножения = РазложитьБезУмножения(ЧислоДляРазложения);
КонецПроцедуры

&НаКлиенте
Функция РазложитьБезУмножения(ЧислоДляРазложения)    
    Если     ЧислоДляРазложения<20 Тогда        
        Возврат СоответсвиеПервых12плюс[ЧислоДляРазложения];                   
    Иначе                 
        Ряд="";
        Остаток = ЧислоДляРазложения%10;
        ЧислоДесяток = ?(Остаток=0,ЧислоДляРазложения/10,(ЧислоДляРазложения - (10+Остаток))/10);        
        Если ЧислоДляРазложения>1000 Тогда
            Ряд = ""+Числодесяток+"*("+СоответсвиеПервых12плюс[10]+")";
            Возврат ?(Остаток = 0, Ряд, Ряд + "+" + СоответсвиеПервых12плюс[10+Остаток])
        Иначе        
            Для сч = 1 По ЧислоДесяток Цикл
                Ряд = Ряд + СоответсвиеПервых12плюс[10] + "+";                
            КонецЦикла;                
            Возврат ?(Остаток = 0, Лев(Ряд,СтрДлина(Ряд)-1), Ряд + СоответсвиеПервых12плюс[10+Остаток]);
        КонецЕсли;    
    КонецЕсли;    
КонецФункции

&НаКлиенте
Функция РазложитьРекурсивно(ЧислоДляРазложения)
    Если ЧислоДляРазложения<8 Тогда
        Возврат ЧислоДляРазложения;
    ИначеЕсли     ЧислоДляРазложения<20 Тогда
        Возврат ""+СоответсвиеПервых12[ЧислоДляРазложения];
    Иначе
        Остаток = ЧислоДляРазложения%10;
        Если Остаток = 0 Тогда
            Возврат  "" + РазложитьРекурсивно(ЧислоДляРазложения/10) +"*" + СоответсвиеПервых12[10]
        Иначе
            Кратно10 = ЧислоДляРазложения - (10+Остаток);
            Возврат "(" + РазложитьРекурсивно(Кратно10/10) + "*" + СоответсвиеПервых12[10] + " + " + СоответсвиеПервых12[10+Остаток]+")";            
        КонецЕсли;            
    КонецЕсли;    
    
КонецФункции

&НаКлиенте
Процедура ПриОткрытии(Отказ)
    СоответсвиеПервых12 = Новый Соответствие;
    СоответсвиеПервых12.Вставить(8 ,"(3*1+5*1)");
    СоответсвиеПервых12.Вставить(9 ,"(3*3+5*0)");    
    СоответсвиеПервых12.Вставить(10,"(3*0+5*2)");
    СоответсвиеПервых12.Вставить(11,"(3*2+5*1)");
    СоответсвиеПервых12.Вставить(12,"(3*4+5*0)");
    СоответсвиеПервых12.Вставить(13,"(3*1+5*2)");
    СоответсвиеПервых12.Вставить(14,"(3*3+5*1)");
    СоответсвиеПервых12.Вставить(15,"(3*5+5*0)");
    СоответсвиеПервых12.Вставить(16,"(3*2+5*2)");
    СоответсвиеПервых12.Вставить(17,"(3*4+5*1)");
    СоответсвиеПервых12.Вставить(18,"(3*1+5*3)");
    СоответсвиеПервых12.Вставить(19,"(3*3+5*2)");
    
    СоответсвиеПервых12плюс = Новый Соответствие;
    СоответсвиеПервых12плюс.Вставить(8 ,"3+5");
    СоответсвиеПервых12плюс.Вставить(9 ,"3+3+3");    
    СоответсвиеПервых12плюс.Вставить(10,"5+5");
    СоответсвиеПервых12плюс.Вставить(11,"3+3+5");
    СоответсвиеПервых12плюс.Вставить(12,"3+3+3+3");
    СоответсвиеПервых12плюс.Вставить(13,"3+5+5");
    СоответсвиеПервых12плюс.Вставить(14,"3+3+3+5");
    СоответсвиеПервых12плюс.Вставить(15,"5+5+5");
    СоответсвиеПервых12плюс.Вставить(16,"3+3+5+5");
    СоответсвиеПервых12плюс.Вставить(17,"3+3+3+3+5");
    СоответсвиеПервых12плюс.Вставить(18,"3+5+5+5");
    СоответсвиеПервых12плюс.Вставить(19,"3+3+3+5+5");
КонецПроцедуры

&НаКлиенте
Процедура ЧислоДляРазложенияИзменениеТекстаРедактирования(Элемент, Текст, СтандартнаяОбработка)
    СтандартнаяОбработка = Ложь;
    Разложить(Число(Текст));
КонецПроцедуры

 

 

Скачать файлы

Наименование Файл Версия Размер
Любое число больше 7 можно разложить на сумму троек и пятерок:
.epf 7,11Kb
06.07.18
0
.epf 7,11Kb Скачать

См. также

Комментарии
Сортировка: Древо
1. mp40 4 06.07.18 17:15 Сейчас в теме
Интересная задача. ) Не знаю про матиндукцию, но в голове все решается проще. Чтобы увеличить любое число состоящее из 3 и 5 на единицу. Нужно заменить одну 5 двумя 3, или три 3 заменить двумя 5. С тройками и пятерками в суммах недостатка нет. Выполнение первой и второй операции по очереди в итоге увеличивает количество цифр в сумме. И даже баланс их сохраниться. )
CyberCerber; manuel; +2 Ответить
2. cool.vlad4 43 07.07.18 01:11 Сейчас в теме
с помощью мат индукции элементарно
допускаем, что при n : 3*a+5*b
надо доказать для n+1: 3*a+5*b + 1 == 3*a+6 + 5*(b-1) = 3*(a+2) + 5*(b-1)
почему число больше 7, также выше понятно
(для корректности надо еще показать что при первом шаге индукции также верно, но оно понятно)
3. bulpi 129 07.07.18 14:38 Сейчас в теме
(2)
Еще нужно рассмотреть случай b=0
4. cool.vlad4 43 07.07.18 15:07 Сейчас в теме
(3) я вроде по русски это написал
для корректности надо еще показать что при первом шаге индукции также верно, но оно понятно)

не? (и не b=0 , а именно первый шаг индукции, он не при b=0, первый шаг это число 8 = 3*1+ 5*1)
5. Sure 140 10.07.18 14:09 Сейчас в теме
Да что тут решать?
Число Х делим с остатком на 3, получаем А как частное и В в остатке : Х=3А+В: Х>7 (по условию задачи), В<3 (остаток).
В=0, 1, 2
Случай В=0 - самый простой :-) Число Х представляется как сумма троек (и троек будет А штук);
В=1 : Х=3А+1=5+5+3(А-3) ;
В=2 : Х=3А+2=5+3(А-1)
ВСЁ!
LordKim; Skin123; +2 Ответить
6. Eskimos 24 10.07.18 16:21 Сейчас в теме
(5)Действительно!
Sure, красиво.
Оставьте свое сообщение