Editing 1229 - Matrice Div Et Imp

== 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>