Clasa a XI-a · Programare dinamicăRead in English

Numărul de moduri de a urca o scară în C++

În engleză: Number of ways to climb a staircase

O(n)C++1738 de linii2 exemple

Ideea

O scară are n trepte; la fiecare pas urcăm fie o treaptă, fie două. În câte moduri putem ajunge sus? Pe treapta i ajungem fie de pe treapta i - 1, fie de pe treapta i - 2, deci nr[i] = nr[i - 1] + nr[i - 2], cu nr[0] = nr[1] = 1. Calculăm valorile de jos în sus și fiecare subproblemă se rezolvă o singură dată (varianta recursivă directă ar recalcula aceleași valori de foarte multe ori). Rezultatul este un termen din șirul lui Fibonacci.

Descrierea în engleză

A staircase has n steps; at every move we climb either one step or two. In how many ways can we reach the top? Step i is reached either from step i - 1 or from step i - 2, so nr[i] = nr[i - 1] + nr[i - 2], with nr[0] = nr[1] = 1. We compute the values from the bottom up and every subproblem is solved only once (the direct recursive version would recompute the same values very many times). The result is a term of the Fibonacci sequence.

Complexitate
O(n) timp, O(n) memorie
Clasa
Clasa a XI-a (Grade 11)

Exemple

Exemplul 1

Intrare

4

Ieșire așteptată

5
Exemplul 2

Intrare

10

Ieșire așteptată

89

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

urcarea-scarii.cpp
/*
 * Titlu: Numărul de moduri de a urca o scară
 * Clasa: 11
 * Capitol: Programare dinamică
 * Descriere: O scară are n trepte; la fiecare pas urcăm fie o treaptă, fie două. În câte
 *            moduri putem ajunge sus? Pe treapta i ajungem fie de pe treapta i - 1, fie de
 *            pe treapta i - 2, deci nr[i] = nr[i - 1] + nr[i - 2], cu nr[0] = nr[1] = 1.
 *            Calculăm valorile de jos în sus și fiecare subproblemă se rezolvă o singură
 *            dată (varianta recursivă directă ar recalcula aceleași valori de foarte multe
 *            ori). Rezultatul este un termen din șirul lui Fibonacci.
 * Complexitate: O(n) timp, O(n) memorie
 *
 * Exemplu
 * Intrare: 4
 * Ieșire: 5
 *
 * Exemplu
 * Intrare: 10
 * Ieșire: 89
 */
#include <iostream>
using namespace std;

int main()
{
    int n;
    long long nr[100];
    cin >> n;
    nr[0] = 1;
    nr[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        nr[i] = nr[i - 1] + nr[i - 2];
    }
    cout << nr[n] << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.