3943 - Cerc5: Difference between revisions

Latest revision as of 23:52, 2 June 2024

Cerința[edit | edit source]

Se dă numărul natural n. Determinati o modalitate de așezare a numerelor din mulțimea 1,2,…,n

pe un cerc astfel încât suma a oricare două nume învecinate să nu fie pătrat perfect.

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 cele n numere cerute, separate prin câte un spațiu.

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

1 ≤ n ≤ 35
dacă există mai multe modalități de aranjare a numerelor astfel încât să fie îndeplinită condiția, se poate afișa oricare;
dacă nu există nicio modalitate de aranjare se va afișa mesajul nu exista

Exemplu 1[edit | edit source]

Intrare

32

Iesire

1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line> import math

Verifică dacă un număr este pătrat perfect

def este_patrat_perfect(x):

   return int(math.isqrt(x)) ** 2 == x

Funcție de backtracking pentru a găsi o soluție validă

def backtrack(cerc, vizitat, n):

   if len(cerc) == n:
       # Verifică dacă primul și ultimul element formează un pătrat perfect
       return este_patrat_perfect(cerc[-1] + cerc[0])

   for i in range(1, n + 1):
       if not vizitat[i]:
           if not cerc or este_patrat_perfect(cerc[-1] + i):
               cerc.append(i)
               vizitat[i] = True
               if backtrack(cerc, vizitat, n):
                   return True
               cerc.pop()
               vizitat[i] = False
   return False

Funcție pentru a găsi aranjarea corectă

def gaseste_aranjare(n):

   cerc = []
   vizitat = [False] * (n + 1)
   if backtrack(cerc, vizitat, n):
       return cerc
   else:
       return "nu exista"

Funcția principală

def main():

   n = int(input().strip())
   rezultat = gaseste_aranjare(n)
   if isinstance(rezultat, list):
       print(" ".join(map(str, rezultat)))
   else:
       print(rezultat)

if __name__ == "__main__":

   main()

if __name__ == "__main__":

   main()

</syntaxhighlight>

@@ Line 1: / Line 1: @@
 == Cerința ==
-Să se genereze toate permutările circulare ale unui șir de numere naturale, unde permutările circulare sunt permutări în care primul și ultimul element sunt considerate consecutive.
+Se dă numărul natural n. Determinati o modalitate de așezare a numerelor din mulțimea 1,2,…,n
+ pe un cerc astfel încât suma a oricare două nume învecinate să nu fie pătrat perfect.
 == Date de intrare ==
-Programul citește de la tastatură un șir de n numere naturale.
+Programul citește de la tastatură numărul n.
 == Date de ieșire ==
-Pe ecran se vor afișa toate permutările circulare ale șirului, câte una pe linie.
+Programul va afișa pe ecran cele n numere cerute, separate prin câte un spațiu.
 == Restricții și precizări ==
-*1 &les; '''n''' &les; 10
+*1 ≤ n ≤ 35
-* Numerele din șir sunt naturale și distincte
+*dacă există mai multe modalități de aranjare a numerelor astfel încât să fie îndeplinită condiția, se poate afișa oricare;
+*dacă nu există nicio modalitate de aranjare se va afișa mesajul nu exista
 == Exemplu 1 ==
 ;Intrare
-2 3
 ;Iesire
-2 3<br>
+8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15
-3 1<br>
-1 2
 == Rezolvare ==
 <syntaxhighlight lang="python" line>
-def citeste_date():
+import math
-     try:
-        sir = list(map(int, input("Introduceți șirul de numere naturale, separate prin spațiu: ").split()))
-        return sir
+# Verifică dacă un număr este pătrat perfect
-    except ValueError:
+def este_patrat_perfect(x):
-        return None
+     return int(math.isqrt(x)) ** 2 == x
-def valideaza_date(sir):
-    if not (1 <= len(sir) <= 10):
-        return False
-    if not all(isinstance(num, int) and num >= 0 for num in sir):
-        return False
-    if len(sir) != len(set(sir)):
-        return False
-    return True
-def permutari_circulare(sir):
+# Funcție de backtracking pentru a găsi o soluție validă
-     n = len(sir)
+def backtrack(cerc, vizitat, n):
-    permutari = []
+     if len(cerc) == n:
+        # Verifică dacă primul și ultimul element formează un pătrat perfect
+        return este_patrat_perfect(cerc[-1] + cerc[0])
-     def backtrack(current_perm, used):
+     for i in range(1, n + 1):
-         if len(current_perm) == n:
+         if not vizitat[i]:
-             if (current_perm[0] == sir[0]):
+             if not cerc or este_patrat_perfect(cerc[-1] + i):
-                 permutari.append(current_perm[:])
+                cerc.append(i)
-            return
+                vizitat[i] = True
+                if backtrack(cerc, vizitat, n):
+                    return True
+                 cerc.pop()
+                vizitat[i] = False
+    return False
-        for i in range(n):
-            if not used[i]:
-                used[i] = True
-                current_perm.append(sir[i])
-                backtrack(current_perm, used)
-                current_perm.pop()
-                used[i] = False
-     used = [False] * n
+# Funcție pentru a găsi aranjarea corectă
-     backtrack([], used)
+def gaseste_aranjare(n):
+    cerc = []
+     vizitat = [False] * (n + 1)
+     if backtrack(cerc, vizitat, n):
+        return cerc
+    else:
+        return "nu exista"
-    return permutari
+# Funcția principală
 def main():
-     sir = citeste_date()
+     n = int(input().strip())
+     rezultat = gaseste_aranjare(n)
-     if sir is None or not valideaza_date(sir):
+     if isinstance(rezultat, list):
-         print("Datele de intrare nu corespund restricțiilor impuse.")
+         print(" ".join(map(str, rezultat)))
-        return
+     else:
+        print(rezultat)
-    print("Datele de intrare corespund restricțiilor impuse.")
-    permutari = permutari_circulare(sir)
+if __name__ == "__main__":
-    for perm in permutari:
+    main()
-        print(" ".join(map(str, perm)))
 if __name__ == "__main__":