Скількома способами хлопчик може піднятися сходами на 10 сходинку, якщо він за один раз може підніматися на наступну сходинку або переступати через одну сходинку?. Сформулюйте алгоритм визначення кількості способів сходження на 5 сходинку
Ответы
Хлопчик може піднятися по сходах на 10-й щабель двома способами: він може зробити одну сходинку за раз, або він може пропустити сходинку і зробити дві сходинки одночасно. Це можна представити у вигляді рекурсивної формули:
шляхи (n) = шляхи (n-1) + шляхи (n-2)
де way(n) представляє кількість способів піднятися сходами до n-ої сходинки.
Щоб визначити кількість способів підйому на 5-ту сходинку, ми можемо використати цю формулу та почати з базових випадків шляхів (1) і шляхів (2), які обидва дорівнюють 1:
шляхи(5) = шляхи(4) + шляхи(3)
= (шляхи(3) + шляхи(2)) + (шляхи(2) + шляхи(1))
= (шляхи(2) + шляхи(1)) + (шляхи(1) + 1)
= 2 + 2 + 1
= 5
Таким чином, є 5 способів піднятися на 5 сходинку за допомогою цього методу.
Алгоритм для визначення кількості способів піднятися на n-ту сходинку за допомогою цього методу може бути таким:
Визначте функцію ways(n), яка повертає кількість шляхів підйому на n-ту сходинку.
Якщо n менше 1, повертається 0.
Якщо n дорівнює 1 або 2, поверніть 1.
Повертає суму шляхів (n-1) і шляхів (n-2).
Цей алгоритм використовує рекурсивний підхід до вирішення проблеми, оскільки функція викликає саму себе з меншими значеннями n, доки не досягне одного з базових випадків.