Подсчет шагов
При подъеме по лестнице некоторые люди предпочитают подниматься по двум ступенькам за раз, по крайней мере, в некоторых случаях. Это приводит к общему вопросу: сколькими разными способами можно подняться по лестнице таким образом?
CHALLENGE
Сколько существует различных способов подняться на 10 ступенек, используя комбинацию одинарных и двойных ступенек (это могут быть только одинарные ступени, только двойные ступени или их сочетание)? А как насчет 20 ступенек?
РАЗВЕДКА
Вы видите какую-нибудь закономерность? Можете ли вы найти способ упростить подсчет всех возможных вариантов?
Заметки
ВЫЗОВ И ИССЛЕДОВАНИЕ
Это еще одно знакомство с числами Фибоначчи. Первые несколько подсчетов того, сколькими способами это можно сделать, следующие: 1, 2, 3, 5 и 8. После решения головоломки с родословной пчел и просмотра первых нескольких чисел в этой головоломке, ваши ученики должны заподозрить неладное.
Сложность заключается в том, чтобы понять, где здесь вступает в действие правило Фибоначчи. Рассмотрим в качестве примера подъем на десять ступеней. Способы выполнения десяти шагов можно разделить на две категории. В первую входят все способы подъема на девять ступеней с последующим одним шагом для достижения десятой. Во вторую — все способы подъема на восемь ступеней с последующим двойным шагом для достижения десятой. Каждая возможность учитывается таким образом, и ничто не учитывается дважды.
В общем случае, количество способов подняться на n ступеней будет равно количеству способов подняться на (n – 1) ступеней плюс количество способов подняться на (n – 2) ступеней. Это и есть правило Фибоначчи.