3943 - Cerc5: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: == 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. == Date de intrare == Programul citește de la tastatură un șir de n numere naturale. == Date de ieșire == Pe ecran se vor afișa toate permutările circulare ale șirului, câte una pe linie. == Restricții și precizări == *1 ⩽ '''n''' ⩽ 10 * Numerele din șir s...)
 
Fără descriere a modificării
 
Linia 1: Linia 1:
== Cerința ==
== 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 ==
== 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 ==
== 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 ==
== Restricții și precizări ==
*1 ⩽ '''n''' ⩽ 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 ==
== Exemplu 1 ==
;Intrare
;Intrare
1 2 3
32


;Iesire
;Iesire
1 2 3<br>
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
2 3 1<br>
 
3 1 2




== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python" line>
<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():
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__":
if __name__ == "__main__":

Versiunea curentă din 2 iunie 2024 23:52

Cerința

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ă numărul n.

Date de ieșire

Programul va afișa pe ecran cele n numere cerute, separate prin câte un spațiu.

Restricții și precizări

  • 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

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

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()
Adus de la „http://wiki.universitas.ro/index.php?title=3943_-_Cerc5&oldid=9908”