Задача на динамическое программирование

@Jeron95 · Регистрация: 26.05.2012

Студворк — интернет-сервис помощи студентам

Даны n последовательных столбиков. Кузнечик находится на первом столбе, умеет прыгать на 1,2,...,k столбиков. Найти количество вариантов, которым он может допрыгать до n-го столба.
Я знаю что решается динамическим программированием, пытался сам в нём разобрать, но не получилось.
Мне нужен код на Pascal или C++, желательно с подробным объяснением.

valeriikozlov · 27.05.2012, 12:21

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var N,i,j,K:integer;
a:array[1..20] of longint;
 
 begin
 write('N= '); read(N);
 write('K= '); read(K);
 a[1]:=1;
 for i:=2 to N do 
 for j:=i-1 downto i-k do begin
 if j=0 then break;
 inc(a[i],a[j]);
 end;
 writeln('Ответ: ', a[N]);
 end.

Вы не написали, максимальные значения n и k, поэтому сделал так что программа работает при 1<=K,N<=20

Сообщение от Jeron95

пытался сам в нём разобрать, но не получилось.

В каждом элементе a[i] - хранится значение количества вариантов, которым можно достичь столбик с номером i. А расчитывается это значение так: суммируются значения для предыдущих k столбиков.

@Jeron95 · 28.05.2012, 21:16 **[ТС]**

valeriikozlov, Я проверил ваш код, либо я плохо объяснил, либо вы не так поняли,при значениях n=3 k=2 выводит 2, а должно быть три.

Добавлено через 2 минуты
Я понял почему, для первого столба на который он прыгнет, n=2

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@Jeron95 11 / 11 / 2 Регистрация: 26.05.2012 Сообщений: 54

	Задача на динамическое программирование 26.05.2012, 14:55. Показов 5886. Ответов 2 Метки нет (Все метки) Даны n последовательных столбиков. Кузнечик находится на первом столбе, умеет прыгать на 1,2,...,k столбиков. Найти количество вариантов, которым он может допрыгать до n-го столба. Я знаю что решается динамическим программированием, пытался сам в нём разобрать, но не получилось. Мне нужен код на Pascal или C++, желательно с подробным объяснением. 0

@Jeron95 11 / 11 / 2 Регистрация: 26.05.2012 Сообщений: 54
	28.05.2012, 21:16 [ТС]
	valeriikozlov, Я проверил ваш код, либо я плохо объяснил, либо вы не так поняли,при значениях n=3 k=2 выводит 2, а должно быть три. Добавлено через 2 минуты Я понял почему, для первого столба на который он прыгнет, n=2 0

Задача на динамическое программирование

Решение