3240 - Sequences: Difference between revisions

From Bitnami MediaWiki
Mraa (talk | contribs)
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...
 
Mraa (talk | contribs)
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
  # Funcție auxiliară pentru calculul coeficientului binomial
    def count_sequences(current_element, current_count, current_index):
  def comb(n, r):
        if current_index == n:
      result = 1
            return 1
      for i in range(r):
 
          result = (result * (n - i)) // (i + 1)
        total_sequences = 0
      return result
        for i in range(current_element, m + 1):
  # Funcție recursivă pentru generarea numărului de șiruri
            if current_count + 1 <= k:
  def count_sequences(current_element, current_count, current_index):
                total_sequences += count_sequences(i, current_count + 1, current_index + 1)
      if current_index == n:
 
          return 1
        total_sequences += count_sequences(current_element, 0, current_index + 1)
      total_sequences = 0
 
      for i in range(current_element, m + 1):
        return total_sequences
          if current_count + 1 <= k:
 
              total_sequences += count_sequences(i, current_count + 1, current_index + 1)
    return count_sequences(1, 0, 0)
      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
  # Citim datele de intrare
    rezultat = numar_siruri(n, m, k)
  n, m, k = map(int, input().split())
    print(rezultat)
  # Calculăm rezultatul și afișăm rezultatul
python siruri_crescatoare.py
  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>