2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача про зайчика
Сообщение17.09.2017, 11:18 
Цитата:
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек 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 различных маршрутов добраться до вершины лестницы.

Цитата:
К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.
$1 \leqslant K \leqslant N \leqslant  300$


Моё решение такое: представим, что лесенка - это у нас число в системе счисления по основанию $K+1$. Каждая ступенька - это разряд нашего числа. Мы будем перебирать все комбинации из диапазона $[0; m)$, где $m = (K+1)^N$ и отбирать те варианты, где сумма разрядов будет равна $N$ и остальные разряды будут равны нулю или разрядов для суммирования больше не будет. Варианты, где в середине последовательности идут нули или где сумма уже превысила $N$, но есть ещё разряды, не рассматриваем.

Проблема этого решения, что тут слишком большая алгоритмическая сложность. Поэтому прошу дать идею в какую сторону ещё можно посмотреть. Так сказать немного подтолкнуть, не давая значительного куска решения.

 
 
 
 Re: Задача про зайчика
Сообщение17.09.2017, 11:22 
Аватара пользователя
Gts в сообщении #1248361 писал(а):
Поэтому прошу дать идею в какую сторону ещё можно посмотреть.

Надо познакомиться с динамическим программированием.

 
 
 
 Re: Задача про зайчика
Сообщение17.09.2017, 21:34 
Это упорядоченные разбиения числа на слагаемые. Гуглите выделенное.

Кстати, здесь это тоже обсуждалось.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group