Рубрики

Посчитай способы добраться до n-й ступени

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

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

Больше примеров:

Input: n = 1
Output: 1
There is only one way to climb 1 stair

Input: n = 2
Output: 2
There are two ways: (1, 1) and (2)

Input: n = 4
Output: 5
(1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)

Мы можем легко найти рекурсивную природу в вышеуказанной проблеме. Человек может добраться до n-й ступени либо с (n-1) -го уровня, либо с (n-2) -го уровня. Пусть общее количество способов добраться до ступеньки не будет «way (n)». Значение 'way (n)' можно записать следующим образом.

    ways(n) = ways(n-1) + ways(n-2)

Вышеупомянутое выражение на самом деле является выражением для чисел Фибоначчи , но есть одна вещь, на которую следует обратить внимание: значение way (n) равно fibonacci (n + 1).

путей (1) = фиб (2) = 1
пути (2) = фиб (3) = 2
пути (3) = фиб (4) = 3

Таким образом, мы можем использовать функцию для чисел Фибоначчи, чтобы найти значение путей (n). Ниже приводится реализация вышеуказанной идеи на C ++.

С

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

}

Джава

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

    }

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

питон

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

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

def fib(n):

    if n <= 1:

        return n

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

  
# возвращает нет. способов добраться до лестницы

def countWays(s):

    return fib(s + 1)

  
# Драйверная программа

  

s = 4

print "Number of ways = ",

print countWays(s)

  
# Предоставлено Харшитом Агравалом

C #

// C # программа для подсчета
// количество способов достичь
// н ая лестница

using System;

  

class GFG

{

    // Простая рекурсивная

    // программа для поиска 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);

    }

  

        // Код драйвера

    static public void Main ()

    {

        int s = 4;

        Console.WriteLine("Number of ways = "

                                 countWays(s));

    }

}

  
// Этот код добавлен
// от akt_mit

PHP

<?php
// PHP-программа для подсчета
// количество способов достичь
// н ая ступенька, когда человек
// можем подняться на 1, 2, ..м ступеньки
// вовремя.

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

function fib($n)

{

if ($n <= 1)

    return $n;

return fib($n - 1) + 

       fib($n - 2);

}

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

function countWays($s)

{

    return fib($s + 1);

}

  
// Код драйвера

$s = 4;

echo "Number of ways = "

           countWays($s);

  
// Этот код добавлен
// от m_kit
?>


Выход:

Number of ways = 5

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

Обобщение вышеуказанной проблемы
Как посчитать количество способов, если человек может подняться до m ступеней по заданному значению m? Например, если m равно 4, человек может одновременно подниматься на 1 ступеньку, 2 ступеньки, 3 ступеньки или 4 ступеньки.

Мы можем написать повторение следующим образом.

   ways(n, m) = ways(n-1, m) + ways(n-2, m) + ... ways(n-m, m) 

Ниже приводится реализация вышеупомянутых повторений.

С

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

}

Джава

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

    }

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

питон

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

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

def countWaysUtil(n,m):

    if n <= 1:

        return n

    res = 0

    i = 1

    while i<=m and i<=n:

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

        i = i + 1

    return res

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

def countWays(s,m):

    return countWaysUtil(s+1, m)

      

  
# Драйверная программа

s,m = 4,2

print "Number of ways =",countWays(s, m)

  
# Предоставлено Харшитом Агравалом

C #

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

using System;

  

class GFG {

      

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

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

    }

  

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

    // s'th лестница

    static int countWays(int s, int m)

    {

        return countWaysUtil(s+1, m);

    }

  

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

    public static void Main ()

    {

        int s = 4,m = 2;

        Console.Write("Number of ways = "

                           + countWays(s, m));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP-программа для подсчета
// количество способов достичь
// н ая ступенька, когда человек
// может подняться либо на 1, либо на 2
// лестницы за один раз

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

function countWaysUtil($n, $m)

{

    if ($n <= 1)

        return $n;

    $res = 0;

    for ($i = 1; $i <= $m && 

                 $i <= $n; $i++)

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

    return $res;

}

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

function countWays($s, $m)

{

    return countWaysUtil($s + 1, $m);

}

  
// Код драйвера

$s = 4; $m = 2;

echo "Nuber of ways = ",

      countWays($s, $m);

      
// Этот код добавлен
// от akt_mit
?>


Выход:

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

}

Джава

// 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("Nuber of ways = " + countWays(s, m));

    }

}

питон

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

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

def countWaysUtil(n,m):

    res = [0 for x in range(n)] # Создает список со всеми элементами 0

    res[0],res[1] = 1,1

      

    for i in range(2,n):

        j = 1

        while j<=m and j<=i:

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

            j = j + 1 

    return res[n-1]

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

def countWays(s,m):

    return countWaysUtil(s+1, m)

      
# Драйверная программа

s,m = 4,2

print "Nmber of ways =",countWays(s,m)

      
# Предоставлено Харшитом Агравалом

C #

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

using System;

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()

    {

        int s = 4, m = 2;

        Console.WriteLine("Number of ways = " + countWays(s, m));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

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

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

function countWaysUtil($n, $m)

{

    $res[0] = 1; $res[1] = 1;

    for ($i = 2; $i < $n; $i++)

    {

        $res[$i] = 0;

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

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

    }

    return $res[$n - 1];

}

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

function countWays($s, $m)

{

    return countWaysUtil($s + 1, $m);

}

  

    // Код драйвера

    $s = 4; 

    $m = 2;

    echo "Nuber of ways = ", countWays($s, $m);

  
// Этот код предоставлен m_kit
?>


Выход:

Number of ways = 5

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

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

Посчитай способы добраться до n-й ступени

0.00 (0%) 0 votes