Tablice
No. Tablice. Cudne narzędzie dla programisty, które pozwala nam tworzyć
zbiory elementów, po których możemy w ustalonej kolejności przechodzić. Na-
rzędzie fajne, ale na początku może napsuć krwi. Zakładam, że tablice indekso-
wane są od 1 do N, gdzie N to długość tablicy.
1.1
Podstawy
Przy wszelkich działaniach na tablicach warto pamiętać, że naturalnie używa
się na nich pętli. Najważniejszą pętlą jest bez wątpienia pętla For - przechodzimy po tych elementach, po których chcemy, jeden po drugim. Najczęściej stosujemy,
by znaleźć coś w tablicy. Przykładowo, minimum:
sub p r o g ()
w c z y t a j tab
w c z y t a j n ’ d l u g o s c t a b e l i
i =1
min = tab ( i )
For i =1 to n
If tab ( i ) < min T h e n
min = tab ( i )
End If
N e x t i
End Sub
Pętli For można też używać, gdy chcemy wyłowić elementy spełniające jakiś
warunek. Wtedy iterujemy po tablicy1 i sprawdzamy, czy jakiś warunek jest
spełniony dla danego elementu i coś robimy, jeżeli jest.
Przykład: podaj ilość elementów, które są większe niż liczba a w tablicy tab:
sub p r o g ()
w c z y t a j tab , a
w c z y t a j n ’ d l u g o s c
t a b e l i
i =1
l i c z n i k =0
For i =1 to n
If tab ( i ) > a T h e n
l i c z n i k = l i c z n i k +1
End If
N e x t i
w y p i s z l i c z n i k
End Sub
Czasami pętla For nie wystarczy. Być może chcemy coś robić tylko do mo-
mentu znalezienia jakiegoś elementu w tablicy. Być może chcemy wykonywać
przestawienia, dopóki nie znajdziemy elementu mniejszego od czegoś. W każdym
razie, naszym celem jest robienie coś z tablicą, dopóki zachodzi jakiś warunek.
Naturalnie wtedy korzysta się z pętli While, ale nie wolno zapomnieć o odpo-
wiedniej2 zmianie indeksu tablicy przy każdym przejściu - pętla While sama
tego nie robi!
1Seksi powiedzenie na ’przechodzimy po wszystkich elementach od lewej do prawej’. Sam nienawidzę korzystać, ale być może będziecie musiały wiedzieć, co to znaczy, więc jest użyte w celu wyjaśnienia.
2odpowiednia - to znaczy taka, która wynika ze sposobu, w jaki rozwiązujemy problem.
Reguły niestety nie ma.
1
Przykład: obrócenie tablicy. Żeby obrócić tablicę (bez używania innej ta-blicy3), wystarczy dojść do połowy tablicy, zamieniając elementy znajdujące się naprzeciw. W tym celu korzystamy z dwóch indeksów: i zaczyna się od jedynki, j od N. Z każdym przejściem zamieniamy element i-ty z j-tym, a następnie zwiększamy i i zmniejszamy j. Robimy to, dopóki i < j.
sub p r o g ()
w c z y t a j tab
w c z y t a j n ’ d l u g o s c t a b e l i
i =1
j = n
Do W h i l e i < j
’ z a m i a n a
t e m p = tab ( i )
tab ( i ) = tab ( j )
tab ( j ) = t e m p
’ o d p o w i e d n i e
u s t a w i e n i e
i n d e k s o w
i = i +1
j = j -1
End W h i l e
End Sub
1.2
Zadania
1.2.1
Usunąć z dwustuelementowej tablicy wszystkie dziesiątki, prze-
suwając pozostałe w lewo.
Zasada działania algorytmu: Przechodzimy po tablicy. Jeżeli znajdziemy 10,
przechodzimy po wszystkich pozostałych elementach tablicy, przepisując ele-
ment j + 1-szy do elementu j-tego. Żeby wiedzieć, gdzie znajduje się ostatni element po usunięciu, możemy zmniejszyć licznik n.
sub p r o g ()
w c z y t a j tab
n = 2 0 0 ’ d l u g o s c
t a b e l i
i =1
Do W h i l e i <= n
If tab ( i ) =10 T h e n
n = n -1
For j = i To n
tab ( j ) = tab ( j +1) ’ p r z e s u n
p o z o s t a l e
e l e m e n t y
N e x t j
End If
i = i +1
End W h i l e
w y p i s z tab (1 .. n ) ’ w n j e s t t e r a z i l o s c e l e m e n t o w t a b l i c y po u s u n i e c i u
d z i e s i a t e k , j e z e l i c h c e m y , m o z e m y r e s z t e
e l e m e n t o w
z a m i e n i c na
j a k a s u s t a l o n a
l i c z b e
End Sub
1.2.2
Sprawdzenie, ile jest różnych liczb w tablicy.
Zasada działania algorytmu: Dwa sposoby. Jeden elegancki, więc mi się po-
doba - posortować tablicę, po czym przejść po niej, dodając do licznika, jeżeli 3To by było oszustwo!
2
dwa kolejne elementy się różnią.4
Ale zadanie to dostałyście przed nauką sortowań, więc trochę mniej przy-
stępny sposób: porównujemy wszystkie możliwe pary elementów. Jeżeli są takie
same, to drugi z nich zastępujemy pierwszym elementem tablicy. Wreszcie, prze-
chodzimy po tablicy i zliczamy liczby, które nie są równe pierwszemu elementowi tablicy.
sub p r o g ()
w c z y t a j tab
w c z y t a j n ’ d l u g o s c t a b e l i
i , j =1
el = tab (1)
’ p i e r w s z e g o
e l e m e n t u n i e m u s i m y b r a c p o d u w a g e
For i =2 To n
For j = i +1 to n
If tab ( i ) = tab ( j ) T h e n
tab ( j ) = el
End If
N e x t j
N e x t i
’ z l i c z a m y
e l e m e n t y r o z n e od t a b ( 1 ) - l i c z n i k
z a c z y n a s i e od 1 , bo t a b
( 1 ) t e z j e s t u n i k a l n y m e l e m e n t e m , k t o r e g o
i n a c z e j
z a p o m n i e l i b y s m y
p o l i c z y c
l i c z = 1
For i =2 To n
If tab ( i ) = el T h e n
l i c z = l i c z +1
End If
N e x t i
w y p i s z l i c z
End Sub
1.2.3
Usuwanie wszystkich duplikatów z tablicy.
Zadanie to tak naprawdę połączenie dwóch pierwszych. Najpierw wykonu-
jemy drugi program bez żadnych zliczań, a potem pierwszy, tylko, że usuwamy
elementy równe pierwszemu elementowi tablicy.
sub p r o g ()
w c z y t a j tab
w c z y t a j n ’ d l u g o s c
t a b e l i
i , j =1
el = tab (1)
’ p i e r w s z e g o
e l e m e n t u n i e m u s i m y b r a c p o d u w a g e
For i =2 To n
For j = i +1 to n
If tab ( i ) = tab ( j ) T h e n
tab ( j ) = el
End If
N e x t j
N e x t i
’ w y w a l a n i e z t a b l i c y ( p i e r w s z e g o
e l e m e n t u n i e w y w a l a m y )
i =2
Do W h i l e i <= n
If tab ( i ) = el T h e n
n = n -1
For j = i To n
tab ( j ) = tab ( j +1) ’ p r z e s u n
p o z o s t a l e
e l e m e n t y
N e x t j
4Dla sportu możecie rozwiązanie zaimplementować same.5
5Taa.
3
i = i +1
End W h i l e
w y p i s z tab (1 .. n )
End Sub
1.2.4
Wypisać z tablicy n-elementowej liczby od największej do naj-
mniejszej.
Posortować. Bo o to chodzi w tym zadaniu. Ew. jeżeli chcemy liczby bez
duplikatów, to posortować i nie wypisywać elementów takich samych, jak wcze-
śniejsze:
sub p r o g ()
’ < - t u t a j s o r t u j e m y t a b
p o p r z e d n i = tab (1) +1 ’ z e b y s i e r o z n i l od p i e r w s z e g o For i =1 To n
If tab ( i ) < > p o p r z e d n i T h e n
w y p i s z tab ( i )
p o p r z e d n i = tab ( i ) ’ z e b y p o r o w n a c z k o l e j n y m
e l e m e n t e m
End If
N e x t i
End Sub
1.2.5
Znaleźć podciąg m-elementowy w ciągu n-elementowym. 6
Zasada działania: Tablica n-elementowa to tabn, tablica m-elementowa (szu-kany podciąg) to tabm. Przechodzimy po tablicy tabn. Jeżeli znajdziemy element równy pierwszemu elementowi tabm, to porównujemy w pętli kolejne elementy.
Jeżeli doszliśmy do końca, to znaleźliśmy podciąg i możemy zwrócić indeks.
sub p r o g ()
w c z y t a j tab_n , t a b _ m
w c z y t a j n , m ’ d l u g o s c
t a b e l i
i , j =1
z n a l e z i o n e = 0 ’ z m i e n n a
l o g i c z n a - jeden , g d y z n a l e z i o n e ; zero , g d y n i e
Do W h i l e i <= n - m And z n a l e z i o n e =0
If t a b _ n ( i ) = t a b _ m (1) T h e n
z n a l e z i o n e = 1 ’ p r z y j m u j e m y , ze j e s t z n a l e z i o n e For j =1 To m
’ i + j -1 , bo w t e d y d l a j =1 d o s t a j e m y i ( z n a l e z i o n y z g a d z a j a c y
s i e e l e m e n t ) , d l a j =2 d o s t a j e m y i +1 ( d r u g i
p o r o w n y w a n y
e l e m e n t ) i t d .
If t a b _ n ( i + j -1) < > t a b _ m ( j ) T h e n
’ j e d n a k n i e z n a l e z i o n e
z n a l e z i o n e = 0
End If
N e x t j
End If
’ j e z e l i n i e z n a l e z l i s m y w t y m o b r o c i e petli , to z w i e k s z a m y l i c z n i k
If z n a l e z i o n e =0 T h e n
i = i +1
End If
End W h i l e
If z n a l e z i o n e =1 T h e n
w y p i s z i ’ w z m i e n n e j i b e d z i e
p o p r a w n y
i n d e k s
E l s e
6Tak dokładniej indeks początkowego elementu podciągu w tablicy n-elementowej
4
w y p i s z " nie z n a l e z i o n o "
End If
End Sub
1.3
Kolos
Mała uwaga: jeżeli zadanie wydaje się wam łatwe, radzę spróbować je zrobić
bez patrzenia w napisany kod. Większość z tych zadań jest prosta, a trochę
praktyki przed kolosem nie zaszkodzi.
1.3.1
Zad 1 - suma ciągu 3 , 6 , 9 ...N ∗ 3
sub p r o g ()
w c z y t a j n
i =1
sum =0
For i =1 To n
sum = sum +( i *3)
N e x t i
w y p i s z sum
End Sub
1.3.2
Zad 2 - suma elementów dodatnich oraz ujemnych w tablicy
sub p r o g ()
w c z y t a j tab
w c z y t a j n
s u m _ d o d = 0
s u m _ u j
= 0
For i =1 To n
If tab ( i ) >0 T h e n
s u m _ d o d = s u m _ d o d + tab ( i )
E l s e If tab ( i ) <0 T h e n
s u m _ u j
= s u m _ u j
+ tab ( i )
End If
N e x t i
w y p i s z s u m _ d o d
w y p i s z s u m _ u j
End Sub
1.3.3
Zad 3 - minimum oraz maksimum w tablicy, jedna pętla
Stosujemy drobny trik - jeżeli coś jest nowym maksimum, na pewno nie
będzie nowym minimum, więc nawet nie musimy sprawdzać.
sub p r o g ()
w c z y t a j tab
w c z y t a j n
min , max = tab (1)
For i =2 To n
If tab ( i ) > max T h e n
max = tab ( i )
E l s e If tab ( i ) < min T h e n
min = tab ( i )
End If
N e x t i
5
w y p i s z min
End Sub
1.3.4
Zad 4 - Wpisywanie do tablicy A o rozmiarze 10 według zasady
A( i) = (2 . 5 ∗i+5) , oraz podaj czwarty element 3 . 0
Czwarty element: (2 . 5 ∗ 4+5) = 15 = 5
3 . 0
3
sub p r o g ()
’ r o b i m y t a b l i c e
Dim tab (1 to 10) As D o u b l e
For i =1 To 10
tab ( i ) = ( 2 . 5 * i + 5) / ( 3 . 0 )
N e x t i
End Sub
1.3.5
Zad 5 - Wczytaj n liczb, wypisz w odwrotnej kolejności
sub p r o g ()
w c z y t a j n
’ t w o r z y m y
t a b l i c e
Dim tab (1 to n ) As I n t e g e r
’ w c z y t a j
l i c z b y
For i =1 To n
w c z y t a j t e m p
tab ( i ) = t e m p
N e x t i
’ w y p i s z w o d w r o t n e j
k o l e j n o s c i
Do W h i l e n >0
w y p i s z tab ( n )
n = n -1
End W h i l e
End Sub
1.3.6
Zad 6 - co wypisze algorytm
Przy pierwszym przejściu: C = 7, A = 4, B = 7
Skoro C < 10, to drugie przejście: C = 11, A = 7, B = 11
Skoro C 10, to koniec pętli, algorytm wypisze 7.
1.3.7
Zad 7 - sito Eratostenesa (liczby pierwsze7 z zakresu od [2 , 100]).
Sito Eratostenesa (jeżeli nie pamiętacie) działa na prostej zasadzie: bierze
liczbę pierwszą, skreśla jej wielokrotności, kolejna nieskreślona liczba jest pierw-sza, bierze ją i skreśla jej wielokrotności i tak dalej dla całego zakresu8. Bardzo efektywny sposób znajdowania liczb pierwszych - jest znane lepsze sito, ale bardzo niewiele lepsze. Także brawo, Eratostenesie!
7Mniam.
8Mała uwaga: stricte rzecz biorąc, dla zakresu [2 , 100] nie trzeba wykonywać skreślań wielokrotności liczb większych od 10. Ale powód, dla którego tak jest, jest trochę skomplikowany, więc w tym kodzie skreślania wielokrotności trwają dla wszystkich nieskreślonych.
6
’ t w o r z y m y
t a b l i c e - t a b ( i ) =0 < - e l e m e n t
s k r e s l o n y ; t a b ( i ) =1 < - e l e m e n t
n i e s k r e s l o n y
Dim tab (2 to 1 0 0 ) As I n t e g e r
’ w p i s z j e d y n k i do t a b l i c y
For i =2 To 100
tab ( i ) = 1
N e x t i
’ z n a j d z
p i e r w s z y
e l e m e n t
n i e s k r e s l o n y
i =2
Do W h i l e i < 1 0 0
If tab ( i ) =1 T h e n
’ e l e m e n t n i e s k r e s l o n y , s k r e s l a j
w i e l o k r o t n o s c i
j =2
Do W h i l e i * j < 1 0 0
tab ( i * j ) =0
j = j +1 ’ k o l e j n a
w i e l o k r o t n o s c
End W h i l e
End If
i = i +1
End W h i l e
End Sub
1.4
Egzamin
Na razie zrobione tylko mnożenie macierzy, bo pozostałych zadań ma (po-
noć) nie być, albo są one łatwe do znalezienia na Google (warunki Neumanna i
Dirichleta, schemat blokowy bąbelkowego), albo ogólnie umiecie (zamiana sys-
temów liczb).
1.4.1
Mnożenie macierzy
Żeby macierze pomnożyć, musimy przyjąc kilka założeń. Mnożymy macierz
A przez macierz B.
Żeby macierze te dało się pomnożyć, macierz A musi mieć tyle kolumn, co macierz B rzędów. Zatem przyjmuję, że macierz A ma wymiary n × p, a macierz B wymiary p × m. Wynik ma wtedy wymiary n × m.
Element ci,j macierzy wynikowej C to następująca suma:
p
X
ci,j =
ai,kbk,j
(1)
k=1
Innymi słowy, element macierzy wynikowej w rzędzie i-tym oraz kolumnie
j-tej to suma iloczynów odpowiadających sobie elementów z i-tego wiersza A i j-tej kolumny B.
Możemy więc zabrać się9 za kod.
sub p r o g ()
w c z y t a j A , B
w c z y t a j n , p , m
Dim C (1 to n , 1 to m ) As I n t e g e r ’ m a c i e r z
w y n i k o w a
’ i - ty w i e r s z
For i =1 To n
9wreszcie!
7
For j =1 To m
’ s u m a i l o c z y n o w
sum = 0
’ k - ty i l o c z y n w s u m i e
For k =1 to p
sum = sum + A ( i , k ) * B ( k , j )
N e x t k
C ( i , j ) = sum
N e x t j
N e x t i
w y p i s z C
End Sub
8
Sortowania
Tytułem wstępu, każdy przykład pseudokodu sortuje w kolejności rosnącej.
By zmienić kolejność, najczęściej wystarczy obrócić znak przy porównaniu ele-
mentów.
2.1
Sortowanie bąbelkowe10
Najczęściej używane przy nauce sortowanie. Działa bardzo prosto: przecho-
dzi po tablicy od lewej do prawej, porównując pary sąsiadujących elementów.
Jeżeli lewy porównywany element jest większy (w sortowaniu w kolejności ro-
snącej), zamieniamy elementy miejscami.
Warto zauważyć, co dzieje się przy jednym przejściu: znajdowany jest ele-
ment największy, i ten element jest przenoszony kolejnymi zamianami na koniec
tablicy. Dlatego z każdym przejściem zmniejszamy n: element n-ty już na pewno jest na swoim miejscu.
sub p r o g ()
w c z y t a j tab
w c z y t a j n ’ d l u g o s c
t a b e l i
i =1
’ p e t l a
z a r z a d z a j a c a
i l o s c i a
p r z e j s c
Do W h i l e n >1
For i =1 to n -1
If tab ( i ) > tab ( i +1) T h e n
t e m p = tab ( i )
tab ( i ) = tab ( i +1)
tab ( i +1) = t e m p
End If
N e x t i
n = n -1 ’ o s t a t n i
e l e m e n t j e s t j u z u s t a w i o n y
End W h i l e
End Sub
Jak widać, algorytm jest prosty. Oraz nieużywany: jest powolny, wykonuje
dużo zamian (nie lubimy zamian, są drogie). Są jego ulepszenia (mało skompli-
kowane, np. sprawdzanie, czy zaszła jakaś zamiana przy przejściu - jeżeli nie,
to tablica jest posortowana; ale i bardziej udziwnione, których nie będę przytaczał), ale zwykle nie są one sensowne. A bazowy bubble sort jest pozbawiony
sensu do cna.
2.2
Sortowanie przez wybór11
Przyjęło się jako nieco czarnawy dowcip informatyczny, że jeżeli kogoś zmu-
siłoby się do wymyślenia algorytmu sortowania przez przystawienie pistoletu do
głowy, wymyśliłby sortowanie przez wybór. Jest w tym sporo prawdy: algorytm
można opisać słowami “znajdź wśród nieposortowanych elementów element naj-
mniejszy i przenieś go na koniec listy elementów już posortowanych”. Łatwo
zauważyć zasadę działania tego algorytmu.
10ang. Bubble Sort
11ang. Selection Sort
9
w c z y t a j tab
w c z y t a j n ’ d l u g o s c
t a b e l i
i , j =1
’ i n d e k s i to p i e r w s z y
n i e p o s o r t o w a n y e l e m e n t , e l e m e n t y
p o s o r t o w a n e b e d a
p r z e d i
For i =1 to n
’ s z u k a m y w s r o d
n i e p o s o r t o w a n y c h
m i n i m u m
m i n i = i
For j = i +1 to n
If tab ( j ) < tab ( m i n i ) T h e n
m i n i = j
End If
N e x t j
’ z a m i e n i a m y
m i e j s c a m i
e l e m e n t na p o z y c j i i - t e j o r a z m a k s i m u m , k t o r e z n a l e z l i s m y , j e z e l i
i n d e k s y te s i e r o z n i a
If m i n i < > i T h e n
t e m p = tab ( i )
tab ( i ) = tab ( m i n i )
tab ( m i n i ) = t e m p
End If
N e x t i
End Sub
Tutaj szczęśliwie żadnych ulepszeń nie ma. Algorytm ten jest lepszy od ba-
zowego sortowania bąbelkowego, ale nie ma cudów - w końcu pisany pod groźbą
postrzału.
2.3
Sortowanie przez wstawianie12
Święty Graal podstawowych algorytmów sortowania. Jak przystało na kie-
lich cieśli, jest prosty, ale skuteczny.13 Idea ponownie prosta: budujemy zbiór posortowany, przenosząc ze zbioru jeszcze nie posortowanych jeden element i
wstawiając go w odpowiednie miejsce.
W programie implementujemy to w następujący sposób: mamy indeks i,
który oznacza nam, w którym miejscu jest pierwszy element ze zbioru “jeszcze
nie wstawionych”14. Ten element następnie przenosimy w lewo, zamieniając ko-
lejne pary, dopóki element nie jest w dobrym miejscu. Wtedy zwiększamy indeks
i - mamy o jeden więcej element “wstawiony”.
sub p r o g ()
w c z y t a j tab
w c z y t a j n ’ d l u g o s c
t a b e l i
i , j =1
For i =2 to n
e l e m e n t = tab ( i )
’ p r z e n o s i m y
e l e m e n t w o d p o w i e d n i e
m i e j s c e
i n d e k s _ d z i u r y = i
Do W h i l e i n d e k s _ d z i u r y > 1 And tab ( i n d e k s _ d z i u r y -1) > e l e m e n t tab ( i n d e k s _ d z i u r y ) = tab ( i n d e k s _ d z i u r y -1)
i n d e k s _ d z i u r y = i n d e k s _ d z i u r y - 1
End W h i l e
tab ( i n d e k s _ d z i u r y ) = e l e m e n t
N e x t i
End Sub
12ang. Insertion Sort
13Chociaż nieśmiertelności po użyciu jego bym nie oczekiwał.
14Zbiór, do którego na pewno nie chcemy należeć - nudno!
10
Sortowanie przez wstawianie jest najszybsze z tych, które znacie. Jeżeli tablica jest już posortowana, wykonuje tylko tyle kroków, ile jest elementów -
lubimy coś takiego, dane w prawdziwym świecie często są choć trochę posorto-
wane.
11