1991 - Trepte 2: Difference between revisions

From Bitnami MediaWiki
Mraa (talk | contribs)
Pagină nouă: ==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 ≤...
 
Mraa (talk | contribs)
No edit summary
Line 34: Line 34:
A treia: 1 -> 3 -> 4
A treia: 1 -> 3 -> 4
==Rezolvare==
==Rezolvare==
<syntaxhighlight lang="python3">
def numar_moduri_urcare_trepte(n, k):
def numar_moduri_urcare_trepte(n, k):
    mod = 9001


    # Inițializare vector dp
  mod = 9001
    dp = [0] * (n + 1)
  # Inițializare vector dp
    dp[1] = 1
  dp = [0] * (n + 1)
  dp[1] = 1
  # Calcul numărul de moduri
  for i in range(1, n + 1):
      for j in range(1, k + 1):
          if i + j <= n:
              dp[i + j] = (dp[i + j] + dp[i]) % mod
  return dp[n]
Citire date de intrare


    # Calcul numărul de moduri
n, k = map(int, input().split())
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if i + j <= n:
                dp[i + j] = (dp[i + j] + dp[i]) % mod


    return dp[n]
Calcul și afișare rezultat
 
# Citire date de intrare
n, k = map(int, input().split())


# Calcul și afișare rezultat
result = numar_moduri_urcare_trepte(n, k) print(result)
result = numar_moduri_urcare_trepte(n, k)
</syntaxhighlight>
print(result)

Revision as of 17:25, 11 January 2024

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

Rezolvare

<syntaxhighlight lang="python3"> def numar_moduri_urcare_trepte(n, k):

  mod = 9001
  # Inițializare vector dp
  dp = [0] * (n + 1)
  dp[1] = 1
  # Calcul numărul de moduri
  for i in range(1, n + 1):
      for j in range(1, k + 1):
          if i + j <= n:
              dp[i + j] = (dp[i + j] + dp[i]) % mod
  return dp[n]

Citire date de intrare

n, k = map(int, input().split())

Calcul și afișare rezultat

result = numar_moduri_urcare_trepte(n, k) print(result) </syntaxhighlight>