Зайчик прыгал через ступеньки

Содержание

Заяц на лестнице
Динамическое программирование на примере олимпиадной задачи «Зайчик»
Динамическое программирование заяц прыгает по ступенькам
Зайчик
Задача 11. Зайчик

Заяц на лестнице

Задача «Заяц на лестнице»

Вот как представлена эта задача на сайте acmp.ru:

Зайчик

(Время: 1 сек. Память: 16 Мб Сложность: 68%)

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не былоскучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

Входные данные

В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К — максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.

INPUT.TXT

3 10 274

Обозначим через C(N, K) – число способов, при котором можно достичь вершины лестницы из N ступеней при максимальном прыжке на K ступеней. Немного подумав, можно написать следующее рекуррентное соотношение:

C(N, K) = C(N — 1, K) + C(N — 2, K) + … + C(N — K, K) (1)

Вот какие рассуждения лежат в основе этого соотношения. Число возможных способов для достижения вершины N при максимальном прыжке K можно получить следующим образом:

Нужно посчитать число способов для достижения вершины N -1. Шагнув на следующую ступеньку, в каждом из этих способов, достигнем вершину N.
К полученному числу следует прибавить число способов для достижения вершины N — 2. Прыгнув на две ступеньки, в каждом из этих способов, достигнем вершину N.
Так продолжать, пока хватает силы допрыгнуть с достигнутой вершины до верха лестницы. Поэтому при максимальном прыжке K последнее слагаемое в соотношении задается значением C(N — K, K).

Заметьте, что это соотношение следует использовать только для значений N > K. В случае, когда максимальный прыжок позволяет достичь вершины лестницы, C(N, K) следует считать по более простой формуле:

C(N, K) = 2 N -1 (N 0 = 1.

Базисное утверждение справедливо.

Шаг индукции: Пусть утверждение справедливо для всех значений N от 1 до M. Докажем его справедливость в этом случае для N = M + 1 в предположении, что N M-1 + 2 M- 2 + … + 2 0 + 1= 2 M

Наше утверждение доказано.

Таким образом, число способов, которыми можно достичь вершины лестницы в предположении, что одним прыжком можно запрыгнуть на любую ступеньку вплоть до вершины, дается простой формулой:

Эта формула позволяет существенно упростить нашу программу, главное, ускорить вычисления.

Рекурсия, Рекуррентность и числа Фибоначчи

Вернемся к исходному рекуррентному соотношению, когда N > K:

C(N, K) = C(N — 1, K) + C(N — 2, K) + … + C(N — K, K)

Понятно, что любое рекуррентное соотношение можно реализовать рекурсивными функциями. Это позволяет быстро написать программу, проверить справедливость высказанных предположений. Но, зачастую, эффективность такой программы можно улучшить, избавившись от рекурсии.

Давайте перепишем это соотношение в виде, более привычном для рекуррентных соотношений:

Нетрудно заметить, что данное соотношение является расширенным вариантом чисел Фибоначчи. Отличие в том, что числа Фибоначчи представляют сумму двух предыдущих слагаемых, а здесь используется сумма K предыдущих слагаемых.

Начальный отрезок из первых K членов вычисляется как степени двойки, что было показано выше.

Приведу программу, представляющую естественное обобщение программы, вычисляющей числа Фибоначчи:

ulong Second_C(int N, int K)

if (K == 1) return 1;

ulong[] CK = new ulong[K];

//Заполнение начального отрезка из K элементов

Источник

Динамическое программирование на примере олимпиадной задачи «Зайчик»

Задача взята с acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 55%)

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

Входные данные:
В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К — максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.

Выходные данные:
В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.

Это прекрасная задача для объяснения принципов динамического программирования, но для начала разберемся с проблемами, которые такой подход решает. Я предлагаю посмотреть на предыдущую (более простую, но очень похожую) задачу «Лесенка«. Та задача решалась рекурсивно, при этом я постарался проиллюстрировать как получается более сложное решение из более простых (обрабатываемых рекурсивно) случаях. Попробуем применить такой подход к нашей задаче:

Функция принимает параметр k (количество ступенек на которые может прыгать заяц) и n — длина лестницы. Если длина лестницы равна нулю — то заяц прыгать не может, поэтому есть всего 1 вариант решения. Во всех остальных случаях мы говорим, что на n-ную ступеньку он может попасть с k предыдущих, поэтому и обрабатываем эти k ступенек рекурсивно (с учетом того, что n может оказаться меньше k).

Приведенное решение очень просто для восприятия, но работает оно очень медленно. Чтобы увидеть причины — предлагаю выписать вручную несколько примеров расчета лесенок, для этого выберем k, равное например 4:

step[0] => 1
step[1] => step[0]
step[2] => step[1] + step[0]
step[3] => step[2] + step[1] + step[0]
step[4] => step[3] + step[2] + step[1] + step[0]
step[5] => step[4] + step[3] + step[2] + step[1]
step[6] => step[5] + step[4] + step[3] + step[2]

Теперь прекрасно видна проблема приведенного выше решения. В нем, для для расчета step[6] было бы сделано 4 рекурсивных вызова, каждый из которых выполнил бы вызов step[2] . Напрашивается вычислить step[2] один раз и если вдруг такое значение потребуется — то использовать готовый результат, а не вычислять его повторно. Такой подход иногда называется табулированием или мемоизацией.

Суть динамического программирования как раз состоит в том, что мы:

разбиваем сложную задачу на более простые — делать это можем как с использованием рекурсии (см. первый вариант решения), так и без нее;
используем мемоизацию результатов вычислений (накапливаем их и используем вместо повторного вычисления)

Отсюда следует, что динамическое программирование даст хороший результат только, когда:

задача является рекуррентной (более сложная выражается через более простые — возможно вручную рассчитать примеры как было показано выше с массивом step);
задачи пересекаются — как было показано выше, результат вычисления step[2] используется k раз.

Если бы писали на каком-нибудь функциональном языке — то могли бы в приведенном выше решении добавить функции дополнительный аргумент-массив, который хранил бы результаты расчета ступенек лесенки, но на С++ мы можем создать такой массив прямо внутри функции, а рекурсию заменить циклом:

Приведенный выше код совершенно правильный и достаточно быстрый, однако решение не пройдет, ведь в результате могут получаться огромные числа, так например для максимально допустимых в условии задачи значений параметров k и n ответ должен быть таким:

Нам необходимо использовать длинную арифметику:

Источник

Динамическое программирование заяц прыгает по ступенькам

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.
Примеры
INPUT.TXT OUTPUT.TXT
|1 3 |1
|2 7 |21
|3 10 |274

В файл я уж сам
, мне бы алгоритм.

Добавлено через 1 час 25 минут
Тааварищи, паапрашу!

Добавлено через 20 часов 16 минут
Фуххх, нашел решение. В freepascal не заработал — только в pascalabc.net. Видимо, много «дельфового» кода:

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Источник

Зайчик

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Зайчик
Помогите пожалуйста с задачей. В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему.

Зайчик
Люди, помогите пожалуйста решить задачу! 2 недели не могу решить!! В нашем зоопарке появился.

Солнечный зайчик
Алиса, стоящая в начале координат бесконечной плоскости, посылает Бобу, который находится в точке с.

Зайчик попрыгайчик
Помогите решить пожалуйста, если есть идеи) Условия и примеры внизу Примечания Первый.

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Солнечный зайчик
Подскажите идею решения этой задачи пожалуйста Ограничение времени 1 секунда Ограничение.

Солнечный зайчик
Добрый вечер! Не могли вы бы объяснить такое явление: Есть квадратной формы зеркало, если с его.

Источник

Задача 11. Зайчик

Предлагаю потренироваться решать задачи на динамическое программирование на одной из классических задач. Читаем условие:

Как определить, что задача на динамическое программирование? Кроме того, что на сайте указан раздел, из которого задача, метод динамического программирования чаще всего помогает отвечать на вопросы «сколько способов?» и «какой способ оптимальный?». Да, есть ещё варианты, например, зная количество способов и первое число в «решении» можно найти k -ое по счёту решение.

Итак, в этой задаче как раз надо посчитать количество способов подняться на лестницу.

При решении методом динамического программирования надо определить три вещи: что является состоянием, переходы между состояниями и база динамики.

Состояние — это параметры, которыми характеризуется подзадача. Это может быть:

координаты точки на карте, если мы ищем путь в лабиринте;
левая и правая граница подстроки, если мы находим все подстроки палиндромы;
длины префиксов двух строк, если мы ищем расстояние Левенштейна между ними.

Чаще всего состояние можно понять из условия задачи. И лишь иногда к тому, что дано приходится добавлять дополнительный параметр.

В нашем случае надо найти количество способов добраться до ступеньки n , а подзадачами будут — найти количество способов добраться до ступеньки i (для всех i от 0 до n ). Значит в качестве состояния можно взять номер ступеньки.

Второй элемент — это переходы между состояниями. Их легко понять, если ответить на вопрос «как мы сюда можем попасть?». Например, если мы стоим на ступеньке i, то как мы могли на неё попасть? Очевидно, что с любой ступеньки с номерами i — k , i — k + 1 , . i — 1 (если такие есть, то есть не меньше нуля).

Зная состояния, мы понимаем, как хранить данные (одномерный массив), зная переходы, мы понимаем, как заполнять нашу структуру данных (слева направо, так как для больших номеров состояния нужны значения меньших состояний).

Осталось определиться с базой динамики. Часто это тривиальные или даже вырожденные состояния, для которых мы уже знаем ответ. База динамики нужна для того, чтобы инициализировать стартовые значения, опираясь на которые можно будет посчитать ответ для всех подзадач, используя переходы между состояниями.

У нас вырожденным случаем является нулевая ступенька (можно было бы взять и тривиальное состояние — первую ступеньку) и для неё ответ 1. Так как зайчик уже там и значит попал туда одним единственным способом.

После такого разбора написать решение не составит труда:

Источник