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

30.01.19

Разработка - Математика и алгоритмы

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

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

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

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

Проверим что числа от 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 в виде суммы 3 и 5

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1757    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4431    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7469    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7856    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4449    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8846    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7814    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. mp40 10 06.07.18 17:15 Сейчас в теме
Интересная задача. ) Не знаю про матиндукцию, но в голове все решается проще. Чтобы увеличить любое число состоящее из 3 и 5 на единицу. Нужно заменить одну 5 двумя 3, или три 3 заменить двумя 5. С тройками и пятерками в суммах недостатка нет. Выполнение первой и второй операции по очереди в итоге увеличивает количество цифр в сумме. И даже баланс их сохраниться. )
CyberCerber; manuel; +2 Ответить
2. cool.vlad4 2 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 215 07.07.18 14:38 Сейчас в теме
(2)
Еще нужно рассмотреть случай b=0
4. cool.vlad4 2 07.07.18 15:07 Сейчас в теме
(3) я вроде по русски это написал
для корректности надо еще показать что при первом шаге индукции также верно, но оно понятно)

не? (и не b=0 , а именно первый шаг индукции, он не при b=0, первый шаг это число 8 = 3*1+ 5*1)
5. Sure 163 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 26 10.07.18 16:21 Сейчас в теме
(5)Действительно!
Sure, красиво.
Оставьте свое сообщение