B13 Разбор решения школьника-2
1. Условие и решение
2. Комментарий
1. В решении, в отличие от демо-версии, не написана рекуррентная формула. Само по себе это не страшно, формулу можно не писать. Но в этом случае нужно описать ее словами - чтобы было понятно, какое отношение таблица имеет к делу. Например, в конце п 3) решения можно добавить: "Для остальных чисел количество программ, которые ведут к этому числу, равно сумме количеств программ для чисел, из которых это число можно получить (они стоят во второй строке)."
2. В работе есть более серьезный недочет - не объяснено, почему мы не рассматриваем числа, которые больше 13.
Это возможно потому, что все команды увеличивают исходное число. Например, если бы среди команд была бы команда вычитания, то приведенное решение было бы неверным.
Мотивация, которая приведена в начале решения - неверная. Что означает фраза "При выполнении команд 1), 2) или 3) получаем числа 1, 2, 3, ..., 13"? При выполнении наших команд можно получать и числа, которые больше 13.
Правильное решение может, например, начинаться так.
"Все команды исполнителя увеличивают исходное число. Поэтому программы, при выполнении которых получаются числа больше, чем 13 можно не рассматривать. Для каждого из чисел 1, 2, ..., 13 подсчитаем количество программ, с помощью которых можно получить это число. " И далее по тексту.
2 комментария
здравствуйте, а какая здесь будет рекуррентная формула
Пусть R(n) - количество программ, результатом работы которых будет число n. Тогда:
если n не делится нм на 2, ни на 3, то R(n) = R(n-1)
если n делится на 2, но не делится на 3, то R(n) = R(n-1) + R(n/2)
если n делится на 3, но не делится на 2, то R(n) = R(n-1) + R(n/3)
если n делится и на 2, и на 3 (т.е. n делится на 6), то R(n) = R(n-1) + R(n/2) + R(n/3)
Удачи!