1942 - Ciclu Hamiltonian

Cerința

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

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

Date de ieșire

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

Restricții și precizări

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

Exemplul 1:

Intrare

3

Ieșire

1

Explicație

Un graf complet cu 3 noduri are un ciclu Hamiltonian.

Exemplul 2:

Intrare

2

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare

<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>