Ещё одна интересная задача. Поначалу она может показаться чисто математической, но суть решения кроется совсем не в этом :)
Собственно, задание:
Любое натуральное число можно представить в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2. Суммы, различающиеся лишь порядком слагаемых, считаются одинаковыми. Например, для числа 7 таких представлений 6 (4+2+1, 4+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1).
Требуется написать программу, которая найдет количество способов такого представления заданного числа N.
Очень хороший способ решения задач на динамическое программирование - порисовать! И если в вас умирает художник, это ваш шанс. Порисовать можно деревья, можно стрелочки, можно обойтись чиселками. Я попробовал все варианты, и вам советую :)
Возьмем для примера числа 5 и 6. Можно заметить, что у каждого следующего числа будут те же разложения, что у предыдущего, но с приписанной единицей. Довольно очевидно.
Но у шестёрки существует ещё два разложения, а именно: 6=2+2+2=4+2
Откуда же нам их взять?
А если вот так?)
Это нам уже кое-что напоминает :)
Проверив нашу теорию на паре примеров, увидим, что кол-во разложений числа N, если N - четное, это сумма разложений числа N-1 и числа N/2
А вот и код:
Вывод: не бойтесь рисовать, ибо это помогает структурировать мысли и увидеть что-то новое. Но берегите бумагу - деревья не бесконечные!