Titlul: Programare dinamica - Trepte Scris de: Alecs Andru din 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 ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) Titlul: Răspuns: Programare dinamica - Trepte Scris de: Profir Alexandru din 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.
|