Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Любой ЯП] мячик прыгает по лестнице

Автор: 14SatanA88 25.7.2011, 22:33

Доброго времени суток, уважаемые форумчане.

Помогите с алгоритмом решения задачи или, если есть, дайте код.

Условие
мячик прыгает по лестнице из N ступенек по не более M ступенек за раз; необходимо посчитать, сколькими способами он может спуститься без вывода самих вариантов прыжков ( O(n*m) )

Обязательно нужно соблюсти сложность алгоритма.

Автор: Silent 26.7.2011, 12:31

Код


#include <stdio.h>

int N, M;
int a[44];

inline int max(int a, int b){ return (a > b) ? a : b; }

int main()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) a[i] = 1;
    for (int i = 1; i < N; i++)
        for (int j = max(0, i-M); j < i; j++)
            a[i] += a[j];
    printf("%d",a[N-1]);
    return 0;
}

обращаю внимание, что последовательность растет очень быстро, и 44х значений хватит лишь для M=2, N=44. Если ограничения задачи выше - используй длинную арифметику, благо тут только сложения.

Автор: 14SatanA88 26.7.2011, 13:28

Silent, за код спасибо.
а ты не мог бы мне алгоритм объяснить?

Автор: DeMoNN 26.7.2011, 14:15

Это простая одномерная динамика. В массиве а храним число способов попасть на данную ступеньку. За первый ход мы можем попасть на каждую из М ступенек, так что заполняем первые М элементов массива единицами. А потом пробегаем циклом с первой ступеньки до последней и добавляем к каждой ступеньке, на которую мы можем попасть из текущей, число способов, которыми мы можем попасть в текущую ячейку (т.е. "переходим" на каждую ступеньку из текущей всеми возможными способами). Легко видеть, что этот алгоритм переберет все возможные способы спуститься на последнюю ступеньку.

Автор: 14SatanA88 26.7.2011, 14:32

DeMoNN, Silent, спасибо.