Lesson 9
Dwuwymiarowe listy (tablice)
1. Listy zagnieżdżone: przetwarzanie i drukowanie
W rzeczywistości Często zadania muszą przechowywać prostokątną tabelę danych. [powiedz więcej o tym!] Takie tabele nazywane są macierzami lub tablicami dwuwymiarowymi. W Pythonie każda tabela może być reprezentowana jako lista list (lista, gdzie każdy element jest z kolei listą). Na przykład tutaj jest program, który tworzy tabelę numeryczną z dwoma wierszami i trzema kolumnami, a następnie wykonuje kilka manipulacji z nią:a = [[1, 2, 3], [4, 5, 6]] print(a[0]) print(a[1]) b = a[0] print(b) print(a[0][2]) a[0][1] = 7 print(a) print(b) b[2] = 9 print(a[0]) print(b)
Pierwszym elementem a tutaj - a[0] - jest lista liczb [1, 2, 3] . Pierwszym elementem tej nowej listy jest a[0][0] == 1 ; ponadto, a[0][1] == 2 , a[0][2] == 3 , a[1][0] == 4 , a[1][1] == 5 , a[1][2] == 6 .
Aby przetworzyć dwuwymiarową tablicę, zwykle używasz zagnieżdżonych pętli. Pierwsza pętla przechodzi przez numer wiersza, druga pętla przechodzi przez elementy wewnątrz rzędu. Na przykład w ten sposób wyświetlasz dwuwymiarową listę numeryczną na ekranie, po linii, oddzielając liczby spacjami:
a = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
for i in range(len(a)):
for j in range(len(a[i])):
print(a[i][j], end=' ')
print()
Już próbowaliśmy wyjaśnić, że zmienna for-loop w Pythonie może iterować nie tylko przez range() , ale ogólnie przez wszystkie elementy dowolnej sekwencji. Sekwencje w Pythonie to listy i łańcuchy znaków (oraz kilka innych obiektów, których jeszcze nie poznaliśmy). Zobacz, jak możesz wydrukować dwuwymiarową tablicę, używając tej przydatnej funkcji pętli for :
a = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
for row in a:
for elem in row:
print(elem, end=' ')
print()
Oczywiście, aby wyprowadzić pojedynczą linię, możesz użyć metody join() :
for row in a:
print(' '.join([str(elem) for elem in row]))
W ten sposób można użyć 2 zagnieżdżonych pętli do obliczenia sumy wszystkich liczb z 2-wymiarowej listy:
a = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
s = 0
for i in range(len(a)):
for j in range(len(a[i])):
s += a[i][j]
print(s)
Lub to samo z iterowaniem elementów, a nie zmiennymi i i j :
a = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
s = 0
for row in a:
for elem in row:
s += elem
print(s)
2. Listy zagnieżdżone: tworzenie
Załóżmy, że podano dwie liczby: liczbę wierszy n oraz liczbę kolumn m . Musisz utworzyć listę o rozmiarze n × m , wypełnioną, powiedzmy, zerami.
Oczywiste rozwiązanie wydaje się błędne:
a = [[0] * m] * n
Można to łatwo dostrzec, jeśli ustawisz wartość a[0][0] na 5 , a następnie wydrukujesz wartość a[1][0] - będzie to równe 5. Przyczyną jest, [0] * m zwraca tylko odwołanie do listy m zer, ale nie do listy. Kolejne powtarzanie tego elementu tworzy listę n elementów, które odnoszą się do tej samej listy (tak samo jak operacja b = a dla list nie tworzy nowej listy), więc wszystkie wiersze na liście wynikowej są w rzeczywistości takie same strunowy.
Za pomocą naszego wizualizatora śledź identyfikator list. Jeśli dwie listy mają ten sam numer identyfikacyjny, w rzeczywistości jest to ta sama lista w pamięci.
n = 3 m = 4 a = [[0] * m] * n a[0][0] = 5 print(a[1][0])
W związku z tym nie można utworzyć dwuwymiarowej listy po prostu przez powtarzanie ciągu znaków. Co robić?..
Możliwy sposób: można utworzyć listę n elementów (powiedzmy, z n zer), a następnie dokonać każdy z elementów linkiem do innego jednowymiarowej listy m elementów:
n = 3
m = 4
a = [0] * n
for i in range(n):
a[i] = [0] * m
Inny (ale podobny) sposób: utwórz pustą listę, a następnie append do niej nowy element n razy (ten element powinien być listą długości m ):
n = 3
m = 4
a = []
for i in range(n):
a.append([0] * m)
Ale najłatwiej jest użyć generatora, tworząc listę n elementów, z których każda jest listą m zer:
n = 3 m = 4 a = [[0] * m for i in range(n)]
W tym przypadku każdy element jest tworzony niezależnie od innych. Lista [0] * m jest n razy oznaczona jako nowa i nie występuje kopiowanie odniesień.
3. Jak wprowadzić tablicę dwuwymiarową?
Powiedzmy, program przyjmuje wejściową tablicę dwuwymiarową w postaci n wierszy, z których każdy zawiera m liczb oddzielonych spacjami. Jak zmusić program do czytania? Przykład tego, jak możesz to zrobić:
# pierwsza linia danych wejściowych to liczba wierszy tablicy
n = int(input())
a = []
for i in range(n):
a.append([int(j) for j in input().split()])
Lub bez użycia skomplikowanych połączeń zagnieżdżonych:
# pierwsza linia danych wejściowych to liczba wierszy tablicy
n = int(input())
a = []
for i in range(n):
row = input().split()
for i in range(len(row)):
row[i] = int(row[i])
a.append(row)
Możesz zrobić to samo z generatorami:
# pierwsza linia danych wejściowych to liczba wierszy tablicy n = int(input()) a = [[int(j) for j in input().split()] for i in range(n)]
4. Przetwarzanie dwuwymiarowej tablicy: przykład
Załóżmy, że masz tablicę kwadratową (tablicę zawierającą n wierszy i n kolumn). I przypuśćmy, że musisz ustawić elementy głównej przekątnej równe 1 (czyli te elementy a[i][j] dla których i==j ), aby ustawić elementy powyżej tej przekątnej równej 0 i ustawić elementy poniżej tej przekątnej równej 2. Oznacza to, że musisz wytworzyć taką tablicę (przykład dla n==4 ):
1 0 0 0 2 1 0 0 2 2 1 0 2 2 2 1(W tym przypadku możesz zrobić to ręcznie, ustawiając
a[0][0] = 1 , a[0][1] = 0 i tak dalej, ale nie zrobisz tego ręcznie dla tablic 100 wierszy i 100 kolumn , które często mają miejsce.) Chętnie pokażemy Wam kilka sposobów rozwiązania tego problemu. Po pierwsze, należy zauważyć, że elementy leżące powyżej głównej przekątnej - są elementami a[i][j] dla których i<j , i elementami dla elementów poniżej głównej przekątnej i>j . W ten sposób możemy porównać wartości i i j , które określają wartość a[i][j] . Otrzymujemy następujący algorytm:
n = 4
a = [[0] * n for i in range(n)]
for i in range(n):
for j in range(n):
if i < j:
a[i][j] = 0
elif i > j:
a[i][j] = 2
else:
a[i][j] = 1
for row in a:
print(' '.join([str(elem) for elem in row]))
Algorytm ten jest powolny: wykorzystuje dwie pętle i dla każdej pary (i,j) wykonuje jeden lub dwa if instrukcji. Jeśli skomplikujemy algorytm, będziemy w stanie to zrobić bez instrukcji warunkowej.
Najpierw wypełnij główną przekątną, dla której potrzebujemy jednej pętli:
for i in range(n):
a[i][i] = 1
Następnie wypełnij zerami wszystkie elementy powyżej głównej przekątnej. Aby to zrobić, dla każdego wiersza o numerze i trzeba przypisać wartość do a[i][j] dla j = i+1 , ..., n-1 . Aby to zrobić, potrzebujesz zagnieżdżonych pętli:
for i in range(n):
for j in range(i + 1, n):
a[i][j] = 0
Analogicznie, dla j = 0 , ..., i-1 ustawia elementy a[i][j] równe 2 :
for i in range(n):
for j in range(0, i):
a[i][j] = 2
Możesz połączyć cały ten kod i otrzymać kolejne rozwiązanie:
n = 4
a = [[0] * n for i in range(n)]
for i in range(n):
for j in range(0, i):
a[i][j] = 2
a[i][i] = 1
for j in range(i + 1, n):
a[i][j] = 0
for row in a:
print(' '.join([str(elem) for elem in row]))
Oto inne rozwiązanie, które powtarza listy, aby zbudować kolejne wiersze listy. i linia listy składa się z i liczb 2 , po nich jedna liczba całkowita 1 , a następnie ni-1 zer:
n = 4
a = [0] * n
for i in range(n):
a[i] = [2] * i + [1] + [0] * (n - i - 1)
for row in a:
print(' '.join([str(elem) for elem in row]))
Jak zwykle możesz zastąpić pętlę generatorem:
n = 4
a = [0] * n
a = [[2] * i + [1] + [0] * (n - i - 1) for i in range(n)]
for row in a:
print(' '.join([str(elem) for elem in row]))
5. Tablice dwuwymiarowe: generatory zagnieżdżone
Możesz użyć generatorów zagnieżdżonych do utworzenia tablic dwuwymiarowych, umieszczając generator listy, która jest ciągiem, wewnątrz generatora wszystkich ciągów. Przypomnij sobie, że możesz utworzyć listę n wierszy i m kolumn używając generatora (który tworzy listę n elementów, gdzie każdy element jest listą m zer):
[[0] * m for i in range(n)]
Ale lista wewnętrzna może być również utworzona za pomocą, na przykład, takiego generatora: [0 for j in range(m)] . Zagnieżdżając jeden generator w drugi, otrzymujemy
[[0 for j in range(m)] for i in range(n)]
W jaki sposób wiąże się z naszym problemem? Chodzi o to, że jeśli liczba 0 zostanie zastąpiona przez jakieś wyrażenie zależne od i (numer linii) i j (numer kolumny), otrzymasz macierz wypełnioną według jakiejś formuły.
Załóżmy na przykład, że musisz zainicjować następującą tablicę (dla wygody, dodatkowe spacje są dodawane między elementami):
0 0 0 0 0 0 0 1 2 3 4 5 0 2 4 6 8 10 0 3 6 9 12 15 0 4 8 12 16 20
W tej tablicy znajduje się n = 5 wierszy, m = 6 kolumn, a element z indeksem wiersza i oraz indeksem kolumny j jest obliczany za pomocą formuły a[i][j] = i * j .
Jak zwykle możesz użyć generatora do stworzenia takiej tablicy:
[[i * j for j in range(m)] for i in range(n)]