Рубрики

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

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

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

Джава

class stairs {

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

    static int fib(int n)

    {

        if (n <= 1)

            return n;

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

    }

  

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

    static int countWays(int s)

    {

        return fib(s + 1);

    }

  

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

    public static void main(String args[])

    {

        int s = 4;

        System.out.println("Number of ways = " + countWays(s));

    }

} / * Этот код предоставлен Раджатом Мишрой * /

Выход:

Number of ways = 5

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

Джава

class stairs {

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

    static 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;

    }

  

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

    static int countWays(int s, int m)

    {

        return countWaysUtil(s + 1, m);

    }

  

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

    public static void main(String args[])

    {

        int s = 4, m = 2;

        System.out.println("Number of ways = " + countWays(s, m));

    }

} / * Этот код предоставлен Раджатом Мишрой * /

Выход:

Number of ways = 5

Джава

// Java-программа для подсчета количества способов добраться до лестницы, когда
// человек может подниматься на 1, 2, .. м по лестнице одновременно

  

class GFG {

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

    static int countWaysUtil(int n, int m)

    {

        int res[] = new int[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];

    }

  

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

    static int countWays(int s, int m)

    {

        return countWaysUtil(s + 1, m);

    }

  

    // Метод драйвера

    public static void main(String[] args)

    {

        int s = 4, m = 2;

        System.out.println("Number of ways = " + countWays(s, m));

    }

}

Выход:

Number of ways = 5

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

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

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

0.00 (0%) 0 votes