1942 - Ciclu Hamiltonian

From Bitnami MediaWiki
Revision as of 18:59, 6 January 2024 by Rus Marius (talk | contribs) (Pagină nouă: = Cerința = Dându-se un număr natural <code>N</code>, aflaţi numărul de cicluri Hamiltoniene dintr-un graf complet cu <code>N</code> noduri. = Date de intrare = Programul citește de la tastatură numărul <code>N</code>. = Date de ieșire = Programul va afișa pe ecran numărul cerut. = Restricții și precizări = * <code>3 ≤ N ≤ 100</code> * două cicluri diferă dacă au cel puțin o muchie diferită = Exemplul 1: = Intrare 3 Ieșire 1 === Explicație ===...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Cerința[edit | edit source]

Dându-se un număr natural N, aflaţi numărul de cicluri Hamiltoniene dintr-un graf complet cu N noduri.

Date de intrare[edit | edit source]

Programul citește de la tastatură numărul N.

Date de ieșire[edit | edit source]

Programul va afișa pe ecran numărul cerut.

Restricții și precizări[edit | edit source]

  • 3 ≤ N ≤ 100
  • două cicluri diferă dacă au cel puțin o muchie diferită

Exemplul 1:[edit | edit source]

Intrare

3

Ieșire

1

Explicație[edit | edit source]

Un graf complet cu 3 noduri are un ciclu Hamiltonian.

Exemplul 2:[edit | edit source]

Intrare

2

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def check_restrictions(n):

   if n < 3 or n >= 100:
       print("Datele nu corespund restrictiilor impuse")
       return False
   return True

def inmultire(x, k):

   t = 0
   for i in range(1, x[0] + 1):
       c = x[i] * k + t
       x[i] = c % 10
       t = c // 10
   while t:
       x[0] += 1
       x[x[0]] = t % 10
       t //= 10

def calculate_factorial(n):

   if not check_restrictions(n):
       return
   x = [0] * 1001
   x[0], x[1] = 1, 1
   for i in range(3, n):
       inmultire(x, i)
   for i in range(x[0], 0, -1):
       print(x[i], end=)

def main():

   n = int(input(""))
   calculate_factorial(n)

if __name__ == "__main__":

   main()

</syntaxhighlight>