Naloge za bolj napredne

Ta dokument vsebuje malo težje naloge v programskem jeziku Go.

Naloga 1: Urejanje z mehurčki in binarno iskanje

1a) isSorted: je seznam urejen?

Preveri, ali je vsak element manjši ali enak naslednjemu. Če najdeš en sam par, kjer to ne drži, seznam ni urejen.

func isSorted(s []int) bool

Prazen seznam in seznam z enim elementom sta urejena. Če ti to vrne false ali sesuje program, imaš napako v mejah zanke.

1b) bubbleSort: urejanje z mehurčki

Kaj je to? Eden najpreprostejših načinov urejanja, zato ga je tudi razmeroma lahko napisati.

Greš čez seznam od začetka do konca in vsakič primerjaš dva soseda. Če je levi večji od desnega, ju zamenjaš. Ko prideš do konca, se je največje število premaknilo povsem na desno, podobno kot mehurček, ki priplava na površje. Zato se metoda tako imenuje.

Potem greš še enkrat čez seznam. In še enkrat. Z vsakim prehodom se naslednje največje število premakne na svoje mesto. Ko v celem prehodu ni več nobene zamenjave, si končal.

Primer na [3 1 2]:

[3 1 2]  primerjaj 3 in 1 → zamenjaj → [1 3 2]
[1 3 2]  primerjaj 3 in 2 → zamenjaj → [1 2 3]
konec prehoda, bila je zamenjava, gremo še enkrat
[1 2 3]  primerjaj 1 in 2 → v redu
[1 2 3]  primerjaj 2 in 3 → v redu
ni bilo zamenjav → urejeno

func bubbleSort(s []int)

Uredi obstoječi seznam (funkcija ne vrne ničesar), ne da bi ustvaril novega. Zamenjava dveh elementov gre v Go takole:

s[i], s[j] = s[j], s[i]

sort.Slice je za zdaj prepovedan.

Po vsakem sortiranju preveri rezultat s svojo funkcijo isSorted. To je poanta naloge 1a.

Dodatno: dodaj zastavico, ki prekine zanko, če v celem prehodu ni bilo nobene zamenjave. Preveri, da [1 2 3 4 5] zdaj naredi samo en prehod.

1c) binarySearch: binarno iskanje

Kaj je to? Igra "uganem tvoje število med 1 in 100". Nihče ne ugiba 1, 2, 3, 4... Smiselno je najprej vprašati "je večje od 50?" in s tem izločiti polovico vseh možnosti.

Isto počneš v urejenem seznamu. Pogledaš element na sredini:

• če je enak iskanemu → našel si ga, končaj
• če je prevelik → iskano število je gotovo levo od sredine, zato desno polovico izloči iz nadaljnjega iskanja
• če je premajhen → iskano število je gotovo desno, zato levo polovico izloči iz nadaljnjega iskanja

Nato postopek ponoviš na polovici, ki ti je ostala. Z vsakim korakom območje iskanja znova prepoloviš, dokler elementa ne najdeš ali ne ostane nič.

V seznamu s tisoč elementi to najde število v desetih korakih namesto v tisoč. Deluje pa samo, če je seznam urejen. Sicer pravilo "levo je manjše, desno je večje" ne drži in binarno iskanje ne deluje pravilno.

Potrebuješ dve spremenljivki, low in high, ki povesta, kje se še išče. Sredina je (low + high) / 2.

func binarySearch(s []int, target int) int

Vrne indeks elementa target, ali -1, če ga ni. Predpostavi, da je s urejen.

Za teste uporabi s = [1 3 5 7 9 11]:

Robni primeri, ki jih moraš preveriti posebej:

Pazi na pogoj zanke: Je low < high ali low <= high? Ena od teh dveh možnosti pri seznamu z enim elementom sploh ne vstopi v zanko. Preveri na [5].

Poskus na koncu: poženi binarySearch([]int{9, 3, 7, 1}, 7). Kaj vrne? Zakaj se program ne sesuje, ampak vseeno vrne narobe?

Naloga 2: Eratostenovo sito

Ponovitev: praštevilo je število, večje od 1, ki je deljivo samo z 1 in samo s sabo. 2, 3, 5, 7, 11, 13... Število 12 ni praštevilo, ker je 12 = 3 × 4. Število 1 po dogovoru ni praštevilo.

2a) Naivna različica

Najbolj očiten način: za vsako število posebej preveri, ali ga deli kakšno manjše število. Če najdeš delitelja, ni praštevilo.

func isPrimeNaive(n int) bool
func primesNaive(limit int) []int

Za vsako število preveri vse možne delitelje. Deljivost preveriš z ostankom: n % d == 0 pomeni "d deli n".

primesNaive(30) → [2 3 5 7 11 13 17 19 23 29] primesNaive(2) → [] (če zgornja meja ni vključena). Odloči se in zapiši, katero pravilo uporabljaš. primesNaive(1) → [] primesNaive(0) → []

2b) Sito

Kaj je Eratostenovo sito? Namesto da za vsako število posebej preverjaš, ali je praštevilo, pristopiš drugače: prečrtaš vsa števila, ki zagotovo niso praštevila.

Napiši vsa števila od 2 do limit na tablo. Potem:

1. Obkroži 2, ker je praštevilo. Prečrtaj vse večkratnike dvojke: 4, 6, 8, 10...
2. Pojdi na naslednje neprečrtano število, to je 3. Obkroži ga in prečrtaj 6, 9, 12, 15...
3. Naslednje neprečrtano je 5 (4 je že prečrtana). Obkroži, prečrtaj 10, 15, 20...
4. Nadaljuj do konca.

Kar ostane neprečrtano, so praštevila. Deljivosti pri tem ne preverjaš neposredno, temveč sistematično prečrtuješ večkratnike.

V kodi je "tabla" seznam []bool dolžine limit+1. Indeks predstavlja število, vrednost pa pove, ali je to število prečrtano.

func sieve(limit int) []int

Rezultat mora biti identičen naivni različici. Napiši kratko primerjavo, ki to preveri za vse meje od 0 do 100.

2c) Meritev

start := time.Now()
// ...
fmt.Println(time.Since(start))

Poženi obe različici za limit = 1_000_000 in zapiši čas:

• naivna: __
• sito: __

Vprašanje: koliko praštevil je pod milijonom? (Odgovor: 78498. Če dobiš drugo številko, imaš napako v mejah.)

Naloga 3: Uravnoteženi oklepaji, ampak s števili

Kaj pomeni uravnoteženo? V matematiki mora biti vsak odprt oklepaj zaprt, in to v pravem vrstnem redu. ([]) je v redu, ([)] ni, ker se kvadratni oklepaj odpre znotraj okroglega in se mora zato tudi zapreti znotraj njega.

Pri nas namesto znakov delamo s števili. Seznam []int, kjer:

• pozitivno število n pomeni odprt oklepaj tipa n
• negativno število -n pomeni zaprt oklepaj tipa n

Torej je [1 2 -2 -1] isto kot ([]), [1 2 -1 -2] pa isto kot ([)].

Kaj je sklad? Kup krožnikov. Nov krožnik daš na vrh, in ko rabiš krožnik, vzameš zgornjega. Do spodnjih ne prideš, dokler ne odstraniš vseh nad njimi. Angleško: push (položi na vrh) in pop (poberi z vrha).

Sklad je za to nalogo primerno orodje: ko naletiš na odprt oklepaj, ga položiš na vrh. Ko naletiš na zaprtega, pogledaš, kaj je na vrhu. Če se ujema, ga odstraniš; sicer zaporedje ni uravnoteženo.

func isBalanced(s []int) bool

Seznam uporabi kot sklad:

sklad = append(sklad, x)          // push
vrh := sklad[len(sklad)-1]        // peek
sklad = sklad[:len(sklad)-1]      // pop

Testni primeri

Pogosta napaka: [-1] na začetku. Če poskusiš odstraniti element s praznega sklada, se program sesuje zaradi dostopa zunaj meja seznama. Prazen sklad moraš preveriti pred dostopom.

Druga pogosta napaka: ko se zanka konča, mora biti sklad prazen. Če na to pozabiš, ti [1] vrne true.

Kaj pa ničla? Odloči se, kaj pomeni 0 v vhodu, in to zapiši v komentar.

Naloga 4: Naloge s števkami

Vse brez pretvorbe v niz. Potrebuješ samo dve stvari:

• n % 10 ti da zadnjo števko števila. Za 1234 dobiš 4.
• n / 10 odreže zadnjo števko. Za 1234 dobiš 123. (V Go med celimi števili deljenje vedno zaokroži navzdol.)

Če ti operaciji ponavljaš v zanki, števke obdeluješ od desne proti levi, dokler ne ostane 0.

4a) sumDigits(n int) int: vsota števk

123 → 1 + 2 + 3 = 6

4b) reverseNumber(n int) int: obrni število

1234 → 4321. Namig: rezultat gradiš tako, da ga vsakič pomnožiš z 10 in prišteješ novo števko.

Pozor: 100 → 1, ne 001. Vodilne ničle pri številih ne obstajajo. Če pričakuješ 001, si mislil na nize.

4c) isPalindrome(n int) bool: je palindrom?

Palindrom je nekaj, kar se enako bere naprej in nazaj. Pri besedah: perper, ana, potop. Pri številih: 121, 1221, 7. Če si naredil nalogo 4b, je ta rešljiva v eni vrstici.

Enomestna števila so palindromi. Če ti 7 vrne false, poglej svoje meje.

4d) Palindromska praštevila

Združi sito iz naloge 2 s isPalindrome. Poišči vsa praštevila pod 10 000, ki so hkrati palindromi.

Preverjanje: prvih nekaj je 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929. Pod 10 000 jih je 113.

Za razmislek: koliko štirimestnih palindromskih praštevil je? Zakaj toliko? (Namig: vsota števk.)

Naloga 5: Najdaljše naraščajoče zaporedje

func longestIncreasingRun(s []int) int

Vrni dolžino najdaljšega zaporednega odseka, kjer je vsak element strogo večji od prejšnjega.

Pomembno: elementi morajo biti eden za drugim v seznamu, ne smeš jih preskakovati. V seznamu [1 2 3 1 2] je najdaljši tak odsek 1 2 3, torej dolžine 3.

Ideja: seznam pregledaš v enem samem prehodu in sproti hraniš dve vrednosti: dolžino trenutnega odseka in dolžino najdaljšega odseka, ki si ga našel do zdaj. Ko naslednji element ni večji od prejšnjega, se trenutni odsek konča in začneš šteti od začetka.

Testni primeri

Pogoste napake:

1. Prazen seznam. Če začneš z najdaljsi := 1, ti bo [] vrnil 1.
2. Kdaj ponastaviti števec? Ko naslednji element ni večji od prejšnjega, je novi odsek dolg 1, ne 0.
3. Zadnji odsek. Če najdaljši odsek konča na zadnjem elementu, ga zlahka spregledaš, odvisno od tega, kje posodabljaš maksimum. Preveri z [1 2 1 2 3 4].

Razširitev, če ostane čas

Vrni tudi začetni indeks najdaljšega odseka (dve vrnjeni vrednosti).

Za [1 3 2 4 6 8 1] → (4, 2), torej dolžina 4, začne se pri indeksu 2.

Če je več odsekov enake dolžine, vrni prvega. Preveri z [1 2 1 2 1 2] → (2, 0).