Рубрики

C Программа для подсчета путей для достижения n-й ступени

Есть n лестниц, человек, стоящий внизу, хочет достичь вершины. Человек может подняться на 1 или 2 ступеньки одновременно. Подсчитайте количество способов, которыми человек может достичь вершины.

Рассмотрим пример, показанный на диаграмме. Значение n равно 3. Есть 3 способа достичь вершины. Диаграмма взята из пазлов Легче Фибоначчи

С

// AC программа для подсчета количества способов добраться до лестницы, когда
// человек может подниматься на 1, 2, .. м по лестнице одновременно.
#include <stdio.h>

  
// Простая рекурсивная программа для поиска n-го числа Фибоначчи

int fib(int n)

{

    if (n <= 1)

        return n;

    return fib(n - 1) + fib(n - 2);

}

  
// Возвращает количество способов добраться до лестницы

int countWays(int s)

{

    return fib(s + 1);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int s = 4;

    printf("Number of ways = %d", countWays(s));

    getchar();

    return 0;

}

Выход:

Number of ways = 5

Временная сложность вышеописанной реализации является экспоненциальной (золотое сечение повышено до степени n). Он может быть оптимизирован для работы за время O (Logn) с использованием ранее обсужденных оптимизаций функции Фибоначчи .

С

// AC программа для подсчета количества способов добраться до лестницы, когда
// человек может подниматься на 1 или 2 ступеньки одновременно
#include <stdio.h>

  
// Рекурсивная функция, используемая countWays

int countWaysUtil(int n, int m)

{

    if (n <= 1)

        return n;

    int res = 0;

    for (int i = 1; i <= m && i <= n; i++)

        res += countWaysUtil(n - i, m);

    return res;

}

  
// Возвращает количество способов добраться до лестницы

int countWays(int s, int m)

{

    return countWaysUtil(s + 1, m);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int s = 4, m = 2;

    printf("Nuber of ways = %d", countWays(s, m));

    return 0;

}

Выход:

Nuber of ways = 5

Временная сложность вышеуказанного решения является экспоненциальной. Его можно оптимизировать до O (mn) с помощью динамического программирования. Ниже приводится решение на основе динамического программирования. Мы строим таблицу res [] снизу вверх.

С

// AC программа для подсчета количества способов добраться до лестницы, когда
// человек может подниматься на 1, 2, .. м по лестнице одновременно
#include <stdio.h>

  
// Рекурсивная функция, используемая countWays

int countWaysUtil(int n, int m)

{

    int res[n];

    res[0] = 1;

    res[1] = 1;

    for (int i = 2; i < n; i++) {

        res[i] = 0;

        for (int j = 1; j <= m && j <= i; j++)

            res[i] += res[i - j];

    }

    return res[n - 1];

}

  
// Возвращает количество способов добраться до лестницы

int countWays(int s, int m)

{

    return countWaysUtil(s + 1, m);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int s = 4, m = 2;

    printf("Nuber of ways = %d", countWays(s, m));

    return 0;

}

Выход:

Nuber of ways = 5

Пожалуйста, обратитесь к полной статье о способах подсчета, чтобы добраться до n-й ступени, чтобы узнать больше!

Рекомендуемые посты:

C Программа для подсчета путей для достижения n-й ступени

0.00 (0%) 0 votes