Suurim ja vähim väärtus

From Wikiversity
Jump to navigation Jump to search

< 7. nädala teemad

Milleks?[edit]

Arvujadas paikneval suurimal või väikseimal elemendil (nn miinimumil või maksimumil) võib olla oluline tähendus kogu jada suhtes. Suurimat või vähimat väärtust võib olla vaja leida ka mõne teise algoritmi koostisosana. Seetõttu tuleks teada, kuidas nimetatud väärtused massivist ülesleida.

Mitmed programmeerimiskeeled annavad kasutajale võimaluse jadast suurimat ja/või vähimat väärtust leida funktsiooni kasutades. Samas on tegemist väikese algoritmiga, mille toimispõhimõtet on kasulik mõista mitmel erineval põhjusel. Näiteks jada (väärtused), millest suurimat leida, ei pruugi nii selgelt esitatud olla (või ei pruugi kõik andmed korraga kättesaadavad olla). Väärtuse leidmine võib sõltuda veel mõnest tingimusest (a la pikim tüdruk). Ja lõpuks - seda ideed võib olla vaja kasutada mõnes veidi erinevas kontekstis ning iga täiendus meie standardalgoritmide tundmisesse teeb meid targemaks nüüd ja tulevikus.

Lisaks tasub arvestada ka sellega, et arvutit ei ole põhjust ülearu tööd tegema panna. Lõpuks võib see töökiirusele pahasti mõjuda, sest hoolimata sellest, et programmis seisab üks väike funktsiooni väljakutse, on seal taga ikka sama suur töö.

Suurima väärtuse leidmise idee[edit]

  1. Võtame kasutusele uue muutuja maks, mille väärtus töö lõpuks saab olema jadas paiknev suurim väärtus.
  2. Omistame muutujale maks jada esimese elemendi väärtuse.
  3. Teeme tsükli üle kõigi jadas olevate arvude ja iga arvuga:
    • võrdleme iga arvu suurust muutujaga maks
    • kui jadas olev arv > maks, siis asendame muutuja maksväärtuse selle sama võrreldud arvuga (ehk teeme tehte: arv = maks)

(st leidsime uue arvu, mis võiks pretendeerida maksimumi nimele, kuna ta on kõigist senistest arvudest suurim).

Modifikatsioonid[edit]

Sellele algoritmile võib teha mitu modifikatsiooni:

  1. Maksimumi asemel saab leida miinimumi (selleks on vaja ainult märk võrdlustehtes ära vahetada).
  2. Maksimumi enda meelespidamise asemel peetakse meeles indeksit. Seda varianti saab kasutada vaid massiivi kasutades (kus indeksid on olemas). Kui indeks on teada, on ka arv alati kättesaadav.

Nimetatud modifikatsiooni plussiks on see, et sama järjenumbri järgi on võimalik andmeid leida ka teistest massiividest / listidest või teha muud vajalikku vastava indeksiga (näiteks kasutavad seda mõned sorteerimisalgoritmid).

< 7. nädala teemad