| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > помогите решить задачу |
| Автор: BSOD 21.7.2005, 22:20 |
| Методист по информатике О.Г. живет на N-ом этаже 9-этажного дома с лифтом, который может останавливаться на каждом этаже. Между соседними этажами дома имеется лестница из 2-х пролетов, разделенных площадкой, по К ступенек в каждом пролете. Сколькими способами О.Г. может подняться на свой этаж, если поднимаясь по лестнице можно становиться на следующую ступеньку или через одну? Пимер ввода: 6 14 Пример вывода: 7133524970800529778695960501 |
| Автор: mvdr 23.7.2005, 07:52 |
| типичная комбинаторика. сначала - думаем: 1) для конкретики берем 4 этаж. тогда N=4; S=(N-1)*2*K // N-1 т.к. чтобы зайти на 2 этаж надо пройти 2 пролета по К ступенек. считаем способы: все этажи на лифте 3 на лифте и 1 пешком, супая на каждую 3 на лифте и 1 пешком, чтупая через одну 2 на лифте, 1 пешком на каждую, и 1 на лифте 2 на лифте, 1 пешком через одну, 1 на лифте 2 на лифте. 1 пешком на каждую, 1 пешком через одну 2 на лифте, 1 пешком через одну, 1 пешком на каждую (это все таки по другому, чем в предыдущем случае) 2 на лифте, 2 пешком на каждую 2 на лифте, 2 пешком через одну .......... ......... все пешком на каждую все пешком через одну. |
| Автор: Fixin 23.7.2005, 14:24 |
| Думаю, решение правильное (сам не могу думать - влияние "дум 3"), тут еще сверхдлинные числа нужны, но с единственной операцией "+1". |
| Автор: mvdr 23.7.2005, 14:31 |
| а на фиг кол-во ступенек? Или подразумевается. что он может идти по ступенкам так: 1112211? (т.е. 1 - на следующую, 2 - через одну) |
| Автор: Pakshin A. S. 23.7.2005, 21:27 |
| Эх... даная задачка... когда-то на олимпиаде была... лень вспоминать, но думаю поск по нету дас пооложительный результат... Посмотри не трех-четырех сайтах с решениями олимп задач... |
| Автор: BSOD 23.7.2005, 22:28 |
| Femida Блин, что-то я немного не въехал... вот у меня есть вариант решения... тока он не работает  b[i]:=b[i-1]+b[i-2]+b[i-2*k]; где b[i]- ступенька в массиве, k- кол-во ступенек в пролете + проверки, чтобы b[i-x] > 0; помоему кол-во способов добраться до i-той ступенки = сумме кол-в способов добраться до ступенек, с которых можно добраться до i-той что не так ?  |
| Автор: Akina 24.7.2005, 20:38 |
| Задача распадается на две. 1) Сколькими способами можно подняться по пролету из К ступеней, если можно на каждом шаге ступать либо на следующую, либо через одну ступеньку. 2) Сколькими способами можно подняться на N-й этаж, если на каждый следующий этаж с предыдущего можно подняться либо по лестнице, либо на лифте. Первое считается рекурсией, второе вообще элементарно... осталось учесть что этаж = 2 пролетам, то что получено в 1 подзадаче, возвесть в квадрат, и учитывать при расчетах в подзадаче 2. |
| Автор: poor_yorik 25.7.2005, 09:57 | ||||
| Неправильно считаешь лифт. Вообщем алгоритм такой для i-й ступеньки.
Это в том случае, если можно сесть в лифт на каждом этаже и подниматься на нем только наверх. Если же лифт можно вызвать только из первого этажа то ответ такой.
 Добавлено @ 10:02 Только здесь если сесть на лифт на 1-ом этаже, выйти на втором, потом подождать снова сесть в лифт и поехать на пятый, это будет не одно и тоже, что сразу поехать с первого на пятый сразу.  |