5
1

Найдите количество способов преобразовать число $%1$% в $%20$%, используя только две операции: $%+1$% (плюс один) и $%\times2$% (умножить на два)

задан 25 Фев '14 21:40

10|600 символов нужно символов осталось
2

Пусть $%f(n)$% означает количество способов преобразовать описанным способом 1 в $%n$%. Тогда $%f(1)=1$%, и далее для каждого нечётного числа $%f(2k+1)=2k$% (нечётное число можно получить только прибавлением 1), и $%f(2k)=f(2k-1)+f(k)$% (чётное число можно получить прибавлением 1 из предыдущего, или удвоением числа вдвое меньшего).

Из этих рекуррентных формул следует правило последовательного заполнения клеток массива. Получается $%f(1)=1$%, $%f(2)=f(3)=2$%, $%f(4)=f(5)=4$%, $%f(6)=f(7)=6$%, $%f(8)=f(9)=10$%, $%f(10)=f(11)=14$%, $%f(12)=f(13)=20$%, $%f(14)=f(15)=26$%, $%f(16)=f(17)=36$%, $%f(18)=f(19)=46$%, $%f(20)=f(19)+f(10)=46+14=60$%.

ссылка

отвечен 26 Фев '14 2:01

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,937

задан
25 Фев '14 21:40

показан
468 раз

обновлен
26 Фев '14 2:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru