Другие языки программирования и технологии

Помогите пожалуйста оптимизировать решение задачи (Зайчик) на C++

Здравствуйте, мн надо решить задачу "Зайчик".
Условия таковы: http://acmp.ru/index.asp?main=task&id_task=11
Я написал решение, но оказалось, что оно слишком медленно работает.
Помогите мне пожалуйста оптимизировать код, он рабочий, но слишком медленный

Вот код: http://pastebin.com/dijNzXwi
Ruslan B
Ruslan B
166
Это классическая задача на динамическое программирование. Твой код работает намного медленнее, чем мог бы, потому что он оказывается на каждой позиции лестницы всегда, когда проходит по лежащему через нее пути, а достаточно всего одного раза.

1) Создай и занули массив чисел от 0 до N включительно
2) Положи в нулевой элемент (тот, который отвечает за то, что заяц на земле) единицу. То есть мы предполагаем, что на земле заяц стоит всего одним способом.
3) Иди по массиву и для каждой i-й ячейки выполняй цикл для j от 1 до k, прибавляя к [i+j]-й ячейке содержимое i-й.

У тебя получится, что в каждой ячейке находится количество способов в нее попасть, то есть в N-й ячейке количество способов попасть в N-ю ячейку.
Сложность получается N*K, что для таких маленьких N и K - фактически ничего.

Кстати, я даю уроки программирования. Самым способным бесплатно.
Yusup Saparov
Yusup Saparov
1 963
Лучший ответ
Ruslan B Спасибо! Но, за что отвечает k?
Для си вообще можно писать N и K так будет код еще понятней.
И ты хочешь сказать "Время: 1 сек" - оно решает дольше секунды?
ВМ
Виктор Мищук
58 583
Ruslan B Если ввести, например входные данные 100 и 100, то там ужс сколько. А ведь ограничение целых 300 на вход.
И система тестирования пишет Time limit exceeded
глянь на моего зайку
http://pastebin.com/WYghPFJW
идея в том, чтобы выходить по возможности раньше.
на тесте 10 30 проскакал в три раза быстрее твоего варианта
АВ
Александр Вусатюк
36 571
Ruslan B Я над таким вариантом думал. Обидно, но похоже тут рекурсия не пройдет.
Слишком медленно работают и твой и мой варианты.
Тут, кажется, только динамика, в которой я полный нуль.
Я хотел подумать над формулой, а потом смотрю... у тя в рекурентной функции ретёрна нет.... ты как хотел из неё выйти??
Никита Сергеевич
Никита Сергеевич
15 046
@ Мерей @ Мукатаев Есть у него база рекурсии. А ретерна нет, потому что тип void. Не путай тут!
Ruslan B Она просматривает все варианты, а потом вырубается.
Она выходит :)
Просто на высоких значениях слишком долго решает. На малых значениях и завершается, и ответ правильный даёт)
Для си вообще можно писать N и K так будет код еще понятней.
И ты хочешь сказать "Время: 1 сек" - оно решает дольше секунды?
ИН
Игорь Наумов
170

Похожие вопросы