3240 - Sequences: Difference between revisions
Pagină nouă: ==Cerința== Să se calculeze numărul de șiruri crescătoare de lungime n, cu numere de la 1 la m, în care fiecare element apare de cel mult k ori. ==Date de intrare== De la intrarea standard se citesc numerele întregi n, m și k, separate prin spațiu. ==Date de ieșire== La ieșirea standard programul va afișa numărul de șiruri descrise în enunț. ==Restricții și precizări== 0 < n < 31 0 < m < 31 0 < k < 31 ==Exemplu==: Intrare 3 4 2 Ieșire 16 ==Explicație... |
No edit summary |
||
Line 22: | Line 22: | ||
Explicație. Șirurile sunt: (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), (1,3,3), (1,3,4), (1,4,4), (2,2,3), (2,2,4), (2,3,3), (2,3,4), (2,4,4), (3,3,4), (3,4,4). | Explicație. Șirurile sunt: (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), (1,3,3), (1,3,4), (1,4,4), (2,2,3), (2,2,4), (2,3,3), (2,3,4), (2,4,4), (3,3,4), (3,4,4). | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3"> | |||
def numar_siruri(n, m, k): | def numar_siruri(n, m, k): | ||
# Funcție auxiliară pentru calculul coeficientului binomial | |||
def comb(n, r): | |||
result = 1 | |||
for i in range(r): | |||
result = (result * (n - i)) // (i + 1) | |||
return result | |||
# Funcție recursivă pentru generarea numărului de șiruri | |||
def count_sequences(current_element, current_count, current_index): | |||
if current_index == n: | |||
return 1 | |||
total_sequences = 0 | |||
for i in range(current_element, m + 1): | |||
if current_count + 1 <= k: | |||
total_sequences += count_sequences(i, current_count + 1, current_index + 1) | |||
total_sequences += count_sequences(current_element, 0, current_index + 1) | |||
return total_sequences | |||
return count_sequences(1, 0, 0) | |||
if __name__ == "__main__": | if __name__ == "__main__": | ||
# Citim datele de intrare | |||
n, m, k = map(int, input().split()) | |||
# Calculăm rezultatul și afișăm rezultatul | |||
rezultat = numar_siruri(n, m, k) | |||
print(rezultat) | |||
</syntaxhighlight> |
Revision as of 17:40, 11 January 2024
Cerința
Să se calculeze numărul de șiruri crescătoare de lungime n, cu numere de la 1 la m, în care fiecare element apare de cel mult k ori.
Date de intrare
De la intrarea standard se citesc numerele întregi n, m și k, separate prin spațiu.
Date de ieșire
La ieșirea standard programul va afișa numărul de șiruri descrise în enunț.
Restricții și precizări
0 < n < 31 0 < m < 31 0 < k < 31 ==Exemplu==: Intrare
3 4 2 Ieșire
16
Explicație
Explicație. Șirurile sunt: (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), (1,3,3), (1,3,4), (1,4,4), (2,2,3), (2,2,4), (2,3,3), (2,3,4), (2,4,4), (3,3,4), (3,4,4).
Rezolvare
<syntaxhighlight lang="python3"> def numar_siruri(n, m, k):
# Funcție auxiliară pentru calculul coeficientului binomial def comb(n, r): result = 1 for i in range(r): result = (result * (n - i)) // (i + 1) return result # Funcție recursivă pentru generarea numărului de șiruri def count_sequences(current_element, current_count, current_index): if current_index == n: return 1 total_sequences = 0 for i in range(current_element, m + 1): if current_count + 1 <= k: total_sequences += count_sequences(i, current_count + 1, current_index + 1) total_sequences += count_sequences(current_element, 0, current_index + 1) return total_sequences return count_sequences(1, 0, 0)
if __name__ == "__main__":
# Citim datele de intrare n, m, k = map(int, input().split()) # Calculăm rezultatul și afișăm rezultatul rezultat = numar_siruri(n, m, k) print(rezultat)
</syntaxhighlight>