Лестница.

Seqular

Дата: Воскресенье, 28.10.2007, 19:11 | Сообщение # 1

Хранитель

Группа: Администраторы

Сообщений: 859

Репутация: 35

Статус: Offline

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

Думаем, господа.

Поддерживаю также проект сообщество молодых сисадминов

Seqular

Дата: Среда, 31.10.2007, 21:58 | Сообщение # 2

Хранитель

Группа: Администраторы

Сообщений: 859

Репутация: 35

Статус: Offline

Полагаю, что есть какая-то зависимость между количеством вариантов и ступенькой...
Вот ряд для 7-ой ступеньки:
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+2+1
1+1+1+2+1+1
1+1+2+1+1+1
1+2+1+1+1+1
2+1+1+1+1+1
1+1+1+2+2
1+1+2+1+2
1+1+2+2+1
1+ 2+1+1+2
1+2+1+2+1
1+2+2+1+1
2+1+1+1+2
2+1+1+2+1
2+1+2+1+1
2+2+1+1+1
2+2+2+1
2+2+1+2
2+1+2+2
1+2+2+2
1+1+1+1+3
1+1+1+3+1
1+1+3+1 +1
1+3+1+1+1
3+1+1+1+1
1+1+2+3
1+1+3+2
1+2+1+3
1+2+3+1
1+3+1+2
1+3+2+1
2+1+1+3
2+1+3+1
2+3+1+1
3+1+1+2
3+1+2+1
3+2+1+1
3+3+1
3 +1+3
1+3+3
2+2+3
2+3+2
3+2+2

44 способа.
Для 6-ти - 21
Для 5-ти - 13.
Для 4,3,2,1 - 7,4,2,1 соответственно.. Думаем над закономерностью.

Поддерживаю также проект сообщество молодых сисадминов

Seqular

Дата: Среда, 31.10.2007, 21:59 | Сообщение # 3

Хранитель

Группа: Администраторы

Сообщений: 859

Репутация: 35

Статус: Offline

Кстати, если кто-то распишет ряд для 8-ой ступеньки - будет легче аппроксимировать.

Поддерживаю также проект сообщество молодых сисадминов

Pavel

Дата: Воскресенье, 04.11.2007, 00:54 | Сообщение # 4

Приближенный

Группа: Модераторы

Сообщений: 210

Репутация: 17

Замечания: 0%

Статус: Offline

ЧЧего делать? Апроксимировать? Для 8 ступеньки наверное ни у кого терпения не хватит! biggrin

Задача интересная. Но я не решил пока как ее буду делать.

Seqular

Дата: Воскресенье, 04.11.2007, 10:02 | Сообщение # 5

Хранитель

Группа: Администраторы

Сообщений: 859

Репутация: 35

Статус: Offline

Интересно, что до 7-ой ступени прекрасно работает формула (n-1)^2 - (n-2) = C.
Где n - нужная ступень, а C - кол-во вариантов.... На 7-ми - сбивается, работает формула (n^2)-(n-2)=C. Так что не исключаю, что существует закономерность, выражаемая несколько другой формулой.

Поддерживаю также проект сообщество молодых сисадминов

Seqular

Дата: Вторник, 29.04.2008, 08:54 | Сообщение # 6

Хранитель

Группа: Администраторы

Сообщений: 859

Репутация: 35

Статус: Offline

Йо-майо. =) Я забыл решение выложить этой задачи. Формула элементарнейшая.
Итак, смотрим:
Для одной ступеньки - 1 вариант. Для 2 - 2 варианта. Для 3-х - 4 варианта.
Берем эти значения как константы. А пото делаем что-то типа ряда Фибоначчи, только складываем не 2 предыдущих, а 3! Т.е. для 4-х ступенек будет 4 + 2 + 1 = 7!
Для 5-ти - 7 + 4 + 2=13!
Для 6-ти - 13 + 7 + 4=24.
Для 7-ми - 24+13+7 = 44!
И так далее! Это все легко объясняемо, так что опущу объяснения! Запомните просто этот ряд. А так же общую формулу A[n] = A[n-3]+A[n-2]+A[n-1].

Поддерживаю также проект сообщество молодых сисадминов

		Четверг, 09.01.2025
	Pascal 4 All