Я пытаюсь решить этот вопрос ниже, который сначала требует найти математическую формулу, а затем написать код в DrRacket (диалект схемы на Лиспе):
Сидит лягушка с неограниченной силой прыжка. на первом пэде (пэд № 0) из N пэдов подряд (N всегда четное). Лягушка хочет достичь последней (N-й) площадки. Лягушка может прыгать на любое четное количество пэдов, включая N: возможно, что она сделает это за 1 прыжок (путем прыжка N пэдов), за N / 2 прыжка (путем прыжка 2 пэдов за раз) или в любой другой комбинации даже прыгает. Например, если бы N было 4, он мог бы прыгнуть за один прыжок: с 0-го на 4-й или за 2 прыжка (с 0-го на 2-й, а затем с 2-го на 4-й). Общее количество способов перепрыгнуть с 0-го на 4-е место составляет 2 способа.
- Какая математическая формула для определения общего числа способов, которым лягушка может достичь N-го участка?
- Используя Схему, напишите процедуру, которая, учитывая количество пэдов N, возвращает общее количество путей, которыми лягушка может достичь N-го пэда, ИСПОЛЬЗУЯ ТОЛЬКО РЕКУРСИВНЫЕ ВЫЗОВЫ. Если число колодок N не является четным, лягушка не может прыгнуть, и процедура возвращает «x».
Я получил решенный вопрос, который немного отличается, и здесь решение для этого ниже, но я не уверен, что математическая формула для вопроса выше, хотя, поэтому был бы признателен за вашу помощь.
Лягушка с неограниченной силой прыжка сидит на первом пэде (пэд № 1) из N пэдов подряд. Лягушка хочет достичь последней (N-й) площадки. Лягушка может прыгать на любое количество пэдов, включая N: возможно, она сделает это за 1 прыжок (путем прыжка N пэдов), за N прыжков (путем прыжка 1 пэда за раз) или в любой другой комбинации. Например, если бы N было 4, он мог прыгнуть за один прыжок; С 1 по 4 или в 2 прыжка; первый из длины 1 и затем 2 (с 1-го по 2-й, а затем со 2-го по 4-й) или первый из длины 2 и затем 1 (с 1-го по 3-й и затем с 3-го по 4-й) или в 3 прыжка (с 1-го до 2 и со 2 по 3 и с 3 по 4). Общее количество способов прыжка с 1-го на 4-й пэд составляет 4 способа. Напишите процедуру, которая при заданном количестве площадок N возвращает общее количество путей, которыми лягушка может достичь N-й площадки.
Решение: