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

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

Вот как представлена эта задача на сайте 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

OUTPUT.TXT

1

1   3 1

2

2   7 21

3

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) =  2N -1            (N <= K)

Справедливость этой формулы докажем строго, используя метод математической индукции.

Базис индукции: N = 1. Когда имеется одна ступенька, то существует только один способ добраться до верха – взойти на ступеньку.

C(1, K) = 20 = 1.

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

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

Рассуждая также как и в случае с получением соотношения (1), запишем соотношение для C(M+1, K)

C(M+1, K) = C(M, K) + C(M-1, K) + … + C(1, K) + 1

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

Учитывая индуктивное предположение, можно записать;

C(M+1, K) = 2M-1 + 2M-2 + … + 20 + 1= 2M

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

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

СС(N) = 2N — 1

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

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

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

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

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

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

CN = CN-1 + CN-2 + CN-3 + … + CN-K

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

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

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

ulong Second_C(int N, int K)

{

ulong M = 0;

if (K == 1) return 1;

if (N > K)

{

ulong[] CK = new ulong[K];

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

CK[0] = 1;

for (int i = 1; i < K; i++)

CK[i] = 2 * CK[i - 1];

//Цикл для вычисления n-го обобщенного числа Фибоначчи

for (int j = 0; j < N — K; j++)

{

//Вычисление очередного числа

M = 0;

for (int i = 0; i < K; i++)

M += CK[i];

//Сдвиг отрезка

for (int i = 0; i < K — 1; i++)

CK[i] = CK[i + 1];

CK[K - 1] = M;

}

// M — искомое число

}

else

M = (ulong)1 << (N — 1);

return M;

}

Еще один способ вычисления C(N, K)

Рассмотрим еще один полезный прием при работе с рекуррентными соотношениями.

Запишем еще раз соотношение для C(N, K):

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

Применив это же соотношение к первому слагаемому в правой части формулы, получим:

C(N, K) = 2*C(N — 2, K) + 2*C(N — 3, K) + … +2* C(N — K, K) + C(N – K -1, K)    (**)

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

C(N, K) = bk *C(K, K) + bk-1 * C(K – 1, K)  + b1 * C(1, K)               (***)

В этом соотношении ни рекурсии, ни рекуррентности уже нет, поскольку для С(N, K) получены простые соотношения, когда N < K. Но возникла новая проблема, поскольку появились коэффициенты b, значения которых нужно определить.

Рассмотрим алгоритм их вычисления. Заметьте, в соотношениях (*), (**) и (***) в правой части всегда присутствует сумма K слагаемых, но с разными коэффициентами. В исходном соотношении (*) все коэффициенты известны и равны единице. В результирующем соотношении (***) коэффициенты становятся искомыми.

Чтобы перейти от соотношения (*) к соотношению (***), нужно создать строку коэффициентов, положив их значения, равными единице. Затем над этой строкой выполнить N – K идентичных преобразований, в результате которых получим искомые коэффициенты.

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

bj = q + bj-1 (для всех j от k до 2)

b1  = q

Соотношение (**) является примером применения этого правила.

Приведу функцию, позволяющую вычислять эти коэффициенты:

ulong[] Coef(int N, int K)

{

ulong[] res = new ulong[K];

ulong q = 0;

for (int i = 0; i < K; i++)

res[ i] = 1;

for (int j = 1; j < N — K; j++ )

{

q = res[0];

for (int i = 0; i < K-1; i++)

res[i] = q + res[i + 1];

res[K - 1] = q;

}

return res;

}

Теперь нам осталось привести заключительную версию нашей программы, весьма эффективную, которая будет быстро работать для всех N и K в указанных диапазонах.

ulong C_new(int N, int K)

{

if (K == 1) return 1;

ulong M = 0;

if (N > K)

{

ulong[] coef = Coef(N, K);

for (int i = 0; i < K; i++)

M += coef[i]*((ulong)1 << (K — 1 — i));

}

else

M = (ulong)1 << (N — 1);

return M;

}

Несколько замечаний к этой программе:

  • Поскольку число способов прохождения лестницы резко растет с ростом N и K, то для этого числа используется максимально возможный целочисленный тип ulong. Он достаточен для значений N и K  в пределах 60. Для больших значений необходимо переходить к типу double. Такой вариант оставляю для самостоятельной работы.
  • Для ускорения вычисления операция возведения двойки в степень N заменена более быстрой операцией сдвига 1 влево на N разрядов. Заметьте, сдвиг числа влево на один разряд эквивалентен умножению на 2. Правда, этот прием применим только в пределах работы с целочисленным типом ulong. При переходе к типу double, придется пользоваться стандартным методом возведения в степень.
  • Рассмотренный вариант по сложности вычислений сравним с вариантом, основанным на обобщенных числах Фибоначчи. По числу выполняемых операций он чуть эффективнее, но оба алгоритма имеют одинаковую сложность O((N –K) * K).

Таким образом, нам удалось помочь зайчику посчитать число способов прохождения лестницы. Правда, ему не всегда хватит жизни, чтобы испытать все эти способы. Но наша цель достигнута. При значениях параметров N = 60 и K = 10 программа мгновенно выдает ответ:

C(60, 10) = 562217791476394080

 

/p