 |
|
Модераторы: Poseidon |
 
|
|
помогите решить задачу, Методист О.Г. 
| BSOD |
|
|||
 Опытный  Профиль Группа: Участник Сообщений: 405 Регистрация: 1.11.2004 Где: Гомель Репутация: нет Всего: 3 |
Методист по информатике О.Г. живет на N-ом этаже 9-этажного дома с лифтом, который может останавливаться на каждом этаже. Между соседними этажами дома имеется лестница из 2-х пролетов, разделенных площадкой, по К ступенек в каждом пролете. Сколькими способами О.Г. может подняться на свой этаж, если поднимаясь по лестнице можно становиться на следующую ступеньку или через одну?
Пимер ввода: 6 14 Пример вывода: 7133524970800529778695960501 Это сообщение отредактировал(а) maximum - 22.7.2005, 16:16 -------------------- как корабль назовешь - то на нем и напишешь |
|||
|
||||
Загрузка ...
| mvdr |
|
|||
|
физик Профиль Группа: Участник Сообщений: 1349 Регистрация: 31.12.2004 Где: Волгоград, Россия Репутация: 7 Всего: 42 |
типичная комбинаторика.
сначала - думаем: 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 |
|
|||
 Ёжик Профиль Группа: Комодератор Сообщений: 1357 Регистрация: 6.1.2004 Репутация: 5 Всего: 18 |
Думаю, решение правильное (сам не могу думать - влияние "дум 3"), тут еще сверхдлинные числа нужны, но с единственной операцией "+1".
|
|||
|
||||
| mvdr |
|
|||
|
физик Профиль Группа: Участник Сообщений: 1349 Регистрация: 31.12.2004 Где: Волгоград, Россия Репутация: 7 Всего: 42 |
а на фиг кол-во ступенек? Или подразумевается. что он может идти по ступенкам так: 1112211? (т.е. 1 - на следующую, 2 - через одну)
-------------------- Появляюсь редко, но часто метко Изображать идиота сложнее, чем изображать умного: полезнее и не каждому дано |
|||
|
||||
| Pakshin A. S. |
|
|||
|
Эксперт Профиль Группа: Участник Клуба Сообщений: 5056 Регистрация: 16.2.2003 Репутация: 5 Всего: 61 |
Эх... даная задачка... когда-то на олимпиаде была... лень вспоминать, но думаю поск по нету дас пооложительный результат... Посмотри не трех-четырех сайтах с решениями олимп задач...
 |
|||
|
||||
| BSOD |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 405 Регистрация: 1.11.2004 Где: Гомель Репутация: нет Всего: 3 |
Femida
Блин, что-то я немного не въехал... вот у меня есть вариант решения... тока он не работает  b[i]:=b[i-1]+b[i-2]+b[i-2*k]; где b[i]- ступенька в массиве, k- кол-во ступенек в пролете + проверки, чтобы b[i-x] > 0; помоему кол-во способов добраться до i-той ступенки = сумме кол-в способов добраться до ступенек, с которых можно добраться до i-той что не так ?  -------------------- как корабль назовешь - то на нем и напишешь |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
Задача распадается на две.
1) Сколькими способами можно подняться по пролету из К ступеней, если можно на каждом шаге ступать либо на следующую, либо через одну ступеньку. 2) Сколькими способами можно подняться на N-й этаж, если на каждый следующий этаж с предыдущего можно подняться либо по лестнице, либо на лифте. Первое считается рекурсией, второе вообще элементарно... осталось учесть что этаж = 2 пролетам, то что получено в 1 подзадаче, возвесть в квадрат, и учитывать при расчетах в подзадаче 2. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| poor_yorik |
|
||||
 Шустрый Профиль Группа: Участник Сообщений: 148 Регистрация: 12.1.2005 Где: Общаги г. Киева Репутация: нет Всего: 8 |
Неправильно считаешь лифт.
Вообщем алгоритм такой для i-й ступеньки.
Это в том случае, если можно сесть в лифт на каждом этаже и подниматься на нем только наверх. Если же лифт можно вызвать только из первого этажа то ответ такой.
 Добавлено @ 10:02 Только здесь если сесть на лифт на 1-ом этаже, выйти на втором, потом подождать снова сесть в лифт и поехать на пятый, это будет не одно и тоже, что сразу поехать с первого на пятый сразу.  Это сообщение отредактировал(а) poor_yorik - 26.7.2005, 09:45 --------------------
Семь раз отмерь, один раз - откомпиль.... Семь раз отпей, один раз - отлей... Семь раз отъешь, один раз - не жадничай и другим дай... |
||||
|
|||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0928 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |