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

[olc0267]

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

В третьем пункте не "наверстаем". Для третьего пункта в комбинаторике есть уже готовая формула "число перестановок c повторениями".
http://umk.portal.kemsu.ru/uch-mathe...sobie/r2-3.htm
Поэтому алгоритм для него городить не нужно. Нужно просто вставить в программу эту формулу.
Надо повнимательней почитать эти правила. Наверняка, и для 2-го пункта что-то есть.

[mtit]

GORLAB, какая формула? Что бы доказать что Вамиприведённая формула неверна - достаточно рассчитать один результат. N=5, m=3. По Вашей формуле получаем 27 или 91 (есть тонкости с началом отсчёта).
У всех остальных получилось 13. Всемирный заговор?

[Марья-2]

Для третьего пункта в комбинаторике есть уже готовая формула "число перестановок c повторениями".

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

количество композиций числа n длины k равно количеству (k-1)-элементных подмножеств (n-1)-элементного множества, то есть биномиальному коэффициенту \tbinom{n-1}{k-1}.

Т.е. это не что иное, как число сочетаний из (N-1) по (K-1), и вычисляется по известной формуле с тремя факториалами . Остается вывести формулу для количества композиций длины К, имеющих в своем составе только слагаемые не более М - и алгоритм сведется к одному циклу

[mtit]

Боюсь, что образование помешает здесь присутствующим дать девочке алгоритм. Ещё раз напоминаю - девочка развлекается, если вы пошлёте её читать комбинаторику - она расстроится.
Девочка имеет мелок, в клеточки она может записывать числа. Ей не обязательно знать формулы.

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

Это из Википедии, по ссылке Марьи-2.
Народ, неужели, по аналогии, ничего в голову не приходит?

[olc0267]

Девочка имеет мелок, в клеточки она может записывать числа. Ей не обязательно знать формулы.

Если двор, в котором живёт девочка, достаточно большой, и чистого асфальта там в избытке, то она может сделать так:
1. в первой строчке записать 1-1-1-1-1-1-1-... до N единиц.
2. во второй строчке две крайние правые единицы объединить в 2.
3. в тетьей строчке свинуть 2 влево на 1 позицию, на её место поставить 1.
4. двигать в каждой последующей строчке 2 влево, пока не упрётся.
5. повторить пункты 2-4.
6. когда ряд заполнится двойками, объединить два крайних правых числа и продолжить по аналогии с педыдущими шагами.
7. Числа не должны превышать m. Когда дальнейшее объединение ячеек станет невозможным, вернуться к пункту 2 и объединить 3 ячейки до 3, и повторить всё сначала.
И т.д.

Задачка в общем-то элементарная как для обычного математика (если пользоваться комбинаторикой), так и для обычного программиста (если пользоваться мелком).

1-1-1-1-1
1-1-1-2
1-1-2-1
1-2-1-1
2-1-1-1
2-1-2
2-2-1
1-1-3
1-3-1
3-1-1
2-3
3-2

12 комбинаций.

PS. Выпала комбинация 1-2-2.
Поэтому надо делать циклические сдвиги чисел - крайнее слева число переставлять на крайнюю правую позицию.

1-1-1-1-1
1-1-1-2
1-1-2-1
1-2-1-1
2-1-1-1
2-1-2
1-2-2
2-2-1
1-1-3
1-3-1
3-1-1
2-3
3-2

[mtit]

olc0267, маленькая подсказка - у девочки уже есть клеточки. В каждую клеточку она может вписать число. Комбинаторику девочка непереваривает. На дух не выносит.
Осталось выяснить с какой клеточки начинать, что записать в эту начальную клеточку, и (самое главное) что будут обозначать числа в этих клеточках?

[Марья-2]

Похоже, посетители темы не очень обеспокоены девочкиной проблемой . Я бы искренне хотела ей помочь, но даже треугольник Паскаля не наводит меня на сколько-нибудь умную мысль. В общем, "колитесь", mtit

[svsexmon]

Можно ли, не сходя с места, дважды в день видеть восход?

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

Похоже, посетители темы не очень обеспокоены девочкиной проблемой . .. В общем, "колитесь", mtit

Да... "судя" по подписи - товарисчу пора бы уже "уколоться"...
(бэз обид!!! - шутю я так... )

[mtit]

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

[Марья-2]

Красота