0895 – PermutarePF

Cerinţă

Se numește permutare a unei mulțimi o aranjare a elementelor mulțimii în altă ordine. De exemplu, permutările mulțimii {1,2,3} sunt: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

Fie (p1, p2, ..., pn) o permutare a mulțimii {1,2,...,n}. Se numește punct fix al permutării o valoare k din mulțime cu proprietatea că pk = k.

Scrieţi definiția completă a subprogramulupermutare care are 2 parametri: sir, prin care primeşte un tablou unidimensional cu maximum 100 de numere naturale mai mici decât 1000 și n, numărul efectiv de elemente ale tabloului.

Subprogramul verifică dacă elementele vectorului sir reprezintă o permutare fără puncte fixe a mulțimii {1,2,...,n} și returnează valoarea 1 în caz afirmativ, respectiv 0 în caz negativ.

Date de intrare

Programul va citi de la tastatură valoarean, apoi n numere întregi reprezentând elementele șirului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte!", apoi se va afișa valoare 1 dacă șirul reprezintă o permutare fără puncte fixe, și 0 în caz contrar. În cazul în care datele nu respectă restricțiile, se va afișa mesajul "Datele introduse nu sunt corecte!".

Restricţii şi precizări

1 <= n <= 100
valorile elementelor șirului vor fi < 1.000

Exemple

Exemplul 1

Intrare: Introduceti numarul de elemente a sirului: 4; Introduceti 4 numere separate prin spatiu:2 3 1 4
Ieșire: Datele introduse sunt corecte!; 0

Exemplul 2

Intrare: Introduceti numarul de elemente a sirului: 6; Introduceti 6 numere separate prin spatiu:2 3 1 6 4 5
Ieșire: Datele introduse sunt corecte!; 1

Exemplul 3

Intrare: Introduceti numarul de elemente a sirului: 103
Ieșire: Datele introduse sunt incorecte!

Rezolvare

<syntaxhighlight lang="python" line="1"> def is_integer(value):

   return value.isdigit()

def verificare_nr_elemente(n):

   if is_integer(n):
       if 1 <= int(n) <= 100:
           return n
       else:
           print("Datele introduse sunt incorecte!")
           exit()
   else:
       print("Datele introduse sunt incorecte!")
       exit()

def verificare_vector(n, vector):

   if len(vector) != int(n):
       print("Datele introduse sunt incorecte!")
       exit()
   else:
       for i in vector:
           if is_integer(i):
               if int(i) < 1000:
                   continue
               else:
                   print("Datele introduse sunt incorecte!")
                   exit()
           else:
               print("Datele introduse sunt incorecte!")
               exit()

def permutare(sir, n):

   for i in range(int(n)):
       if sir[i] == i+1:
           return 0
   return 1

def det_puncte_fixe(sir):

   if permutare(sir, n) == 1:
       print("1")
   else:
       print("0")

if __name__ == '__main__':

   n = input("Introduceti numarul de elemente a sirului: ")
   verificare_nr_elemente(n)
   elem = input(f"Introduceti {n} numere separate prin spatiu:").split()
   verificare_vector(n, elem)
   lst_int = list(map(int, elem))
   print("Datele introduse sunt corecte!")
   det_puncte_fixe(lst_int)

</syntaxhighlight>

Explicație rezolvare

Acest program primește de la utilizator un număr n reprezentând numărul de elemente ale vectorului și apoi primește un vector unidimensional de lungime n cu numere întregi prin intermediul funcției input(). Programul verifică dacă n este un număr natural cuprins între 1 și 100 și dacă elementele vectorului sunt numere întregi mai mici decât 1000. Aceste verificări sunt efectuate de funcțiile verificare_nr_elemente() și verificare_vector(), care ies din program prin intermediul funcției exit() în cazul în care datele introduse sunt incorecte.

Programul utilizează apoi o funcție permutare() pentru a determina dacă vectorul primit reprezintă o permutare fără puncte fixe a mulțimii {1,2,...,n}. Funcția parcurge vectorul și verifică dacă există un element al vectorului care se află pe aceeași poziție cu valoarea sa (adică este un punct fix). Dacă se găsește cel puțin un punct fix, funcția returnează valoarea 0, altfel returnează valoarea 1.

În cele din urmă, programul utilizează funcția det_puncte_fixe() pentru a determina dacă vectorul primit reprezintă o permutare fără puncte fixe și afișează valoarea 1 în caz afirmativ și valoarea 0 în caz negativ.

Datele introduse sunt considerate corecte dacă toate verificările sunt trecute fără probleme și programul ajunge la afișarea valorii 1 sau 0.