1942 - Ciclu Hamiltonian
De la Universitas MediaWiki
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
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()