Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Programare dinamica - Trepte  (Citit de 6687 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ALEx6430
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« : Martie 14, 2018, 13:42:25 »

Cerința
O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial este pe treapta 1)

Date de intrare
Programul citește de la tastatură numerele n și k.

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

Restricții și precizări
1 < n ≤ 100.000
1 ≤ k ≤ n - 1
deoarece numărul va fi prea mare sa va afișa modulo 9001.
Exemplul 1:
Intrare

2 2
Ieșire

1
Explicație
Există o soluție, aceea când sare direct pe treapta 2.

Exemplul 2:
Intrare

4 2
Ieșire

3
Explicație
Prima: 1 -> 2 -> 3 -> 4
A doua: 1 -> 2 -> 4
A treia: 1 -> 3 -> 4

ma chinui de 3 ore sa gasesc o relatie de recurenta  Brick wall Brick wall Brick wall Brick wall Brick wall Brick wall Brick wall Brick wall Brick wall Brick wall Brick wall
Memorat
coolback
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #1 : Februarie 28, 2019, 16:53:07 »

Ma gandesc ca initial porneste de pe treapta unu, dar in algoritmul tau poti incepe initial de pe treapta unu si sa numeri scarile urcate. Dupa poti incepe de pe treapta 2 si sa numeri scarile urcate si tot asa.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines