Kahemõõtmelise massiivi töötlemine

From Wikiversity

< 9. nädala teemad

Üldist[edit]

Kahemõõtmeline massiiv koosneb mitmest reast, mis on ühte muutujasse kokkuvõetud. Võime teda ettekujutada umbes sarnasel viisil kui mõnda tabelarvutuse tabelit - igal real ja veerul on oma number (indeks) ning ühe väärtuse kättesaamine massiivist eeldab kahe indeksi kasutamist.

Tehniliselt on võimalik kasutada ka rohkemats mõõtmetega massiive (kolme-, nelja- jne mõõtmelisi), kuid enamasti vajadus nende järele puudub, sest andmestiku (või algoritmi) iseloom on tavaliselt see, mis tingib teatud tüüpi massiivi kasutamise. Kahemõõtmelise massiivi kohta on öeldud, et kui selle töötlemisest aru saadakse ja osatakse seal nii ridu kui veerge pidi liikudes igasugused probleemid lahendada, siis on elementaarsem algoritmimine selge.

Näiteid kasutamisest[edit]

Millal võiks olla kasu kahemõõtmelisest massiivist? Siis kui andmestik on olemuselt selline. Näiteks mõtleme oüliõpilaste pikkuste ülesandele (leida kesmisest lühemad ...). Oletame, et meil on vaja sama tulemust leida eraldi erinevate õpperühmade üliõpilaste kohta (erinevad kursused, eriala vms). Või teine juba tuttav näide - sprodipäeval visatud pall. Kujutame ette, et algandmetena on teada iga õpilase 3 katset ja vaja on leida võitja vms.

Esimesel juhul sobiks õpperühmade andmete eristamiseks paigutada iga õpperühma andmed eraldi massiivi ridadesse. Teise näite puhul aga - kuna esimene samm võiks olla iga õpilase parima tulemuse tuvastamine, siis organiseerida iga õpilase andmed eraldi ritta.

Lisaks võib kasu olla sellisest massiivist ka mõnel juhul, kus selline andmestik üldse välja ei paista - selle nädala ülesannete all kvalifitseerub selleks puuduvate doominokivide leidmise ülesanne.

Töötlemise põhimõtted[edit]

Kui ühemõõtmeline andmestik vajas töötlemiseks lihtsamal juhul ühte tsüklit, siis kahemõõtmelise massiivi puhul ei pääse kahest üksteise sisse paigutatud tsüklist, kui on sooviks kõik massiivi elemendid vähemalt ühe korra läbi käia. Nende tsüklite eesmärgiks on ühelt poolt õige korduste arvu määramine ja teisalt indeksite saamine vajalikus järjekorras. Ühemõõtmelise massiivi juurest on juba tuttav tsüklimuutuja kasutamine indeksina. Samal viisil saab ära kasutada ka kahe koos töötava tsükli muutujaid.

Järgnev näide ei pretendeeri ühegi konkreetse keele for-tsüklile, kuid käitumismuster on tüüpiline:

Sisesta A[N, M] 
for rida in [0 .. N-1]
   for veerg in [0 .. M-1]
      ...teeme midagi elemendiga A[rida,veerg]
   endfor
endfor

Millises järjekorras töödeldakse selles näites massiivi elemente? Ridade kaupa. Selle mõistmiseks võiks välja kirjutada indeksite rida ja veerg väärtuste paarid tsüklite seest. Oletame, et N on 3 ja M on 4:

rida veerg
0    0
0    1
0    2
0    3
1    0
1    1
1    2
1    3
2    0
2    1
2    2
2    3

Mida teha massiivi veergude kaupa töötlemiseks? Vahetada rea ja veeru indekseid muutvad tsüklid omavahel ära.

Kahemõõtmeline struktuur Pythonis[edit]

Kahemõõtmelise struktuuri Pythonis moodustavad listid, mis on paigutatud ühe suure listi sisse. Üldine töötlemise põhimõte on sarnane eelpool kirjeldatule.

Näide 1 (mis ei ole päris Pythoni-pärane) tekitab nullidega täidetud kahemõõtmelise struktuuri - listi listidest:

# Listide listi nullimine: nullidest koosnevad listid tuleb ükshaaval
# "üles ehitada", et vältida hilisemaid üllatusi.
n = int(input('Massiivi külg?'))
a = []
for r in range(n):
    rida = []
    for v in range(n):
        rida += [0]
    a += [rida]
print (a)

Näide 2 on alguseks maagilise ruudu kontrollimise ülesandele, näidates samal ajal ka erinevaid listide listis liikumise võimalusi:

# -*- coding: ISO-8859-4 -*-
#NB! Programmi tuleb täiendada, vaata allpool olevaid kommentaare
print("Loeme sisse listi listis.")
print("Kõigepealt algväärtustame massiivi 0-idega ja selleks on vaja teada ridade ja veergude arvu.")
#Maaglises ruudus on tegelikult ridu ja veerge sama palju - seega võiks piirduda ühe muutuja
#küsimisega, kuid näidet võib sel viisil vaadata laiemalt.
ridu = int(input("Mitu rida? "))
veerge = int(input("Mitu veergu? "))
a = []
for r in range(ridu):
    rida = []
    for v in range(veerge):
        arv = int(input("Sisesta arv"))
        rida += [arv]
    a += [rida]
print(a)
Järgnev tsükkel näitab, kuidas leida ja eraldi listis meeles pidada kõigi ridade summad.
rea_summa = []
for r in range(ridu):
    summa = 0
    for v in range(veerge):
        summa = summa + a[r][v]
    rea_summa += [summa]
print(rea_summa)
# Siia tuleb lisada veel veerusummade leidmine
# Ja seejärel mõlemad summad ühte listi kokku
# panna. Tekkinud list kannab praegu nime summad.

#Ja lõpuks "maagilisuse" kontroll põhimõttel, et kui avastatakse mingi kõrvalekalle, siis 
#fikseeritakse teadmine, et ei ole maagiline.
on_maagiline = True
for r in range(ridu + veerge):
    if summad[0] != summad[r]:
        on_maagiline = False
if on_maagiline == True:
    print("on")
else:
    print("ei ole")

Eelmisest näitest võib seega leida mitu erinevat ideed listide listi töötlemiseks. Ja see näide peab saama ülesannete lahendamise käigus täiendust veergude summade leidmise ja kontrollimise näol.

< 9. nädala teemad