Эрудиция и смекалка

[svsexmon]

... Рекурсия на пальцах...
Когда мы дойдём до 0-вой клеточки ... - то в 0-вой клеточке мы получим количество вариантов прыжков.

Короче... - Допрыгались!!!

И откуда такие Вумные берутся!??

[Caxaroza]

mtit, тоесть читаем книгу с конца на начало?

[EdisonS]

Спор я так полагаю, не совсем о чём, потому как нет определения системы измерения, а по сему, как мне кажется - вариантов вообще может быть много. Чутка попозже найду с чего сыр-бор начался. Извините за редкие появления.

[mtit]

Caxaroza, именно. Стандартный ход. Имея компьютер - т.е. неограниченную (практически неограниченную - у меня 8 гигов оперативной и много дискового пространства) неограниченную доску - можно любые задачи решать с конца, записывая все результаты.
И частный случай - рекурсия. Суть рекурсии в двух словах:
1. Задаём результат на конечном шаге. Т.е. пользуясь здравым смыслом, принимаем за аксиому одно решение. Т.е. мы на финишной клетке поставили единичку. Эта единичка никак не вычисляется, но она частный случай для N=1. Очевидно.
2. Каждое последующее решение находим как функцию от предыдущих. В наше случае - сумма m штук.

Всё, дальше можно идти от начала к концу (языки высокого уровня здесь очень помогают - вся цепочка вопросов (для N=5?, для N=4?, для N=3? и т.д. реализуется компилятором).
Или от конца к началу. Тут тоже компьютер подспорье - иногда ветки решения раздваиваются (разделяются) и приходится своеобразное дерево выписывать, где только одна ветка приведёт к решению.
Сумбурно пытаюсь объснить, но, "как-то так".

[GORLAB]

Колюсь. Рекурсия на пальцах. Запишем в финишную клетку 1. Это будет количество вариантов прыжков: если мы на финише - вариант единственный. Продолжим классики ещё на m клеточек далее за финиш. Заполним их нулями. Естественно, нулями - назад прыгать нельзя, вариантов нет.
Теперь двигаемся от финиша к старту. В каждую клетку пишем сумму чисел из клеток, до которых мы можем допрыгнуть (сумму m следующих клеточек).
Когда мы дойдём до 0-вой клеточки (пересечём "Старт")(клеточки в условии задачи были с 1 по N)(Нулевую клеточку можно нарисовать для наглядности) - то в 0-вой клеточке мы получим количество вариантов прыжков.

Т.е. факториал всётаки. просто с измудрениями, как сумма факториалов от конца. От одного чтения уже голова кружиться, а уж от подсчёта...

[Марья-2]

Имхо, можно не "пятиться" назад, а начать с начала и двигаться к концу - записать 1 в "нулевую" клетку, а в n-й получить результат. Мне, например, такой образ действий более понятен - в каждой клетке записано количество способов туда добраться.
Правда, "физический смысл" самой первой единицы (как в том, так и в другом варианте отсчета) от меня ускользает

[Федя-Инженер]

Есессно... - с утра Солнца, вечерком Луны...

эдак и звезд восходы посчитать можно...
а вот Луна одна так может...
и как тут продолжительность "Лунного дня" меняется? и по какому закону?

[mtit]

"физический смысл" самой первой единицы (как в том, так и в другом варианте отсчета) от меня ускользает

Марья-2, допустим каждую последовательность мы завершаем специальной командой "больше не прыгать".
Т.е. из Вашего примера "1-1-3-больше не прыгать"
При N=1 и больше, все последовательности будут заканчиваться этой командой. Т.е. писать её нет смысла. Очевидные вещи человеческий разум просто отбрасывает - даже если мы её пишем, на просьбу прочитать каждый среднестатистический индивид ответит: "1-1-3".

И добавление этой команды не приведёт к изменению числа вариантов. Команда записывается только в конце последовательности. Сколько было у нас вариантов - столько и останется.
А вот при N=0 - появляется новая последовательность "больше не прыгать". И эта последовательность будет единственной, которая приведёт к финишу. Т.е. количество вариантов - 1. Именно число вариантов мы и пишем в клетки.

Кстати, у меня ошибочка:

Эта единичка никак не вычисляется, но она частный случай для N=1. Очевидно.

Извините.

[Марья-2]

Отвлечемся немного от математики

Диего Веласкес
Улисс Грант
Владимир Ильич Ленин
Иоганн Бальтазар Нейман
Шандор Петёфи
Жан Расин
Симон Родригес

По какому признаку эти разные люди оказались в одном списке?
Один из них несколько "выбивается" из общего ряда. Кто именно?

[Марья-2]

Galbert, я тоже про некоторых из них ранее никогда не слышала