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

Решить задачу динамического программирования

Методом прямой прогонки. (Написать программу)
Вот сама задача:
Кузнечик находиться на 1 клетке. У кузнечика есть любимое число k. Кузнечик может прыгать по прямой на 1, на 2, и на k клеток вперёд. Кузнечик хочет посчитать, сколько есть способов добраться до n клетки. Помогите кузнечику узнать ответ на его вопрос. Входные данные: n - количество клеток, k - любимое число кузнечика. Выходные данные: Требуется вывести одно число - ответ на задачу. Ограничения на входные данные: k < n <= 10^5 Пример:
Входные данные: 5 4
Выходные данные: 5
Михаил Муковнин
Михаил Муковнин
165
Результат в примере ошибочен:
1 1 1 1
2 1 1
1 2 1
1 1 2
2 2
4
ШЕСТЬ вариантов.

var
line: array [-100000..100000] of integer;
i, n, k: integer;
begin
read(n, k);
{этот цикл не нужен, если твоя версия Pascal обнуляет значения создаваемых переменных}
for i := 2 - k to 0 do line[i] := 0;
line[1] := 1;
for i := 2 to n do line[i] := line[i - 1] + line[i - 2] + line[i - k];
writeln(line[n])
end.

Предполагается, что k не равно 1 или 2.
Александр Петровичев
Александр Петровичев
73 989
Лучший ответ
Михаил Муковнин Учитель дал задние придумать и решить задачу динамического программирования методом прямой прогонки, я придумал такую задачу, поэтому она может быть не точной, можете её поправить
Что-то мне твой пример не очень понятен. 5 клеток он может пропрыгать так:

1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1

Явно больше, чем 5 вариантов. Поясни.
Ерлан Тасмаганбетов
Ерлан Тасмаганбетов
61 992
Asom Kambarov думаю, что вот такие варианты
1 1 1 1 1
1 1 1 2
1 2 2
1 4
Михаил Муковнин Учитель дал задние придумать и решить задачу динамического программирования методом прямой прогонки, я придумал такую задачу, поэтому она может быть не точной, можете её поправить
Метод прямой прогонки - это частный случай метода Гаусса для трёхдиагональной матрицы. Я в душе не ипу, причём здесь ДП. Не соизволишь разъяснить, как и зачем сюда можно додуматься прикрутить прогонку?
Михаил Казаков
Михаил Казаков
51 164
Михаил Муковнин Учитель дал задние придумать и решить задачу динамического программирования методом прямой прогонки, я придумал такую задачу, поэтому она может быть не точной, можете её поправить
cоставляем таблицу A (по примеру) - по горизонтали номер ячейки, по вертикали - число, на которое прыгает кузнечик.
в ячейке пишется количество способов которыми кузнечик может попасть в эту ячейку. Как его вычислить?
первый ряд - единицы, понятно. Второй ряд ( число 2), i-ая ячейка- пишем максимум из двух значений (верхняя ячейка и 1 + содержимое верхней ячейки под номером i-2. Также для следующей строки ( число 4).
Ответ на задачу - максимум таблицы
сам раза три таблицу перерисовывал. надо днем делать
Мирлан Болжобеков
Мирлан Болжобеков
25 445

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