Zmicala Narcis: Pagină nouă: == Cerința == Marian a fost foarte interesat de metoda divide et impera și a primit de la profesorul său o problemă: se dă o matrice de dimensiune 2^n și ea trebuie parcursă după o anumită regulă bazată pe divide et impera. Pe baza a trei exemple, el trebuie să descopere regula și s-o aplice . Din păcate, acesta nu reusește și vă cere ajutorul. Vrea o rezolvare foarte eficienta atât din punct de vedere al timpului de execuție cât și a limitei de memorie....

2024-01-02T18:24:22Z

Pagină nouă: == Cerința == Marian a fost foarte interesat de metoda divide et impera și a primit de la profesorul său o problemă: se dă o matrice de dimensiune 2^n și ea trebuie parcursă după o anumită regulă bazată pe divide et impera. Pe baza a trei exemple, el trebuie să descopere regula și s-o aplice . Din păcate, acesta nu reusește și vă cere ajutorul. Vrea o rezolvare foarte eficienta atât din punct de vedere al timpului de execuție cât și a limitei de memorie....

New page

== Cerința ==
Marian a fost foarte interesat de metoda divide et impera și a primit de la profesorul său o problemă: se dă o matrice de dimensiune 2^n și ea trebuie parcursă după o anumită regulă bazată pe divide et impera. Pe baza a trei exemple, el trebuie să descopere regula și s-o aplice . Din păcate, acesta nu reusește și vă cere ajutorul. Vrea o rezolvare foarte eficienta atât din punct de vedere al timpului de execuție cât și a limitei de memorie.
== Date de intrare ==
Fișierul de intrare '''matrice_div_et_impin.txt''' conține pe prima linie numărul '''n''', iar pe celelalte '''2^n''' linii câte '''2^n''' numere naturale nenule separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''matrice_div_et_impout.txt''' va conține o linie cu cele '''2^n*2^n''' numere ale matricei , parcurse după respectiva regulă.
== Restricții și precizări ==
* '''0 ≤ n ≤ 9'''
* numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000.000'''
== Exemplul 1 ==
; matrice_div_et_impin.txt
: 1
: 1 2
: 3 4
; matrice_div_et_impout.txt
: Datele introduse corespund restricțiilor impuse.
: 1 4 2 3
== Exemplul 2 ==
; matrice_div_et_impin.txt
: 2
: 15 12 13 14
: 36 56 34 58
: 98 80 79 11
: 10 43 47 50
; matrice_div_et_impout.txt
: Datele introduse corespund restricțiilor impuse.
: 15 56 12 36 79 50 11 47 13 58 14 34 98 43 80 10
== Exemplul 3 ==
; matrice_div_et_impin.txt
: 3
: 1 2 3 4 5 6 7 8
: 9 10 11 12 13 14 15 16
: 17 18 19 20 21 22 23 24
: 25 26 27 28 29 30 31 32
: 33 34 35 36 37 38 39 40
: 41 42 43 44 45 46 47 48
: 49 50 51 52 53 54 55 56
: 57 58 59 60 61 62 63 64
; matrice_div_et_impout.txt
: Datele introduse corespund restricțiilor impuse.
: 1 10 2 9 19 28 20 27 3 12 4 11 17 26 18 25 37 46 38 45 55 64 56 63 39 48 40 47 53 62 54 61 5 14 6 13 23 32 24 31 7 16 8 15 21 30 22 29 33 42 34 41 51 60 52 59 35 44 36 43 49 58 50 57
== Exemplul 4 ==
; matrice_div_et_impin.txt
: 2
: 1 2 3 4
: 5 6 7 8
: 9 10 11 12
: 13 14 15 1000000001
; matrice_div_et_impout.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 1229 - Matrice Div Et Imp
def validare(dimensiune_n, lista_matrice1): # functia de validare a datelor de intrare
if dimensiune_n < 0 or dimensiune_n > 9:
raise ValueError

for linie in lista_matrice1:
for numar in linie:
if numar < 1 or numar > 1000000000:
raise ValueError

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

def parcurgere(dimensiune_n, lista_matrice1, x, y): # functia de rezolvare
if dimensiune_n == 0:
return [lista_matrice1[x][y]]
else:
dimensiune_n -= 1
dim = 2 ** dimensiune_n
return (parcurgere(dimensiune_n, lista_matrice1, x, y) +
parcurgere(dimensiune_n, lista_matrice1, x + dim, y + dim) +
parcurgere(dimensiune_n, lista_matrice1, x, y + dim) +
parcurgere(dimensiune_n, lista_matrice1, x + dim, y))

if __name__ == '__main__':
fisier_intrare = open("matrice_div_et_impin.txt", "r") # declararea fisierelor
fisier_iesire = open("matrice_div_et_impout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
dim_n = int(fisier_intrare.readline())
lista_matrice = [list(map(int, fisier_intrare.readline().split())) for _ in range(2**dim_n)]

validare(dim_n, lista_matrice) # apelul functiei de validare
rezultat = parcurgere(dim_n, lista_matrice, 0, 0) # apelul functiei de rezolvare
fisier_iesire.write(' '.join(map(str, rezultat)) + '\n')

except ValueError:
fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

1229 - Matrice Div Et Imp - Revision history