Tabela

Tabela

Avtor: Mojca Kerin

Besedilo naloge

Imamo kvadratno tabelo števil n × n, ki je urejena tako, da števila strogo naraščajo po vrsticah in po stolpcih. Primer tabele 5 × 5: 1 3 7 9 11 2 4 8 12 14 3 5 9 13 15 4 6 12 15 17 5 7 15 16 18 Za nek podatek želimo izvedeti, kolikokrat in kje nastopa v tej tabeli. Napiši podprogram, ki dobi kot argument iskano število in izpiše koordinate vseh mest v tabeli, kjer se nahaja to število. Nasvet: obstaja rešitev, pri kateri ni treba pregledati vseh elementov, kar je pomemben prihranek časa pri velikih tabelah.

Opis problema in ideja rešitve

V datoteki imamo zapisana števila po vrsticah, med seboj ločena s predsledki. S pomočjo nekja zank bomo lahko pregledali elemente v tej tabeli. Števila bomo med seboj primerjali, ter vsakič, ko bo število enako iskanemu bomo povečali števec, ter zapisali v seznam 'koordinate', kje se ta element nahaja. Na primer, da se nek element nahaja v drugi vrstici in v tretjem stolpcu to zapišemo kot [2,3]. Da bo program tudi hiter za tabele, ki so zelo velike, bo boljše, da primerjamo elemente samo do tistega elementa, ki je tenak iskanemu, saj so vrstice zgrajene tako, da je število, ki je desno od trenutnega števila večje. Tako v isti vrstici zagotovo ni več iskanega števila.

Razlaga algoritma - 1.del

Kodo začnemo z ukazom def, nato zapišemo ime metode, v oklepaju pa podamo parametre. Naša metoda po sprejela dva parametra ime datoteke in število, za katerega nas zanima, kolikokrat in kje se pojavi v dani tabeli.

Števec stevec bo hranil podatke o tem, kolikokrat se je neko število pojavilo v tabeli. Na začetku ga nastavimo na 0. Določimo še seznam sez, v katerega bomo shranjevali koordinate kjer se nahaja iskani element. Števec k bo hranil podatek o tem v kateri vrstici smo, nastavimo na 0. Potrebovali ga bomo pri določanju 'koordinate' elementa.

S pomočjo ukaza open odpremo datoteko za branje, ter jo shranimo v spremenljivko dat. Potem gremo s pomočjo for zanke skozi vsako vrstico v datoteki dat, ji s pomočjo ukaza strip odstranimo 'bele' znake (beli znaki so: skok v novo vrstico: '\n', tabulatorji: '\tab'….). V spremenljivko a shranimo tekočo vrstico, ki jo predhodno spremenimo v seznam s pomočjo ukaza split (), ki mu za parameter podamo ' ' niz, ki vsebuje presledek, saj so naši elementi v datoteki ločeni s presledkom, ker jih ukaz split razbije na majhne nize glede na ta parameter.

Sedaj izgleda metoda tako, kot je prikazano na sliki spodaj.

(MojcaKerin_tabela4.png)

Razlaga algoritma - 2.del

Ko to imamo k povečamo za 1, saj smo že v neki vrstici (trenutno v prvi, ko se bo naslednjič izvedla for zanka bomo v drugi vrstici ...). Števec ipa bomo potrebovali za izvajanje zanke while. Začnemo z while zanko, ki se bo izvajala vse dokler bo števec i večji od dolžine seznama a. Dolžino seznama a dobimo z ukazom len(a). Nato z if stavkom preverimo, če je slučajno že prvi elment v seznamu a večji od iskanega števila, kajti potem zagotov v preostanku tabele ni nobenega števila, ki bi bil enak iskanemu številu. Če se to zgodi, potem lahko funkcijo kar zaklučimo. Če uporabimo metodo return sredi funkcije , se bo le ta zključila, takoj ko jo zazna. Tako se bo v tem primeru tu končala naša funkcija, kar pa tudi želimo in vrnila števec stevec ter seznam koordinat.

Če se ta if stavek ne izvede, potem se funkcija ne zaključi. Nato preverimo, če je i-ti element tega seznama a enak iskanim številom. To storimo s pomočjo ukaza if: if int(a[i])==stevilo: . Ker so v seznamu števila zapisana kot nizi, jih moramo še prej spremeniti v števila. To storimo s pomočjo ukaza int. Če je pogoj izpolnjen števec povečamo za 1, ter v seznam dodamo par števil, ki predstavljata 'koodrinati' kje je to število postavljeno. To storimo tako: sez.append((k,a.index(a[i])+1)). Tu uporabimo števec k, ki pove v kateri vrstici se nahajamo. Y koordinato pa dobimo tako, da pogledamo na katerem mestu v seznamu je ta element. Ker se indeksi elementov seznamu začnejo z 0, moramo piršteit še 1. Seznam a nastavimo na pazen seznam, tako se while zanka ne bo več izvajala, saj je sedaj dolžina seznama enaka 0, števec pa bo imel vrednost najmanj 1. Zunaj if stavka, števec še števec i povečamo za 1.

Na koncu zapišemo return stevec, sez, ki vrne število, kolikokrat se je iskani element pojavil v tabeli, ter seznam koordinat kje se je pojavil.

Sedaj izgleda metoda tako, kot je prikazano na sliki spodaj.

(MojcaKerin_tabela1.png)

Testni program

0%
0%