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

[Марья-2]

Но студент может на порядок ускорить вычисления(относительно той картинки, что у Вас), (не используя рекурсию), как?

Ваш студент выполняет подобные вычисления для произвольного значения N, не используя рекурсию? Любопытно
Что касается "бедной девочки", то ей вовсе не обязательно знать всякие мудреные слова Но если у нее есть другой способ, кроме как бессознательно следовать той же стратегии (т.е. выбрать "порядок обхода" (возрастание или убывание), фиксировать предыдущую позицию и варьировать последующие в выбранном порядке, каждый раз записывая мелом на асфальте только что "отпрыганный" вариант), то я очень хотела бы за ней понаблюдать

[olc0267]

Но какой алгоритм приемлем для девочки, которая имеет только асфальт, мелок и элементарные знания математики?

Если так, то
1. Минимальное число прыжков - округление до наибольшего целого числа Min=N/m. Максимальное Max=N. Число вариантов количества прыжков Max-Min+1.
2. Для каждого варианта количества прыжков находим все варинты как суммой чисел от 1 до m получить N при количестве чисел, равному числу прыжков.
3. Для каждого ряда чисел, найденного в пунктах 1 и 2 находим все перестановки чисел, отбрасывая варианты, когда переставляются одинаковые числа.

[Марья-2]

Для каждого варианта количества прыжков находим все варинты как суммой чисел от 1 до m получить N при количестве чисел, равному числу прыжков.
3. Для каждого ряда чисел, найденного в пунктах 1 и 2 находим все перестановки чисел, отбрасывая варианты, когда переставляются одинаковые числа.

Боюсь, что мама не дождется девочку к ужину Но идею попробую реализовать.
PS. Не, передумала. В реализации пункта 2 опять придется использовать рекурсию, а mtit знает какой-то другой способ Подожду.

Кстати, вот.
Бедная девочка...

[mtit]

Ваш студент выполняет подобные вычисления для произвольного значения N

Марья-2, нет, извините надо было сразу обговорить. Студент для наперёд жёстко заданного N=const пишет программу.

3. Для каждого ряда чисел, найденного в пунктах 1 и 2 находим все перестановки чисел, отбрасывая варианты, когда переставляются одинаковые числа.

olc0267, есть такая формула в комбинаторике. Ну собственно в этом и был вопрос задачи (алгоритм для студента). Вы решили более красиво, чем я. Я видел такое решение: всё те же вложенные циклы, но ищем не последовательность прыжков, а (как у Вас) наборы чисел. Например сразу упорядочив по возрастанию. Потом, для каждого варианта - просто применяем формулу из комбинаторики (перестановка с повторением, ЕМНП). Снимаю шляпу.

[Марья-2]

Студент для наперёд жёстко заданного N=const пишет программу.

...тем самым перечеркивая весь смысл программирования вообще Теперь понятно, почему он обошелся без рекурсии

olc0267, есть такая формула в комбинаторике. Ну собственно в этом и был вопрос задачи (алгоритм для студента).

mtit, а почему вы обошли вниманием пункт 2, который и составляет главный интерес? Или числа больше первого десятка Вас не интересуют в принципе?
Идея olc0267 мне понравилась. Поскольку по поводу использования рекурсии мы уже все выяснили, надо будет ее алгоритмизировать

[mtit]

Марья-2, ну в принципе пункт 2. решения olc0267 и мой вариант - я думаю решать так: Вложенные циклы. Пусть i - счётчик первого цикла, j - счётчик второго цикла, и так далее. Тогда i меняется от 1 до m, а j уже меняется от 1 до i. И так далее.
Т.е. в промежуточном решении получаются (3,1,1), но сразу отсекаются (1,3,1) и (1,1,3).
После небольшого раздумья мне кажется, что вариант решения olc0267 можно решить через моё, только вызывать несколько раз и наложить ограничения на количество прыжков.
Т.е. - да, красиво в задумке, а на практике - надо думать как также красиво реализовать.

Или числа больше первого десятка Вас не интересуют в принципе?

Именно для больших чисел и упомянут компьютер. Да, согласен, если я(школьник) не знает слово "рекурсия" - программирование и сводится к написанию не универсальной программы, а каждый раз новой. (Количество циклов - каждый раз новое). (Что не подходит под определение "компьютерный алгоритм").
Мой вариант с укорачивающимися циклами в этом случае лучше, чем Ваш вариант со скриншота. Можно тупо написать 100 циклов - при этом, если поставить предуслове, то лишние циклы просто не будут "крутиться".

[mtit]

Не могу гарантировать что в выходные буду онлайн. Поэтому даю небольшую подсказку:

Кстати, вот.
Бедная девочка...

Именно, если прочитать и осмыслить - то девочка отнюдь не бедная. Имея мелок и совсем чуть-чуть асфальта - девочка справится легко. (Главное, чтоб не устала писать числа со многими нулями , зачёркнуто, знаками).

[GORLAB]

...
Поскольку по поводу использования рекурсии мы уже все выяснили, надо будет ее алгоритмизировать

Грей Фрэнк (не путать с Сашей Грей ) это сделал до вас. Он любил вечерами под развесистым абажуром алгоритмы писать . Один из кодов даже в честь него назвали и патент ему дали.

Да только ту разновидность, что вы предложили, как-то не клеится к задаче в моём мозжечке! Впрочем, вопрос то - СКОЛЬКО ВАРИАНТОВ!? А не как их вычислить.
Чем вам формула предложенная выше не угодила?

[GORLAB]

Поэтому даю небольшую подсказку:

Зачем? Решение уже предложено ещё вчера.

Подобное уже решено сто лет назад. То же для кодового замка. сколько вариантов возможных чисел примет замок если количество разрядов N, а каждый разряд принимает значения от 1 до m.
Таже фигня про девочку с N количеством классиков и силушкой прыгать от 1 до m классика враз.
То же яйцо -вид сбоку.

Имея мелок и совсем чуть-чуть асфальта - девочка справится легко. (Главное, чтоб не устала писать числа со многими нулями , зачёркнуто, знаками).

Число действительно офигенное. Однако, формула есть желаемый результат. Не так ли?

[Марья-2]

Мой вариант с укорачивающимися циклами в этом случае лучше, чем Ваш вариант со скриншота.

Замечу, что на скриншоте всего лишь результат - он не может быть ни лучше, ни хуже, потому что он единственно правильный Реализация же осталась за кадром, но, смею Вас заверить, там нет лишних ходов - цикл каждого уровня прерывается в нужный момент.
Кстати, я засомневалась, что выполнение пункта 1 и пункта 2 варианта olc0267 (имеется в виду решение в общем виде, для произвольных N и M) в сумме обойдется "дешевле" - ведь то, что мы "сэкономим" при поиске разбиений, потом вcе равно "наверстаем" в пункте 3.
Тоже отбываю на выходные. Если не помру от жары, попробую проверить