Gabii: Pagină nouă: == Enunț == Fie mulţimea `M={1,2,..,n}` şi `P(1),P(2),...,P(n)` o permutare a ei. Elementul `x` din `M` se numeşte punct fix dacă `P(x)=x`. = Cerinţa = Se citeşte un număr natural nenul `n`. Să se afişeze, în ordine lexicografică, permutările fără puncte fixe ale mulţimii `{1,2,..,n}`. = Date de intrare = Fişierul de intrare `permpfIN.txt` conţine pe prima linie număru...

2023-12-03T21:17:55Z

Pagină nouă: == Enunț == Fie mulţimea <code>M={1,2,..,n}</code> şi <code>P(1),P(2),...,P(n)</code> o permutare a ei. Elementul <code>x</code> din <code>M</code> se numeşte punct fix dacă <code>P(x)=x</code>. = Cerinţa = Se citeşte un număr natural nenul <code>n</code>. Să se afişeze, în ordine lexicografică, permutările fără puncte fixe ale mulţimii <code>{1,2,..,n}</code>. = Date de intrare = Fişierul de intrare <code>permpfIN.txt</code> conţine pe prima linie număru...

New page

== Enunț ==
Fie mulţimea <code>M={1,2,..,n}</code> şi <code>P(1),P(2),...,P(n)</code> o permutare a ei. Elementul <code>x</code> din <code>M</code> se numeşte punct fix dacă <code>P(x)=x</code>.

= Cerinţa =
Se citeşte un număr natural nenul <code>n</code>. Să se afişeze, în ordine lexicografică, permutările fără puncte fixe ale mulţimii <code>{1,2,..,n}</code>.

= Date de intrare =
Fişierul de intrare <code>permpfIN.txt</code> conţine pe prima linie numărul <code>n</code>.

= Date de ieşire =
Fişierul de ieşire <code>permpfOUT.txt</code> va conţine pe fiecare linie elementele unei permutări, separate prin câte un spaţiu.

= Restricţii şi precizări =

* <code>0 < n < 9</code>

= Exemplul 1 =
<code>permpfIN.txt</code>
3
<code>permpfOUT.txt</code>
2 3 1
3 1 2

= Exemplul 2 =
<code>permpfIN.txt</code>
10
Consola
Valoarea lui n nu respectă restricțiile.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii_n(n):
return 0 < n < 9

def are_puncte_fixe(perm):
for i in range(len(perm)):
if perm[i] == i + 1:
return True
return False

def backtracking(perm, poz, n, output_file):
if poz == n:
if not are_puncte_fixe(perm):
output_file.write(' '.join(map(str, perm)) + '\n')
return

for i in range(1, n + 1):
if i not in perm:
perm[poz] = i
backtracking(perm, poz + 1, n, output_file)
perm[poz] = 0

def permutari_fara_puncte_fixe(n, output_file):
perm = [0] * n
backtracking(perm, 0, n, output_file)

# Citirea valorii lui n din fișierul de intrare
with open("permpfIN.txt", "r") as input_file:
line = input_file.readline().strip()
if not line:
print("Fișierul de intrare este gol sau corupt.")
else:
try:
n = int(line)
# Verificăm restricțiile asupra valorii lui n
if verifica_restrictii_n(n):
# Deschiderea fișierului de ieșire
with open("permpfOUT.txt", "w") as output_file:
# Apelăm funcția pentru generarea permutărilor fără puncte fixe
permutari_fara_puncte_fixe(n, output_file)
else:
print("Valoarea lui n nu respectă restricțiile.")
except ValueError:
print("Linia citită din fișier nu reprezintă un număr întreg valid.")

</syntaxhighlight>

0202 - PermPF - Revision history