Zmicala Narcis at 18:55, 28 December 2023

2023-12-28T18:55:20Z

@@ Line 67: / Line 67: @@
      fisier_intrare = open("permutarepowin.txt", "r")
      fisier_iesire = open("permutarepowout.txt", "w")
 </syntaxhighlight>

Zmicala Narcis: Pagină nouă: == Cerința == Fie '''∆''' o permutare de gradul '''n'''. Se cere să se calculeze perioada principală a funcției '''f(x)''' = '''∆^x'''. == Date de intrare == Fișierul de intrare '''permutarepowin.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale distincte separate prin spații, reprezentând valorile permutării '''∆'''. == Date de ieșire == Fișierul de ieșire '''permutarepowout.txt''' va conține pe prima linie număru...

2023-12-28T18:54:01Z

Pagină nouă: == Cerința == Fie '''∆''' o permutare de gradul '''n'''. Se cere să se calculeze perioada principală a funcției '''f(x)''' = '''∆^x'''. == Date de intrare == Fișierul de intrare '''permutarepowin.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale distincte separate prin spații, reprezentând valorile permutării '''∆'''. == Date de ieșire == Fișierul de ieșire '''permutarepowout.txt''' va conține pe prima linie număru...

New page

== Cerința ==
Fie '''∆''' o permutare de gradul '''n'''. Se cere să se calculeze perioada principală a funcției '''f(x)''' = '''∆^x'''.
== Date de intrare ==
Fișierul de intrare '''permutarepowin.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale distincte separate prin spații, reprezentând valorile permutării '''∆'''.
== Date de ieșire ==
Fișierul de ieșire '''permutarepowout.txt''' va conține pe prima linie numărul '''P''', reprezentând perioada principală a funcției '''f'''.
== Restricții și precizări ==
* '''1 ≤ n ≤ 1.000.000'''
* Numerele de pe a doua linie vor aparține intervalului '''[1,n]'''
* Despre permutări
== Exemplul 1 ==
; permutarepowin.txt
: 4
: 3 4 2 1
; permutarepowout.txt
: Datele introduse corespund restricțiilor impuse.
: 4
== Explicație ==
Se observă că '''∆''' = '''∆^5''', deci perioada principală este '''4'''.
== Exemplul 2 ==
; permutarepowin.txt
: 5
: 1 2 3 4 6
; permutarepowout.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 2597 - PermutarePow
import math

def validare(permutare_intrare): # functia de validare a datelor de intrare
n_intrare = len(permutare_intrare)
if n_intrare < 1 or n_intrare > 1000000:
raise ValueError

for numar in permutare_intrare:
if numar < 1 or numar > n_intrare: # fiecare numar trebuie sa fie intre 1 si n
raise ValueError

fisier_iesire.write("Datele introduse corespund restrictiilor impuse.\n")

def perioada_principala(permutare_intrare):
n_intrare = len(permutare_intrare)
vizitat = [False] * n_intrare
cicluri = []

for i in range(n_intrare):
if not vizitat[i]:
ciclu = 0
j = i
while not vizitat[j]:
vizitat[j] = True
ciclu += 1
j = permutare_intrare[j] - 1
cicluri.append(ciclu)

p_curent_local = cicluri[0]
for i in range(1, len(cicluri)):
p_curent_local = (p_curent_local * cicluri[i]) // math.gcd(p_curent_local, cicluri[i])

return p_curent_local

if __name__ == '__main__':
fisier_intrare = open("permutarepowin.txt", "r")
fisier_iesire = open("permutarepowout.txt", "w")

</syntaxhighlight>

2597 - PermutarePow - Revision history

Zmicala Narcis at 18:55, 28 December 2023