Дорога к счастью

Чтобы вы знали: путь к счастью - это вовсе не дорога, а лестница. Лестница о тридцати ступенях. Но мало по ней просто прошагать. Для счастья нужно пройти все ступени только вперёд таким сочетанием разных шагов, как этого ещё никто не делал. А шаги получаются только трёх видов:
1. Через две ступеньки;
2. Через одну ступеньку;
3. На следующую ступеньку.

Сколько людей смогут обрести счастье, пройдя этой лестницей? 

Ответ: Обозначим через S(n) число людей, которые могут пройти по лестнице в n ступенек. Тогда S(1)=1 (один одинарный шаг), S(2)=2 (два одинарных, либо один двойной), S(3)=4 (одинарный+двойной, двойной+одинарный, три одинарных, один тройной). Дальше. Свяжем последовательность S(n) рекуррентной формулой. Все последовательности шагов заканчиваются либо одинарным, либо двойным, либо тройным шагом. Тогда число разных людей, закончивших восхождение на n-ю ступеньку одинарным шагом равно S(n-1); число разных людей, закончивших восхождение на n-ю ступеньку двойным шагом равно S(n-2); число разных людей, закончивших восхождение на n-ю ступеньку тройным шагом равно S(n-3). Значит S(n)=S(n-1)+S(n-2)+S(n-3). Что-то похожее на числа Фибоначчи, только суммируются не предыдущие 2 члена, а предыдущие 3. Итого 53 798 080 счастливцев. 

Ваша оценка: Нет Средняя: 3.8 (46 оценки)


Комментарии

Чисто математика

boje moi golova !!!

Все зависит от лестницы. Если лестница по типу - межэтажная то последняя (30 -я ступенька) является частью этажной площадки. А если лестница рабочая переносная (элементарно, деревянная - на крышу), то чтобы попасть к цели пути, с последней ступеньки нужно еще шаг сделать. Приведенный ответ верен для межэтажной лестницы, а для переносной рабочей он будет равен межэтажной с 31 ступенью, т.е 98950096 счастливцев.

ты просто написал здоровое число,чтобы никто не понял????

Все еще проще.
В задаче сказано "сочетанием шагов", а не как в решении "последовательностью".
Есть шаги в 3 ст., 2 и 1. И лестница в 30 ст.
Далее небольшая таблица:
Размерность шагов: 3 2 1
кол-во шагов: 10 0 0 1 вариант с 10 ш. по 3 ст.
9 1 1 2 вар. с 9 ш. по 3 ст.
9 0 3
8 3 0 4 вар.
8 2 2
8 1 4
8 0 6
7 4 1 5 вар.
7 3 3
7 2 5
7 1 7
7 0 9
6*7 вар.
5*8 вар.
4*10 вар.
3*11 вар.
2*13 вар.
1*14 вар.
0*16 вар.
Итого 1+2+4+5+7+8+10+11+13+14+16=91 человек.

Красивое решение, без перебора вариантов.

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

если считать сочетание шагов и не учитовать последовательность то это несколько миллиардов, если же не учитовать последовательность а только сочетание то вот:
10,0,0
9,0,3
9,1,1
8,0,6
8,1,4
8,2,2
8,3,0
7,0,9
7,1,7
7,2,5
7,3,3
7,4,1
6,0,12
6,1,10
6,2,8
6,3,6
6,4,4
6,5,2
6,6,0
5,0,15
5,1,13
5,2,11
5,3,9
5,4,7
5,5,5
5,6,3
5,7,1
4,0,18
4,1,16
4,2,14
4,3,12
4,4,10
4,5,8
4,6,6
4,7,4
4,8,2
4,9,0
3,0,21
3,1,19
3,2,17
3,3,15
3,4,13
3,5,11
3,6,9
3,7,7
3,8,5
3,9,3
3,10,1
2,0,24
2,1,22
2,2,20
2,3,18
2,4,16
2,5,14
2,6,12
2,7,10
2,8,8
2,9,6
2,10,4
2,12,2
2,14,0
1,0,27
1,1,25
1,2,23
1,3,21
1,4,19
1,5,17
1,6,15
1,7,13
1,8,11
1,9,9
1,10,7
1,11,5
1,12,3
1,13,1
0,0,30
0,1,28
0,2,26
0,3,24
0,4,22
0,5,20
0,6,18
0,7,16
0,8,14
0,9,12
0,10,10
0,11,8
0,12,6
0,13,4
0,14,2
0,15,0

тоесть 91 чел, внизу правильно ответил чел)

А я для каждого из 91 сочетания количества шагов нашел ещё и количество перестановок этих шагов и оно выглядело так:

ЧислоШаговПо2По3 = ШагиПо2 + ШагиПо3;
ЧислоСочетанийШаговПо2По3 = C(ЧислоШаговПо2По3, ШагиПо2);

ЧислоШаговПо1По2По3 = ШагиПо1 + ШагиПо2 + ШагиПо3; // всегда равняется 30
ЧислоСочетанийШаговПо1 = C(ЧислоШаговПо1По2По3, ЧислоШаговПо2По3);

ВСЕГО = ЧислоСочетанийШаговПо1 * ЧислоСочетанийШаговПо2По3;

ИТОГО = ИТОГО + ВСЕГО; // подсчет общего количества

Сложил количества перестановок сочетаний для каждого из 91 сочетания и получил ответ 53 798 080 - как у автора.

Всё понятно?

Да, кстати. Рекуррентное соотношение.

C(N, k) = C(N - 1, k) + C_(N - 1, k - 1)
C(N, 1) = C(N, N - 1) = N
C(N, N) = C(N, 0) = 1