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

01.01.2020Динамическое программирование, Математика

Есть 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