Lag enkle algoritmer

Skip to content

Quote

“Algorithm”, a word used by programmers when they don’t want to explain what they did.

Algoritme?

Hva er en algoritme?

En algoritme er en logisk funksjon som utfører en gitt operasjon. Altså, du kan teknisk sett kalle en funksjon som plusser sammen to tall en “algoritme”, men som oftest er en algoritme noe litt mer komplisert enn som så. Ofte blir algoritmer brukt for å gjøre operasjoner som tar mye tid, raskere.

Algorithm Meme

Må jeg bruke Python i disse oppgavene?

Nei! Du kan bruke hvilket som helst programmeringsspråk du foretrekker i disse oppgavene.

Innebygde biblioteker?

Tanken i disse oppgavene er å unngå å bruke innebygde biblioteker eller spesielle Python funksjoner. For eksempel, det finnes en enkel “one-liner” for å reversere tekst: text[::-1], men her vil vi at du prøver å løse slike oppgaver uten å bruke dette. Det kan hende vi nevner en innebygd funksjon dersom løsningen er litt vanskelig å finne på. Dette vil bli markert med ❗.

I praksis så skal det være fullt mulig å løse alle disse oppgavene med if, for, while og vanlige listeoperasjoner.

Hvordan “designe” en algoritme?

Som oftest blir algoritmer designet iterativt. Hva betyr dette?

1. ✅ Bryt først problemet ned i mindre deler.
  • Tenk først å fremst på det aller viktigste du trenger for at algoritmen skal fungere
    • Skal den returnere en verdi? En boolean? En liste?
    • Trenger jeg noen hjelpe-funksjoner?
2. ❓ Er det noen “edge-cases”?
  • Hva skjer dersom du hiver inn en tom liste eller tekst?
3. ✅ Begynn med å bare prøve å lage en løsning
4. ✅ Sjekk om algoritmen virker grei i kjøretid
  • Prøv større input, tar det lang tid?
5. ❓ Tenk på løsningen din, trenger du alle stegene du har brukt?
  • Er alle if-sjekker nødvendige?
  • Hvis du har mer enn en for-loop, finnes det noen klare måter å gjør dette til en for-loop?
    • Dette er forskjellig dersom du har nested loops eller loops etterhverandre. Etterhverandre er ofte mulig å unngå.
6. ✅ Tenk på ekstreme scenarioer med inputs:
  • Eksempel med tall: store tall, små tall, negative tall
  • Teksteksempel: mye tekst, mange små ord, ekstra mellomrom, store og små bokstaver.
7. ❓ Er det nyttig bruke pseudo-kode til å forstå logikken bedre?

Easy Oppgave 1 - Finne ut om en liste inneholder et gitt tall

Lag en algoritme (funksjon) som finner ut om en liste inneholder et gitt tall. Den skal returnere True eller False basert på om tallet eksisterer i listen eller ikke.

Her er en 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. Ta inn en liste og en liste-verdi in en funksjon. I denne oppgaven skal det være tall, men kan være tekst.
  2. Bruk en for-loop til å gå igjennom listen
  3. Hvis tallet er lik sjekke-tallet, returner True
  4. Dersom for-loopen er over og du ikke har funnet 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 Oppgave 2 - Summering

Lag en algoritme som summerer sammen en liste med tall.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], gir svaret 21.
  • [5, 1, 23, 68, 22, 13, 4], gir svaret 136
  • [3, 3, -3, -3, 3] gir svaret 3. Eventuelt så kan du ignorere negative tall å gi svaret 9.
Tips til framgangsmåte
  1. Ta inn en liste i en funksjon
  2. Lagre en midlertidig sum som 0.
  3. Bruk en for-loop for å gå igjennom listen.
  4. return summen av listen.
Svaret (i python) 
def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Medium Oppgave 3a - Maksverdi i en liste

Lag en algoritme som finner den største verdien i en liste.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], gir svaret 6.
  • [6, 17, 227, 1, 23, 42, 12], gir svaret 227
  • [2, -2, 2, -2, -2, 2] gir svaret 2.
Tips til framgangsmåte
  1. Ta inn en liste i en funksjon
  2. Sett en midlertidig verdi til første element i listen.
  3. Bruk en for-loop for å gå igjennom listen å sammenlign med verdien du satt i 2.
  4. Hvis verdien er større sett 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 Oppgave 3b - Hvis listen er tom?

Legg til en sjekk som tester om listen inneholder elementer. Hvis ikke, 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 Oppgave 4 - Telle antall av et gitt element i en liste

Lag en algoritme som teller antallet av et gitt element i en liste.

Test-data for algoritme:
  • ["apple", "banana", "orange", "apple", "apple", "banana"] med apple gir 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 gir svaret 8.
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] med dog gir svaret 3.
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] med 7 gir svaret 5.
  • ["red", "blue", "green", "red", "yellow", "red"] med red gir svaret 3.
  • [10, -2, -2, -2, 5, 10, 10, -2] med -2 gir svaret 4.
Tips til framgangsmåte
  1. Ta inn en liste og en sjekke-verdi i en funksjon
  2. Begynn med en midlertidig telle verdi satt til 0.
  3. Gå igjennom listen med en for-loop.
  4. Hvis elementet er likt med sjekken, øk telle-verdien med 1.
  5. Returner telle-verdien.
Svaret (i python) 
def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

Medium Oppgave 5 - Reversere en string, tekst

Lag en algoritme som reverserer en gitt string.

Test-data for algoritme:
  • Hello there! blir til !ereht olleH.
  • heisann alle sammen blir til nemmas ella nnasieh
  • Python blir til nohtyP
  • racecar blir til racecar
  • 12345abc blir til cba54321
  • god morgen blir til negrom dog
Tips til framgangsmåte
  1. Ta inn en string i en funksjon
  2. Lag en midlertidig verdi for å lagre en tom string.
  3. Gå igjennom tekstne med en for-loop med range. Her kan du gå igjennom listen baklengs, men det går an å løse denne ved å gå framover i listen.
  4. Legg til hver karakter i den midlertidige verdien i rekkefølge.
  5. Returner den midlertidige teksten.
Svaret (i python) 
def reverse(text):
    result = ""
    # Denne linja er litt komplisert, men den starter
    # på slutten, går (inkludert) til 0 (ved å skrive
    # -1 som slutt), og teller nedover med 1 hver gang
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Eventuelt så kan du bruke en algoritme som legger til på begynnelsen i stedet:

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

Medium Oppgave 6 - Palindrom-algoritme

Lag en algoritme som sjekker om et gitt ord er et palindrom. Eksempler på palindromer er abba, racecar, regninger.

Tips til framgangsmåte
  1. Lag en funksjon som tar in tekst å sjekke
  2. Bruk en for-loop til å sjekke om bokstavene på hver side av teksten er like.
  3. Returner False dersom en bokstav ikke stemmer, hvis alle stemmer (for-loopen blir ferdig), returner True.

Ekstra:
Ser du hvordan du kan gjøre algoritmen dobbelt så rask?

Hint

Du trenger bare å 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
Raskere 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 Oppgave 7 - Sjekke om en liste er sortert

Lag en algoritme som sjekker om en liste er sortert. Den letteste måten å sjekke dette på er å begynne fra begynnelsen å sammenligne om neste element er “større”. Dersom et element ikke er “større” så er ikke listen sortert.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], gir svaret True.
  • [6, 17, 227, 1, 23, 42, 12], gir svaret False
  • [2, -2, 2, -2, -2, 2] gir svaret False.
  • [2, 2, 3, 4, 4, 6], gir svaret True.
  • [12, 23, 34, 45, 56, 67], gir svaret True.
Tips til framgangsmåte
  1. Lag en funksjon som tar in en liste
  2. Bruk en for-loop til å gå igjennom hele listen (bruk range til lengden av listen, minus 1 len(list) - 1)
  3. Sammenlign element \(n\) med \(n + 1\), altså nåværende element med neste element.
  4. Hvis \(n\) er mindre enn \(n + 1\), gå til neste sammenligning.
  5. Hvis det ikke er mindre, men større, så er ikke listen sortert. Returner False her.
  6. Hvis du når enden så er listen 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 Oppgave 8 - Shuffle

Lag en algoritme som blander en liste med ting. Det finnes mange måter å gjøre dette på, men en god måte er det som kalles en Fisher-Yates shuffle algorithm. Du kan lese mer om denne her Wikipedia.

Test Data
  • ["a", "b", "c", "d", "e"] → kan bli f.eks. ["c", "e", "a", "d", "b"]
  • [1, 2, 3, 4, 5, 6] → kan bli f.eks. [4, 1, 6, 3, 2, 5]
  • ["apple", "banana", "orange"] → kan bli f.eks. ["orange", "apple", "banana"]
  • ["x"] → blir fortsatt ["x"]
  • [] → blir fortsatt []

Den fungerer slik:

Algoritmen
  1. Lag en funksjon som tar inn listen med tall
  2. Lag en ny tom liste som skal holde på det blanda resultatet.
  3. Bruk en random til å velge en tilfeldig index i listen.
  4. Legg til dette elementet i den tomme listen og slett det fra den gamle
  5. Returner den nye listen fra 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 Oppgave 9 - Bogo-sort

I denne oppgaven skal du lage en (praktisk talt) forferdelig, men ekstremt enkel sorterings-algoritme. Den er ekstremt dårlig når det kommer til store lister (den kommer til å ta evigheter med mer enn 12-13 ting). I Level 2 så skal vi lage en bedre 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 fungerer slik:

Algoritmen
  1. Lag en funksjon som tar inn listen med usorterte tall
  2. Bland listen tilfedlig (bruk shuffle fra oppgave 8).
  3. Sjekk om listen er sortert (bruk sjekken du lagde i oppgave 7).
  4. Hvis listen ikke er sortert, repeter steg 2 og 3.
  5. Repeter helt til listen er sortert, deretter return

Enkelt forklart: bogo-sort blander hele listen og håper på at den er sortert.

Gru bogo sort meme
Les om Big O notation i Level 2.

Hint: Gjerne bruk shuffle fra oppgave 8 til å lage en 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 Oppgave 10a - Søk etter tekst - “substring” (Vanskelig!)

Lag en algoritme som kan finne et søkeord i tekst. Altså, dersom du har en setning som hello there så vil du returnere True med søkeordet hello, False med et 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 en funksjon som tar inn to strings, data og søkeord.
  2. Bruk en for-loop med range til å gå igjennom teksten.
  3. Her er det viktig å tenke på hvor langt loopen skal gå.
  4. Opprett en midlertidig variabel som sier om søkeordet har blitt funnet, sett den til True by default.
  5. Bruk enda en for-loop med range til å sammenligne der du er i teksten med søkeordet.
  6. Hvis noe i søkeordet ikke stemmer med der du sjekker nå, sett den midlertidige variabelen til True og break ut av den indre loopen
  7. Hvis du kommer til slutten av teksten uten å finne noe, 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 Oppgave 10b

Legg også til en ekstra sjekk som passer på at søkeordet ikke er lengre enn setningen.

Tips til framgangsmåte
  • Legg til denne sjekken før for-loopen.
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 Oppgave 11 - Reversering av ord i setning (Vanskelig)

Husk tilbake på Oppgave 5 om å reversere en setning. Gjør om på (eller begynn på nytt), å lag en algoritme som reverserer hvert enkelt ord i en setning, så setter dem sammen igjen.

Test-data for algoritme:
  • hello there everyone blir til olleh ereht enoyreve
  • This is the way it goes! blir til sihT si eht yaw ti !seog
  • does this racecar go? of course! blir til seod siht racecar ?og fo !esruoc
Tips til framgangsmåte
  1. Lag en funksjon som tar inn en string.
  2. ❗Del opp teksten ved å bruke .split(" ").
  3. Lag en midlertidig variabel for å lagre sluttverdien.
  4. Bruk en for-loop til å gå igjennom hvert ord.
  5. Bruk samme metode for reversering som i Oppgave 5
  6. Bruk resultatet å legg til i variablen du lagde 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 Oppgave E1 - Slette duplikater fra en liste

Si du har en liste som inneholder tall, eller tekst, men vi vil slette duplikatene. Lag en algoritme som sletter alle duplikater fra en liste og inneholder kun den første av hvert unike element som eksisterer i lista.

Tips til framgangsmåte
  1. Begynn med en funksjon som tar inn en liste
  2. Her skal vi bruke while-loops i stedet for for. Det gjør det lettere i Python, i andre språk fungerer for med telle-variabler fint.
  3. Opprett en tellevariabel idx (for index, eller i)
  4. Bruk en while loop som skal gå til lengden av listen
  5. Vi vil sammenligne elementet på idx med alle andre elementer
  6. Opprett en tellevariabel til jdx (eller j) som starter på idx + 1
  7. Sammenlign element på idx med element på jdx, hvis de er like, slett jdx med å bruke pop(jdx).
  8. HUSK! Hvis du sletter elementet så blir listen mindre, derfor må vi gå tilbake et steg ved jdx -= 1.
  9. Øk jdx med 1 og test neste element
  10. Etter den indre while-loopen øk idx med 1 og den ytre while-loopen vil fortsette
  11. Returner til slutt listen med slettede duplikater
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 gi: ["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 Oppgave E2 - Counting Sort

Counting sort er en av de få sorterings-algoritmene som fungerer i det vi kaller \(O(n)\) tid. Altså, den tar ikke så veldig mye lengre tid enn antall elementer i lista. Les mer om Big O notation i Level 2.

Det kommer litt an på hvor stort spennet av elementer er. Hvis det minste er 0 og det største er 100000 kan det ta litt tid, så denne kan brukes dersom spennet av verdier er lite. Den fungerer heller ikke for negative tall, men det går an å modifisere algoritmen til å fungere med negative tall.

Algoritmen fungerer slik:

  • Finn ut hvor stort største element er, lagre verdien til dette elementet som \(k\).
  • Lag en liste som inneholder \(k + 1\) elementer, count.
  • Gå igjennom den usorterte listen og bruk verdien til tallet som index. Altså, hvis elementet har verdien 47, så går du til count[47] og øker den med 1.
  • Gå igjennom count listen og plasser antallet tall som indeksen er. Eksempel: Det står 3 på index 1, så legger du til tre 1 tall.
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. Begynn med å lage en funksjon med en liste som input
  2. Lag en tom output liste
  3. Bruk en for-loop til å gå igjennom hele listen
  4. Hold styr på maksverdien i en variabel før for-loopen
  5. Oppdater maksverdien dersom du finner noe større
  6. Lag en liste som inneholder dette antall nuller + 1. Eksempel: største verdi er 47, da lager du en liste med 48 nuller. Dete kan du gjøre med [0] * (maks + 1), eller en for loop. Kall den count.
  7. Gå igjennom listen en gang til med en for-loop
  8. Bruk verdien til elementet som index og øk med 1. count[value] += 1
  9. Bruk en for-loop til å gå igjennom count listen.
  10. Bruk verdien som er på hver index til å legge til det antallet tall
  11. Returner den sorterte listen
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 en haug med nuller
    count = [0] * (max_val + 1)

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

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

    return output