1798 - Trepte

Sursa: [1]

Cerinţa

O persoana are de urcat n trepte. Ştiind că poate păşi pe treapta urmatoare sau poate sări peste o treapta, aflaţi in câte moduri poate urca cele n trepte.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul c, reprezentând numărul de moduri in care poate urca cele n trepte.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează in câte moduri poate urca cele n trepte

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

• 1 ≤ n ≤ 30

Exemplul 1

Datele de intrare

Introduceti numarul de trepte:

2

Datele sunt introduse corect.

Datele de ieșire

Numarul de moduri pentru a urca cele", n, "trepte este:

2

Rezolvare

<syntaxhighlight lang="python" line>

1. 1798

mem = {0: 1, 1: 1, 2: 2} # inițializăm dicționarul cu valorile pentru n = 0, 1, 2

def urcare_trepte(n):

   if n in mem:
       return mem[n]  # dacă rezultatul pentru n a fost deja calculat, îl returnăm din memorie
   else:
       mem[n] = urcare_trepte(n-1) + urcare_trepte(n-2)  # calculăm numărul de moduri pentru n și îl memorăm
       return mem[n]

def validate_input(n):

   if n < 1 or n > 30:
       return False
   else:
       return True

if __name__ == '__main__':

   n = int(input("Introduceti numarul de trepte: "))
   if not validate_input(n):
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       print("Numarul de moduri pentru a urca cele", n, "trepte este:", urcare_trepte(n))

</syntaxhighlight>

Explicatie cod:

Acest cod calculează numărul de moduri în care se pot urca N trepte, folosind recursivitate și memorizare a rezultatelor anterioare.

În primul rând, se inițializează un dicționar cu valorile pentru n = 0, 1 și 2, pentru a putea folosi aceste valori în calculul recursiv.

Funcția urcare_trepte primește ca argument numărul de trepte, n. Dacă rezultatul pentru n a fost deja calculat și stocat în memorie, se returnează direct acel rezultat. În caz contrar, se calculează recursiv numărul de moduri pentru a urca cele n trepte, adunând numerele de moduri pentru a urca cele n-1 și n-2 trepte. Rezultatul este memorat în dicționar și apoi returnat.

Funcția validate_input verifică dacă numărul de trepte introdus este valid, respectiv dacă este un număr între 1 și 30.

În blocul if name == 'main' se citește numărul de trepte introdus de utilizator. Dacă acesta nu este valid, se afișează un mesaj corespunzător. În caz contrar, se afișează numărul de moduri în care se pot urca cele n trepte, calculat cu ajutorul funcției urcare_trepte.