Conte as maneiras de chegar à enésima escada
Existem n escadas, uma pessoa que está na parte inferior quer chegar ao topo. A pessoa pode subir 1 ou 2 degraus de cada vez. Conte o número de maneiras pelas quais a pessoa pode chegar ao topo.
Considere o exemplo mostrado no diagrama. O valor de n é 3. Existem 3 maneiras de chegar ao topo. O diagrama é retirado dos quebra-cabeças Fibonacci mais fáceis
Exemplos:
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)
Método 1 : O primeiro método usa a técnica de recursão para resolver este problema.
Abordagem: podemos encontrar facilmente a natureza recursiva do problema acima. A pessoa pode alcançar n th escada a partir de qualquer (n-1) th escada ou a partir de (N-2) th escada. Assim, para cada escada n , tentamos descobrir o número de maneiras de chegar a n-1 ª escada e n-2 ª escada e adicioná-los para dar a resposta para o n º escada. Portanto, a expressão para tal abordagem acaba sendo:
ways(n) = ways(n-1) + ways(n-2)
A expressão acima é na verdade a expressão para números de Fibonacci , mas há uma coisa a se notar, o valor de maneiras (n) é igual a fibonacci (n + 1).
ways(1) = fib(2) = 1 ways(2) = fib(3) = 2 ways(3) = fib(4) = 3
Para um melhor entendimento, vamos consultar a árvore de recursão abaixo -:
Input: N = 4
fib(5)
'3' / \ '2'
/ \
fib(4) fib(3)
'2' / \ '1' / \
/ \ / \
fib(3) fib(2)fib(2) fib(1)
/ \ '1' / \ '0'
'1' / '1'\ / \
/ \ fib(1) fib(0)
fib(2) fib(1)
Portanto, podemos usar a função para números de Fibonacci para encontrar o valor das maneiras (n). A seguir está a implementação em C++ da ideia acima.
// C++ program to count number of
// ways to reach Nth stair
#include <bits/stdc++.h>
using namespace std;
// A simple recursive program to
// find N'th fibonacci number
int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways to
// reach s'th stair
int countWays(int s)
{
return fib(s + 1);
}
// Driver C
int main()
{
int s = 4;
cout << "Number of ways = " << countWays(s);
return 0;
}
// This code is contributed by shubhamsingh10// C Program to count number of
// ways to reach Nth stair
#include <stdio.h>
// A simple recursive program to
// find n'th fibonacci number
int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways to reach s'th stair
int countWays(int s)
{
return fib(s + 1);
}
// Driver program to test above functions
int main()
{
int s = 4;
printf("Number of ways = %d", countWays(s));
getchar();
return 0;
}class stairs {
// A simple recursive program to find
// n'th fibonacci number
static int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways to reach s'th stair
static int countWays(int s)
{
return fib(s + 1);
}
/* Driver program to test above function */
public static void main(String args[])
{
int s = 4;
System.out.println("Number of ways = " + countWays(s));
}
} /* This code is contributed by Rajat Mishra */# Python program to count
# ways to reach nth stair
# Recursive function to find
# Nth fibonacci number
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# Returns no. of ways to
# reach sth stair
def countWays(s):
return fib(s + 1)
# Driver program
s = 4
print "Number of ways = ",
print countWays(s)
# Contributed by Harshit Agrawal// C# program to count the
// number of ways to reach
// n'th stair
using System;
class GFG {
// A simple recursive
// program to find n'th
// fibonacci number
static int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways
// to reach s'th stair
static int countWays(int s)
{
return fib(s + 1);
}
// Driver Code
static public void Main()
{
int s = 4;
Console.WriteLine("Number of ways = " + countWays(s));
}
}
// This code is contributed
// by akt_mit<?php
// A PHP program to count
// number of ways to reach
// n'th stair when a person
// can climb 1, 2, ..m stairs
// at a time.
// A simple recursive
// function to find n'th
// fibonacci number
function fib($n)
{
if ($n <= 1)
return $n;
return fib($n - 1) +
fib($n - 2);
}
// Returns number of
// ways to reach s'th stair
function countWays($s)
{
return fib($s + 1);
}
// Driver Code
$s = 4;
echo "Number of ways = ",
countWays($s);
// This code is contributed
// by m_kit
?><script>
// A Javascript program to count
// number of ways to reach
// n'th stair when a person
// can climb 1, 2, ..m stairs
// at a time.
// A simple recursive
// function to find n'th
// fibonacci number
function fib(n)
{
if (n <= 1)
return n;
return fib(n - 1) +
fib(n - 2);
}
// Returns number of
// ways to reach s'th stair
function countWays(s)
{
return fib(s + 1);
}
// Driver Code
let s = 4;
document.write("Number of ways = " + countWays(s));
// This code is contributed
// by _saurabh_jaiswal
</script>Saída:
Number of ways = 5
Análise de complexidade:
- Complexidade de tempo: O (2 ^ n)
A complexidade de tempo da implementação acima é exponencial (razão áurea elevada à potência n) devido a cálculos redundantes. Pode ser otimizado para trabalhar em tempo O (Logn) usando as otimizações de função de Fibonacci discutidas anteriormente . - Espaço Auxiliar: O (1)
Generalização do problema
Como contar o número de maneiras se a pessoa pode subir m escadas para um determinado valor m. Por exemplo, se m for 4, a pessoa pode subir 1 escada ou 2 escadas ou 3 ou 4 escadas de cada vez.
Abordagem: Para a generalização da abordagem acima, a seguinte relação recursiva pode ser usada.
ways(n, m) = ways(n-1, m) + ways(n-2, m) + ... ways(n-m, m)
Nesta abordagem para alcançar a n- ésima escada , tente subir todos os números possíveis de escadas menores que igual an a partir da escada atual.
A seguir está a implementação da recorrência acima.
// C++ program to count number of ways
// to reach nth stair when a person
// can climb either 1 or 2 stairs at a time
#include <bits/stdc++.h>
using namespace std;
// A recursive function used by 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;
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver code
int main()
{
int s = 4, m = 2;
cout << "Number of ways = " << countWays(s, m);
return 0;
}
// This code is contribute by shubhamsingh10// C program to count number of ways
// to reach nth stair when a person
// can climb either 1 or 2 stairs at a time
#include <stdio.h>
// A recursive function used by 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;
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver program to test above functions-
int main()
{
int s = 4, m = 2;
printf("Number of ways = %d", countWays(s, m));
return 0;
}class stairs {
// A recursive function used by 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;
}
// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
/* Driver program to test above function */
public static void main(String args[])
{
int s = 4, m = 2;
System.out.println("Number of ways = "
+ countWays(s, m));
}
} /* This code is contributed by Rajat Mishra */# A program to count the number of ways
# to reach n'th stair
# Recursive function used by 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
# Returns number of ways to reach s'th stair
def countWays(s, m):
return countWaysUtil(s + 1, m)
# Driver program
s, m = 4, 2
print "Number of ways =", countWays(s, m)
# Contributed by Harshit Agrawal<?php
// A PHP program to count
// number of ways to reach
// n'th stair when a person
// can climb either 1 or 2
// stairs at a time
// A recursive function
// used by 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;
}
// Returns number of ways
// to reach s'th stair
function countWays($s, $m)
{
return countWaysUtil($s + 1, $m);
}
// Driver Code
$s = 4; $m = 2;
echo "Number of ways = ",
countWays($s, $m);
// This code is contributed
// by akt_mit
?><script>
// A Javascript program to count
// number of ways to reach
// n'th stair when a person
// can climb either 1 or 2
// stairs at a time
// A recursive function
// used by countWays
function countWaysUtil(n, m)
{
if (n <= 1)
return n;
let res = 0;
for (let i = 1; i <= m &&
i <= n; i++)
res += countWaysUtil(n - i, m);
return res;
}
// Returns number of ways
// to reach s'th stair
function countWays(s, m)
{
return countWaysUtil(s + 1, m);
}
// Driver Code
let s = 4;
let m = 2;
document.write("Number of ways = " + countWays(s, m));
// This code is contributed by _saurabh_jaiswal
</script>Saída:
Number of ways = 5
Análise de complexidade:
- Complexidade de tempo: O (2 ^ n)
A complexidade de tempo da implementação acima é exponencial (proporção áurea elevada à potência n) devido a cálculos redundantes. Ele pode ser otimizado para O (m * n) usando a programação dinâmica. - Espaço Auxiliar: O (1)
Método 2 : Este método usa a técnica de Programação Dinâmica para chegar à solução.
Abordagem: Criamos uma tabela res [] de maneira ascendente usando a seguinte relação:
res[i] = res[i] + res[i-j] for every (i-j) >= 0
de modo que o i ésimo índice da array conterá o número de caminhos necessários para alcançar o i ésimo passo considerando todas as possibilidades de escalada (ou seja, de 1 a i ).
O código abaixo implementa a abordagem acima:
// C++ program to count number of ways
// to reach n'th stair when a person
// can climb 1, 2, ..m stairs at a time
#include <iostream>
using namespace std;
// A recursive function used by 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];
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver code
int main()
{
int s = 4, m = 2;
cout << "Number of ways = "
<< countWays(s, m);
return 0;
}
// This code is contributed by shubhamsingh10// A C program to count number of ways
// to reach n'th stair when
// a person can climb 1, 2, ..m stairs at a time
#include <stdio.h>
// A recursive function used by 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];
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver program to test above functions
int main()
{
int s = 4, m = 2;
printf("Number of ways = %d", countWays(s, m));
return 0;
}// Java program to count number of ways
// to reach n't stair when a person
// can climb 1, 2, ..m stairs at a time
class GFG {
// A recursive function used by 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];
}
// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver method
public static void main(String[] args)
{
int s = 4, m = 2;
System.out.println("Number of ways = "
+ countWays(s, m));
}
}# A program to count the number of
# ways to reach n'th stair
# Recursive function used by countWays
def countWaysUtil(n, m):
# Creates list res with all elements 0
res = [0 for x in range(n)]
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]
# Returns number of ways to reach s'th stair
def countWays(s, m):
return countWaysUtil(s + 1, m)
# Driver Program
s, m = 4, 2
print "Number of ways =", countWays(s, m)
# Contributed by Harshit Agrawal// C# program to count number
// of ways to reach n'th stair when
// a person can climb 1, 2, ..m
// stairs at a time
using System;
class GFG {
// A recursive function
// used by 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];
}
// Returns number of ways
// to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver Code
public static void Main()
{
int s = 4, m = 2;
Console.WriteLine("Number of ways = "
+ countWays(s, m));
}
}
// This code is contributed by anuj_67.<?php
// A PHP program to count number
// of ways to reach n't stair when
// a person can climb 1, 2, ..m
// stairs at a time
// A recursive function used by 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];
}
// Returns number of ways
// to reach s'th stair
function countWays($s, $m)
{
return countWaysUtil($s + 1, $m);
}
// Driver Code
$s = 4;
$m = 2;
echo "Number of ways = ", countWays($s, $m);
// This code is contributed by m_kit
?><script>
// A Javascript program to count number
// of ways to reach n't stair when
// a person can climb 1, 2, ..m
// stairs at a time
// A recursive function used by countWays
function countWaysUtil(n, m)
{
let res = [];
res[0] = 1;
res[1] = 1;
for (let i = 2; i < n; i++)
{
res[i] = 0;
for (let j = 1; j <= m && j <= i; j++)
res[i] += res[i - j];
}
return res[n - 1];
}
// Returns number of ways
// to reach s'th stair
function countWays(s, m)
{
return countWaysUtil(s + 1, m);
}
// Driver Code
let s = 4;
let m = 2;
document.write("Number of ways = " + countWays(s, m));
// This code is contributed by _saurabh_jaiswal
</script>Saída:
Number of ways = 5
Análise de complexidade:
- Complexidade de tempo: O (m * n)
- Espaço Auxiliar: O (n)
Método 3 : O terceiro método usa a técnica de Janela Deslizante para chegar à solução.
Abordagem: Este método implementa com eficiência a abordagem de Programação Dinâmica acima.
Nesta abordagem para a i ª escada, mantemos uma janela de soma das últimas m escadas possíveis a partir da qual podemos subir até a i ª escada. Em vez de executar um loop interno, mantemos o resultado do loop interno em uma variável temporária. Removemos os elementos da janela anterior e adicionamos o elemento da janela atual e atualizamos a soma.
O código abaixo implementa a ideia acima
// A C++ program to count the number of ways
// to reach n'th stair when user
// climb 1 .. m stairs at a time.
// Contributor: rsampaths16
#include <iostream>
using namespace std;
// Returns number of ways
// to reach s'th stair
int countWays(int n, int m)
{
int res[n + 1];
int temp = 0;
res[0] = 1;
for (int i = 1; i <= n; i++)
{
int s = i - m - 1;
int e = i - 1;
if (s >= 0)
{
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
int main()
{
int n = 5, m = 3;
cout << "Number of ways = "
<< countWays(n, m);
return 0;
}
// This code is contributed by shubhamsingh10// A C program to count the number of ways
// to reach n'th stair when user
// climb 1 .. m stairs at a time.
// Contributor: rsampaths16
#include <stdio.h>
// Returns number of ways
// to reach s'th stair
int countWays(int n, int m)
{
int res[n + 1];
int temp = 0;
res[0] = 1;
for (int i = 1; i <= n; i++) {
int s = i - m - 1;
int e = i - 1;
if (s >= 0) {
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
int main()
{
int n = 5, m = 3;
printf("Number of ways = %d",
countWays(n, m));
return 0;
}// Java program to count number of
// ways to reach n't stair when a
// person can climb 1, 2, ..m
// stairs at a time
class GFG{
// Returns number of ways
// to reach s'th stair
static int countWays(int n, int m)
{
int res[] = new int[n + 1];
int temp = 0;
res[0] = 1;
for(int i = 1; i <= n; i++)
{
int s = i - m - 1;
int e = i - 1;
if (s >= 0)
{
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
public static void main(String[] args)
{
int n = 5, m = 3;
System.out.println("Number of ways = " +
countWays(n, m));
}
}
// This code is contributed by equbalzeeshan# Python3 program to count the number
# of ways to reach n'th stair when
# user climb 1 .. m stairs at a time.
# Function to count number of ways
# to reach s'th stair
def countWays(n, m):
temp = 0
res = [1]
for i in range(1, n + 1):
s = i - m - 1
e = i - 1
if (s >= 0):
temp -= res[s]
temp += res[e]
res.append(temp)
return res[n]
# Driver Code
n = 5
m = 3
print('Number of ways =', countWays(n, m))
# This code is contributed by 31ajaydandge// C# program to count number of
// ways to reach n'th stair when
// a person can climb 1, 2, ..m
// stairs at a time
using System;
class GFG{
// Returns number of ways
// to reach s'th stair
static int countWays(int n, int m)
{
int[] res = new int[n + 1];
int temp = 0;
res[0] = 1;
for(int i = 1; i <= n; i++)
{
int s = i - m - 1;
int e = i - 1;
if (s >= 0)
{
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
public static void Main()
{
int n = 5, m = 3;
Console.WriteLine("Number of ways = " +
countWays(n, m));
}
}
// This code is contributed by equbalzeeshan<script>
// Javascript program to count number of
// ways to reach n't stair when a
// person can climb 1, 2, ..m
// stairs at a time
// Returns number of ways
// to reach s'th stair
function countWays(n , m)
{
var res = Array(n + 1).fill(0);
var temp = 0;
res[0] = 1;
for (i = 1; i <= n; i++) {
var s = i - m - 1;
var e = i - 1;
if (s >= 0) {
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
var n = 5, m = 3;
document.write("Number of ways = " +
countWays(n, m));
// This code contributed by Rajput-Ji
</script>Saída:
Number of ways = 13
Análise de complexidade:
- Complexidade de tempo: O (n)
- Espaço Auxiliar: O (n)
Este artigo é uma contribuição de Abhishek . Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima
Método 4 : O quarto método usa matemática simples, mas isso só é aplicável para este problema se (a ordem não importa) durante a contagem de passos.
Abordagem : Neste método, simplesmente contamos o número de conjuntos com 2.
#include <iostream>
using namespace std;
int main() {
int n;
n=5;
// Here n/2 is done to count the number 2's in n
// 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
cout<<"Number of ways when order of steps does not matter is : "<<1+(n/2)<<endl;
return 0;
}import java.util.*;
class GFG{
public static void main(String[] args)
{
int n;
n = 5;
// Here n/2 is done to count the number 2's
// in n 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
System.out.print("Number of ways when order of steps " +
"does not matter is : " + (1 + (n / 2)));
}
}
// This code is contributed by todaysgauravn = 5
# Here n/2 is done to count the number 2's in n
# 1 is added for case where there is no 2.
# eg: if n=4 ans will be 3.
# {1,1,1,1} set having no 2.
# {1,1,2} ans {2,2} (n/2) sets containing 2.
print("Number of ways when order "
"of steps does not matter is : ", 1 + (n // 2))
# This code is contributed by rohitsingh07052using System;
class GFG{
static public void Main()
{
int n;
n = 5;
// Here n/2 is done to count the number 2's
// in n 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
Console.WriteLine("Number of ways when order of steps " +
"does not matter is : " + (1 + (n / 2)));
}
}
// This code is contributed by Ankita saini<script>
var n;
n = 5;
// Here n/2 is done to count the number 2's in n
// 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
document.write("Number of ways when order " +
"of steps does not matter is : ",
parseInt(1 + (n / 2)));
// This code is contributed by Ankita saini
</script>Saída:
Number of ways when order of steps does not matter is : 3
Análise de complexidade:
- Complexidade de tempo: O (1)
- Complexidade do espaço: O (1)
Nota: Este método é aplicável apenas para a questão Contagem de caminhos até a N'th Stair (a ordem não importa).
A ordem não importa significa que para n = 4 {1 2 1}, {2 1 1}, {1 1 2} são considerados iguais.
Método 5: Este método usa a técnica de Exponenciação de Arrayes para chegar à solução.
Abordagem: O número de maneiras de alcançar a n- ésima escada (a ordem é importante) é igual à soma do número de maneiras de alcançar (n-1) a escada e (n-2) a escada
Isso corresponde à seguinte relação de recorrência:
f(n) = f(n-1) + f(n-2) f(1) = 1 f(2) = 2
onde f (n) indica o número de maneiras de alcançar a n- ésima escada
Observação:
f (1) = 1 porque há apenas 1 maneira de alcançar n = 1 escada {1}
f (2) = 2 porque existem 2 maneiras de alcançar n = 2 escadas {1,1}, {2}
É um tipo de relação de recorrência linear com coeficientes constantes e podemos resolvê-los usando o método de Exponenciação de Arrayes que basicamente encontra uma array de transformação para uma dada relação de recorrência e aplica repetidamente esta transformação a um vetor base para chegar à solução).
F(n) = CN-1F(1) where C is the transformation matrix F(1) is the base vector F(n) is the desired solution
Portanto, para o nosso caso, a array de transformação C seria:
| 0 | 1 |
| 1 | 1 |
C N-1 pode ser calculado usando a técnica de divisão e conquista, em O ((K ^ 3) Log n) onde K é a dimensão de C
E F (1):
| 1 |
| 2 |
Por exemplo, para n = 4:
F (4) = C 3 F (1)
C 3 =
| 1 | 2 |
| 2 | 3 |
Portanto, C 3 F (1) =
| 5 |
| 8 |
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long> > matrix;
#define LOOP(i, n) for (int i = 1; i < n; i++)
// Computes A*B
// where A,B are square matrices
matrix mul(matrix A, matrix B, long long MOD = 1000000007)
{
int K = A.size();
matrix C(K, vector<long long>(K, 0));
LOOP(i, K)
LOOP(j, K)
LOOP(k, K)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
// Computes A^n
matrix power(matrix A, long long n)
{
if (n == 1)
return A;
if (n % 2 != 0) {
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1));
}
else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A);
}
return A;
}
long long ways(int n)
{
vector<long long> F(3);
F[1] = 1;
F[2] = 2;
int K = 2;
long long MOD = 1000000007;
// create K*K matrix
matrix C(K + 1, vector<long long>(K + 1, 0));
/*
A matrix with (i+1)th element as 1 and last row
contains constants
[
[0 1 0 0 ... 0]
[0 0 1 0 ... 0]
[0 0 0 1 ... 0]
[. . . . ... .]
[. . . . ... .]
[c(k) c(k-1) c(k-2) ... c1]
]
*/
for (int i = 1; i < K; ++i) {
C[i][i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
C[K][1] = 1;
C[K][2] = 1;
if (n <= 2)
return F[n];
// f(n) = C^(n-1)*F
C = power(C, n - 1);
long long result = 0;
// result will be the first row of C^(n-1)*F
for (int i = 1; i <= K; ++i) {
result = (result + C[1][i] * F[i]) % MOD;
}
return result;
}
int main()
{
int n = 4;
cout << "Number of ways = " << ways(n) << endl;
}
// This code is contributed by darshang631Número de maneiras = 5
Análise de complexidade:
- Complexidade de tempo: O (Log n)
- Complexidade do espaço: O (1)
Generalização do problema:
Dada uma array A {a1, a2,…., Am} contendo todos os degraus válidos, calcule o número de maneiras de alcançar a n- ésima escada. (A ordem importa)
Exemplos :
Input:
A = [1,2]
n = 4
Output: 5
Explanation:
This is the given problem, i.e, count the number of ways to reach n=4 stairs with climbing 1 or 2 stairs at a time
Therefore, ways will be: {1,1,1,1} {1,1,2} {1,2,1} {2,1,1} {2,2} = 5
Input:
A = [2,4,5]
n = 9
Output: 5
Explanation:
There are 5 ways to reach n=9 stairs with climbing 2 or 4 or 5 stairs at a time
Therefore, ways will be: {5,4} {4,5} {2,2,5} {2,5,2} {5,2,2} = 5
Abordagem:
O número de maneiras de alcançar a enésima escada é dado pela seguinte relação de recorrência
Seja K o maior elemento em A.
Etapa 1: Calcular o vetor base F (1) (consistindo em f (1) ... f (K))
Isso pode ser feito em tempo O (m 2 K) usando a abordagem de programação dinâmica da seguinte forma:
Vamos tomar A = {2,4,5} como exemplo. Para calcular F (1) = {f (1), f (2), f (3), f (4), f (5)} vamos manter uma array inicialmente vazia e anexar iterativamente A i a ela e para cada A i , encontraremos o número de maneiras de chegar a [A i-1 , a A i, ]
Portanto, para A = {2, 4, 5}
Seja T o array inicialmente vazio
Iteration 1: T = {2} n = {1,2} dp = {0,1} (Number of ways to reach n=1,2 with steps given by T)
Iteration 2: T = {2,4} n = {1,2,3,4} dp = {0,1,0,2} (Number of ways to reach n=1,2,3,4 with steps given by T)
Iteration 3: T = {2,4,5} n = {1,2,3,4,5} dp = {0,1,0,2,1} (Number of ways to reach n=1,2,3,4,5 with steps given by T)
Nota : Uma vez que alguns valores já foram calculados (1,2 para a Iteração 2, etc.), podemos evitá-los no loop
Após todas as iterações, a array dp seria: [0,1,0,2,1]
Assim, o vetor base F (1) para A = [2,4,5] é:
| 0 |
| 1 |
| 0 |
| 2 |
| 1 |
Agora que temos o vetor base F (1), o cálculo de C (array de transformação) é fácil
Etapa 2: Calcular C, a array de transformação
É uma array com os elementos A i, i + 1 = 1 e a última linha contém constantes
Agora as constantes podem ser determinadas pela presença desse elemento em A
Então, para A = [2,4,5] constantes serão c = [1,1,0,1,0] (C i = 1 se (K-i + 1) estiver presente em A, ou então 0 onde 1 <= i <= K)
Assim, a array de transformação C para A = [2,4,5] é:
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
Etapa 3: Calcular F (n)
Para calcular F (n), a seguinte fórmula é usada:
F(n) = Cn-1F(1)
Agora que temos C e F (1), podemos usar a técnica de divisão e conquista para encontrar C n-1 e, portanto, a saída desejada
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long> > matrix;
#define LOOP(i, n) for (int i = 1; i < n; i++)
// Computes A*B when A,B are square matrices of equal
// dimensions)
matrix mul(matrix A, matrix B, long long MOD = 1000000007)
{
int K = A.size();
matrix C(K, vector<long long>(K, 0));
LOOP(i, K)
LOOP(j, K)
LOOP(k, K)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
matrix power(matrix A, long long n)
{
if (n == 1)
return A;
if (n % 2 != 0) {
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1));
}
else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A);
}
return A;
}
vector<long long> initialize(vector<long long> A)
{
// Initializes the base vector F(1)
int K = A[A.size() - 1]; // Assuming A is sorted
vector<long long> F(K + 1, 0);
vector<long long> dp(K + 1);
dp[0] = 0;
dp[A[1]] = 1; // There is one and only one way to reach
// first element
F[A[1]] = 1;
for (int i = 2; i < A.size(); ++i) {
// Loop through A[i-1] to A[i] and fill the dp array
for (int j = A[i - 1] + 1; j <= A[i]; ++j) {
// dp[j] = dp[j-A[0]] + .. + dp[j-A[i-1]]
for (int k = 1; k < i; ++k) {
dp[j] += dp[j - A[k]];
}
}
// There will be one more way to reach A[i]
dp[A[i]] += 1;
F[A[i]] = dp[A[i]];
}
return F;
}
long long ways(vector<long long> A, int n)
{
int K = A[A.size() - 1]; // Assuming A is sorted
vector<long long> F = initialize(A); // O(m^2*K)
int MOD = 1000000007;
// create K*K matrix
matrix C(K + 1, vector<long long>(K + 1, 0));
/*
A matrix with (i+1)th element as 1 and last row contains
constants
[
[0 1 0 0 ... 0]
[0 0 1 0 ... 0]
[0 0 0 1 ... 0]
[. . . . ... .]
[. . . . ... .]
[c(k) c(k-1) c(k-2) ... c1]
]
*/
for (int i = 1; i < K; ++i) {
C[i][i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
for (int i = 1; i < A.size(); ++i) {
C[K][K - A[i] + 1] = 1;
}
if (n <= K)
return F[n];
// F(n) = C^(n-1)*F
C = power(C, n - 1); // O(k^3Log(n))
long long result = 0;
// result will be the first row of C^(n-1)*F
for (int i = 1; i <= K; ++i) {
result = (result + C[1][i] * F[i]) % MOD;
}
return result;
}
int main()
{
int n = 9;
vector<long long> A = {
0, 2, 4, 5
}; // 0 is just because we are using 1 based indexing
cout << "Number of ways = " << ways(A, n) << endl;
}
// This code is contributed by darshang631Número de maneiras = 5
Análise de complexidade:
Time Complexity: O( m2K + K3Logn )
where
m is the size of Array A
K is the largest element in A
n denotes the stair number (nth stair)
Space Complexity: O(K2)
Observação:
Esta abordagem é ideal quando n é muito grande para iteração
Por exemplo: Considere esta abordagem quando (1 ≤ n ≤ 10 9 ) e (1 ≤ m, k ≤ 10 2 )
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
