Lag enkle algoritmar,

Skip to content

Dette er ein maskinomsett tekst som kann innehalda feil!

Quote

«Algoritme», eit ord programmerar nyttar når dei ikkje vil forklåra kva dei har gjort.

Algoritme?

Kva er ein algoritme?

Ein algoritme er ein logisk funksjon som utfører ein gjeven operasjon. Altså, du kan teknisk sett kalla ei funksjon som plussar saman to tal ein «algoritme», men som oftast er ein algoritme noko litt meir komplisert enn som så. Ofte vert algoritmar brukte for å gjera operasjonar som tek mykje tid, raskare.

Algorithm Meme

Må eg bruka Python i desse oppgåvene?

Nei! Du kan bruka kvart som helst programmeringsspråk du føretrekk i desse oppgåvene.

Innebygde bibliotek?

Tanken i desse oppgåvene er å unngå å bruke innebygde bibliotek eller spesielle Python funksjonar. Til dømes, det finst ein enkel «one-liner» for å reversere tekst: text[::-1], men her vil me at du prøver å løyse slike oppgåver utan å bruke dette. Det kan hende me nemner ein innebygd funksjon dersom løysinga er litt vanskeleg å finne på. Dette vil verte markert med ❗.

I praksis, so skal det vera fullt mogleg å løyse alle desse oppgåvene med if, for, while og vanlege listeoperasjonar.

Korleis «designe» ein algoritme?

Som oftast vert algoritmar designa iterativt. Kva tyder dette?

1. ✅ Bryt fyrst problemet ned i mindre delar.
  • Tenk fyrst å fremst på det aller viktigaste du treng for at algoritmen skal fungera
    • Skal han returnera ein verdi? Ein boolean? Ei liste?
    • Treng eg nokon hjelpe-funksjonar?

2. ❓ Er der nokon «edge-cases»?
  • Kva hender dersom du kastar inn ei tom liste eller tekst?

3. ✅ Byrja med å berre prøva å laga ein løysing

4. ✅ Sjå um algoritmen hev ein god fart i kjøretida
  • Prøv større innmat, tek det lang tid?

5. ❓ Hugs på løysinga di, treng du alle stega du har brukt?
  • Er alle if-sjekkar naudsynte?
  • Um du har meir enn ein for-lykkje, finst det nokre klåre måtar å gjera dette til ein for-lykkje?
    • Dette er ulikt dersom du har nestla lykkjer eller lykkjer etter kvarandre. Etter kvarandre er ofte mogleg å unngå.

6. ✅ Hugs på ekstreme scenarium med inputs:
  • Døme med tal: store tal, små tal, negative tal
  • Tekstdøme: mykje tekst, mange små ord, ekstra mellomrom, store og små bokstavar.

7. ❓ Er det nytto å bruka pseudo-kode til å forstå logikken betre?

Easy Oppgåve 1 – Finna ut om ei liste inneheld eit gjeve tal

Lag ein algoritme (funksjon) som finn ut om ei liste inneheld eit gjeve tal. Han skal returnera True eller False basert på om talet eksisterer i lista eller ikkje.

Her er ei liste med test-data:

Test-data for algoritme:
Test-Data Sjekk Svar
[1, 2, 3, 4, 5, 6, 7, 8, 9] 5 True
[1, 2, 3, 4, 5, 6, 7, 8, 9] 10 False
[2, 3, 5, 7, 11, 13, 17, 19, 23] 2 True
[2, 3, 5, 7, 11, 13, 17, 19, 23] 10 False
[-1, 0, 1, -34, 321, 22, 98, -214] -214 True
[-1, 0, 1, -34, 321, 22, 98, -214] 0 True
[-1, 0, 1, -34, 321, 22, 98, -214] 2 False

Tips til framgangsmåte
  1. Tak inn ei liste og ei liste-verdi inn i ei funksjon. I denne oppgåva skal det vera tal, men kan vera tekst.
  2. Bruk ei for-lykkje til å gå gjennom lista
  3. Um talet er lik sjekketalet, returner True
  4. Dersom for-lykkja er over og du ikkje har funne det, returner False

Svaret (i python) 
def exists_in_list(the_list, check):
    for number in the_list:
        if number == check:
            return True
    return False

Easy Oppgåve 2 - Summering

Lag ein algoritme som summerer ihop ei liste med tal.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], gjev svaret 21.
  • [5, 1, 23, 68, 22, 13, 4], gjev svaret 136
  • [3, 3, -3, -3, 3] gjev svaret 3. Eventuelt so kann du ignorera negative tal å gjeva svaret 9.

Tips til framgangsmåte
  1. Tak inn ei liste i ei funksjon
  2. Lagra ei midlertidig sum som 0.
  3. Bruk ei for-lykkje for å gå gjennom lista.
  4. return summen av lista.

Svaret (i python) 
def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Medium Oppgåve 3a – Største verdi i ei liste

Lag ein algoritme som finn den største verdien i ei liste.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], gjev svaret 6.
  • [6, 17, 227, 1, 23, 42, 12], gjev svaret 227
  • [2, -2, 2, -2, -2, 2] gjev svaret 2.

Tips til framgangsmåte
  1. Tak inn ei liste i ei funksjon
  2. Set ei midlertidig verdi til fyrste elementet i lista.
  3. Bruk ei for-lykkje for å gå igjennom lista og samanlikn med verdien du sette i 2.
  4. Um verdien er større, set den midlertidige verdien til den nye verdien.
  5. return denne midlertidige verdien.

Svaret (i python) 
def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Easy Uppgåve 3b – Um lista er tom?

Legg til ein prøve som testar um lista inneheld element. Um ikkje, returner None.

Svaret (i python) 
def find_max(numbers):
    if len(numbers) == 0:
        return None

    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Easy Oppgåve 4 – Telja talet av eit gjeve element i ei liste

Lag ein algoritme som tel talet av eit gjeve element i ei liste.

Test-data for algoritme:
  • ["apple", "banana", "orange", "apple", "apple", "banana"] med apple gjev svaret 3.
  • [1, 4, 5, 2, 4, -3, -4, 4, 2, 4, 221, 3, 1, 1, 4, 1, 12, 33, 4, 4, 2, -4, 1, 4] med 4 gjev svaret 8.
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] med dog gjev svaret 3.
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] med 7 gjev svaret 5.
  • ["red", "blue", "green", "red", "yellow", "red"] med red gjev svaret 3.
  • [10, -2, -2, -2, 5, 10, 10, -2] med -2 gjev svaret 4.

Tips til framgangsmåte
  1. Tak inn ei liste og ei sjekkeverdi i ei funksjon
  2. Byrj med ei midlertidig teljeverdi sett til 0.
  3. Gå igjennom lista med ei for-lykkje.
  4. Um elementet er likt med sjekken, auk teljeverdien med 1.
  5. Returner teljeverdien.

Svaret (i python) 
def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

Medium Oppgåve 5 – Vende ein streng, tekst

Lag ein algoritme som vender ein gjeven streng.

Test-data for algoritme:
  • Hello there! vert til !ereht olleH.
  • heisann alle sammen vert til nemmas ella nnasieh
  • Python vert til nohtyP
  • racecar vert til racecar
  • 12345abc vert til cba54321
  • god morgen vert til negrom dog

Tips til framgangsmåte
  1. Tak inn ein string i ei funksjon
  2. Lag ei mellombels verdi for å lagra ein tom string.
  3. Gå igjennom tekstane med ein for-løkke med range. Her kan du gå igjennom lista baklengs, men det går an å løysa denne ved å gå framover i lista.
  4. Legg til kvar karakter i den mellombelse verdien i rekkefølge.
  5. Returner den mellombelse teksten.

Svaret (i python) 
def reverse(text):
    result = ""
    # Denne linja er litt komplisert, men ho startar
    # på slutten, går (inkludert) til 0 (ved å skrive
    # -1 som slutt), og tel nedover med 1 kvar gong
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Eventuelt so kann du bruke ein algoritme som legg til på byrjinga i staden:

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # legg til på byrjinga i staden
       result = text[i] + result
   return result

Medium Oppgåve 6 – Palindrom-algoritme

Lag ein algoritme som sjekkar om eit gjeve ord er eit palindrom. Døme på palindrom er abba, racecar, regninger.

Tips til framgangsmåte
  1. Lag ei funksjon som tek inn tekst å sjekke
  2. Bruk ei for-løkke til å sjekke om bokstavane på kvar side av teksten er like.
  3. Returner False dersom ei bokstav ikkje stemmer, viss alle stemmer (for-løkka blir ferdig), returner True.

Ekstra:
Ser du korleis du kan gjere algoritmen dobbelt så rask?

Hint

Du treng berre å sjekke halvparten!

Svaret (i python) 
def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True
Raskare algoritme

def palindrome(text):
for i in range(0, int(len(text) / 2)):
if text[i] != text[len(text) - i - 1]:
return False
return True

Medium Oppgåve 7 – Sjekke um ei liste er sortert

Lag ein algoritme som sjekkar um ei liste er sortert. Den lettaste måten å sjekke dette på er å byrja frå byrjinga å samanlikne um neste element er «større». Dersom eit element ikkje er «større» så er ikkje lista sortert.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], gjev svaret True.
  • [6, 17, 227, 1, 23, 42, 12], gjev svaret False
  • [2, -2, 2, -2, -2, 2] gjev svaret False.
  • [2, 2, 3, 4, 4, 6], gjev svaret True.
  • [12, 23, 34, 45, 56, 67], gjev svaret True.

Tips til framgangsmåte
  1. Lag ei funksjon som tek inn ei liste
  2. Bruk ei for-lykkje til å gå gjennom heile lista (bruk range til lengda av lista, minus 1 len(list) - 1)
  3. Samanlikn element \(n\) med \(n + 1\), altså noverande element med neste element.
  4. Um \(n\) er mindre enn \(n + 1\), gå til neste samanlikning.
  5. Um det ikkje er mindre, men større, så er ikkje lista sortert. Returner False her.
  6. Um du når enden, så er lista sortert, returner True.

Svaret (i Python) 
def is_sorted(the_list):
    for i in range(len(the_list) - 1):
        if the_list[i] > the_list[i + 1]:
            return False
    return True

Medium Oppgåve 8 - Blanding

Lag ein algoritme som blandar ei liste med ting. Det finst mange måtar å gjera dette på, men ein god måte er det som vert kalla ein Fisher-Yates shuffle algoritme. Du kan lesa meir om denne her Wikipedia.

Test Data
  • ["a", "b", "c", "d", "e"] → kan verte t.d. ["c", "e", "a", "d", "b"]
  • [1, 2, 3, 4, 5, 6] → kan verte t.d. [4, 1, 6, 3, 2, 5]
  • ["apple", "banana", "orange"] → kan verte t.d. ["orange", "apple", "banana"]
  • ["x"] → vert framleis ["x"]
  • [] → vert framleis []

Han verkar slik:

Algoritmen
  1. Lag ei funksjon som tek inn lista med tal
  2. Lag ei ny tom liste som skal halda på det blanda resultatet.
  3. Bruk ein random til å velja ein tilfeldig indeks i lista.
  4. Legg til dette elementet i den tomme lista og slett det frå den gamle
  5. Returner den nye lista frå funksjonen

Svaret (i Python) 
import random

def shuffle(the_list):
    shuffled = []

    while len(the_list) > 0:
        i = random.randrange(0, len(the_list))
        shuffled.append(the_list[i])
        the_list.pop(i)

    return shuffled

Medium Oppgåve 9 - Bogo-sort

I denne oppgåva skal du lage ein (praktisk talt) forferdeleg, men ekstremt enkel sorterings-algoritme. Han er ekstremt dårleg når det gjeld til store lister (han kjem til å taka evigheter med meir enn 12-13 ting). I Level 2 så skal me laga ein betre sorterings-algoritme, bubble-sort.

Test Data
  • [3, 1, 2] → [1, 2, 3]
  • [5, 4, 3, 2, 1] → [1, 2, 3, 4, 5]
  • [10, 7, 8, 2] → [2, 7, 8, 10]
  • [1, 1, 1] → [1, 1, 1]
  • [9, 3, 6, 3, 9] → [3, 3, 6, 9, 9]
  • [0, -1, 4, -2] → [-2, -1, 0, 4]

Algoritmen verkar slik:

Algoritmen
  1. Lag ei funksjon som tek inn lista med usorterte tal
  2. Bland lista tilfeldig (bruk shuffle frå oppgåve 8).
  3. Sjekk om lista er sortert (bruk sjekken du laga i oppgåve 7).
  4. Um lista ikkje er sortert, gjenta steg 2 og 3.
  5. Gjentak heilt til lista er sortert, deretter returner

Enkelt forklart: bogo-sort blandar heile lista og vonar på at ho er sortert.

Gru bogo sort meme
Les um Big O notasjon i Nivå 2.

Hint: Gjerne bruk shuffle frå oppgåve 8 til å laga ei usortert liste for algoritmen din.

Svaret (i Python) 
def bogo_sort(the_list):
    while not is_sorted(the_list):
        the_list = shuffle(the_list)
    return the_list

Hard Oppgåve 10a – Søk etter tekst – «substring» (Vanskelig!)

Lag ein algoritme som kann finne eit søkeord i tekst. Altså, dersom du har ei setning som hello there så vil du returnere True med søkeordet hello, False med eit søkeord som hahah. Denne algoritmen skal fungere uansett input og output.

Bruk tekst-dataen under til å sjekke om algoritmen din fungerer.

Test-data for algoritme:
  • hello there everyone med there = True
  • hello there everyone med ever = True
  • hello there everyone med then = False
  • qwecvyufavsjekkftyergwcery med sjekk = True

Tips til framgangsmåte
  1. Lag ei funksjon som tek inn to stringar, data og søkeord.
  2. Bruk ei for-løkke med range til å gå gjennom teksten.
  3. Her er det viktig å tenkje på kor langt løkka skal gå.
  4. Opprett ei midlertidig variabel som seier om søkeordet har vorte funne, sett ho til True by default.
  5. Bruk endå ei for-løkke med range til å samanlikne der du er i teksten med søkeordet.
  6. Um noko i søkeordet ikkje stemmer med der du sjekkar no, sett den midlertidige variabelen til True og break ut av den indre løkka
  7. Um du kjem til slutten av teksten utan å finne noko, returner False

Svaret (i Python) 
def search(data, word): 
    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Easy Oppgåve 10b

Legg òg til ein ekstra kontroll som passar på at søkeordet ikkje er lengre enn setningi.

Tips til framgangsmåte
  • Legg til denne kontrollen før for-lykkja.

Svaret (i python) 
def search(data, word): 
    if len(word) > len(data):
        return False

    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Hard Oppgåve 11 - Reversering av ord i setning (Vanskelig)

Hugsa attende til Oppgåve 5 um å reversera ei setning. Gjør um på (eller byrja på nytt), å lag ein algoritme som reverserer kvart eit ord i ei setning, so set dei saman att.

Test-data for algoritme:
  • hello there everyone vert til olleh ereht enoyreve
  • This is the way it goes! vert til sihT si eht yaw ti !seog
  • does this racecar go? of course! vert til seod siht racecar ?og fo !esruoc

Tips til framgangsmåte
  1. Lag ei funksjon som tek inn ei string.
  2. ❗Del opp teksten ved å bruke .split(" ").
  3. Lag ei mellombels variabel for å lagra sluttverdien.
  4. Bruk ei for-løkke til å gå gjennom kvart ord.
  5. Bruk same metoden for reversering som i Oppgåve 5
  6. Bruk resultatet og legg til i variabelen du laga i steg 2.
  7. Returner sluttverdien

Svaret (i Python) 
def reverse_words(words):
    sentence = words.split(" ")
    output = ""

    for word in sentence:
        reversed_word = ""
        for i in range(0, len(word)):
            reversed_word = word[i] + reversed_word
        output += reversed_word + " "

    return output

➕ Ekstra:

Cracked Oppgåve E1 – Slette duplikatar frå ei liste

Sagt at du hev ei liste som innhald tall, eller tekst, men me vil slette duplikatarne. Lag ein algoritme som slettar alle duplikatar frå ei liste og innhald berre den fyrste av kvart unikt element som eksisterer i lista.

Tips til framgangsmåte
  1. Byrj med ein funksjon som tek inn ei liste
  2. Her skal me bruke while-løkker i staden for for. Det gjer det lettare i Python, i andre språk fungerer for med telje-variablar fint.
  3. Opprett ei teljevariabel idx (for indeks, eller i)
  4. Bruk ei while-løkke som skal gå til lengda av lista
  5. Me vil samanlikne elementet på idx med alle andre element
  6. Opprett ei teljevariabel til jdx (eller j) som startar på idx + 1
  7. Samanlikn element på idx med element på jdx, viss dei er like, slett jdx ved å bruke pop(jdx).
  8. HUGSA! Hvis du slettar elementet så blir lista mindre, derfor må me gå tilbake eit steg ved jdx -= 1.
  9. Auka jdx med 1 og test neste element
  10. Etter den indre while-løkka auka idx med 1 og den ytre while-løkka vil fortsette
  11. Returner til slutt lista med sletta duplikatar

Test Data
  • [1, 2, 2, 3, 1, 4, 3] → blir [1, 2, 3, 4]
  • ["a", "b", "a", "c", "b", "d"] → blir ["a", "b", "c", "d"]
  • [5, 5, 5, 5] → blir [5]
  • ["x", "y", "z", "x", "y", "x"] → blir ["x", "y", "z"]
  • [10, -1, 10, -1, 0, 0, 10] → blir [10, -1, 0]
  • ["apple", "apple', "banana", "orange", "apple", "orange", "pear", "apple"]
    • Skal gjeva: ["apple", "banana", "orange", "pear"]

Svaret (i Python) 
def delete_duplicates(the_list):
    idx = 0

    while idx < len(the_list):
        jdx = idx + 1

        while jdx < len(the_list):
            if the_list[idx] == the_list[jdx]:
                the_list.pop(jdx)
                jdx -= 1
            jdx += 1
        idx += 1

    return the_list

Cracked Oppgåve E2 - Counting Sort

Counting sort er ein av dei få sorterings-algoritmene som verkar i det me kallar \(O(n)\) tid. Altså, han tek ikkje så veldig mykje lengre tid enn talet på element i lista. Les meir om Big O notasjon i Level 2.

Det kjem litt an på kor stort spennet av element er. Dersom det minste er 0 og det største er 100000 kan det taka litt tid, så denne kan brukast dersom spennet av verdiar er lite. Han fungerer heller ikkje for negative tal, men det går an å modifisera algoritmen til å fungera med negative tal.

Algoritmen fungerer slik:

  • Finn ut kor stort største element er, lagre verdien til dette elementet som \(k\).
  • Lag ei liste som inneheld \(k + 1\) element, count.
  • Gå igjennom den usorterte lista og bruk verdien til talet som indeks. Altså, dersom elementet har verdien 47, så går du til count[47] og aukar den med 1.
  • Gå igjennom count lista og plasser talet på tal som indeksen er. Døme: Det står 3 på indeks 1, så legg du til tre 1 tal.

Testdata
Usortert Data Sortert Data
[7, 3, 9, 1, 4, 3, 0, 6, 8, 6, 2, 1, 9, 0, 5, 4] [0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9]
[12, 13, 15, 0, 8, 15, 8, 5, 16, 8, 0, 20, 4, 9, 17, 16, 1, 3, 6, 15, 5, 2, 3, 1, 19, 13, 17, 5, 3, 10] [0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 8, 8, 8, 9, 10, 12, 13, 13, 15, 15, 15, 16, 16, 17, 17, 19, 20]

Tips til framgangsmåte
  1. Byrj med å lage ein funksjon med ei liste som innspel
  2. Lag ei tom output liste
  3. Bruk ei for-lykkje til å gå gjennom heile lista
  4. Halde styr på maksverdien i ein variabel før for-lykkja
  5. Oppdater maksverdien dersom du finn noko større
  6. Lag ei liste som inneheld dette talet nullar + 1. Døme: største verdi er 47, då lagar du ei liste med 48 nullar. Dette kan du gjere med [0] * (maks + 1), eller ei for lykkje. Kall den count.
  7. Gå gjennom lista ein gong til med ei for-lykkje
  8. Bruk verdien til elementet som indeks og auk med 1. count[value] += 1
  9. Bruk ei for-lykkje til å gå gjennom count lista.
  10. Bruk verdien som er på kvar indeks til å leggje til det talet tall
  11. Returner den sorterte lista

Svaret (i Python) 
def counting_sort(input_list):
    output = []

    max_val = input_list[0]

    for n in input_list:
        if n > max_val:
            max_val = n

    # dette vil lage ein haug med nullar
    count = [0] * (max_val + 1)

    for n in input_list:
        count[n] += 1

    for i in range(len(count)):
        # bruk _ for å ignorere ein verdi
        for _ in range(count[i]):
            output.append(i)

    return output