Luo yksinkertaisia algoritmeja

Skip to content

Tämä on konekäännetty teksti, joka saattaa sisältää virheitä!

Quote

“Algoritmi”, sana, jota ohjelmoijat käyttävät, kun he eivät halua selittää, mitä he tekivät.

Algoritme?

Mitä algoritmi on?

Algoritmi on looginen funktio, joka suorittaa tietyn operaation. Voit siis teknisesti ottaen kutsua funktiota, joka laskee yhteen kaksi lukua “algoritmiksi”, mutta useimmiten algoritmi on hieman monimutkaisempi. Algoritmeja käytetään usein nopeuttamaan aikaa vieviä operaatioita.

Algorithm Meme

Pitääkö minun käyttää Pythonia näissä tehtävissä?

Ei! Voit käyttää mitä tahansa ohjelmointikieltä, jota haluat näissä tehtävissä.

Sisäänrakennetut kirjastot?

Näiden tehtävien ajatuksena on välttää sisäänrakennettujen kirjastojen tai erityisten Python-funktioiden käyttöä. Esimerkiksi tekstin kääntämiseen on olemassa yksinkertainen “one-liner”: text[::-1], mutta tässä haluamme sinun yrittävän ratkaista tällaiset tehtävät ilman tätä. Ratkaisun löytämisen ollessa hieman vaikeaa, saatamme mainita sisäänrakennetun funktion. Tämä merkitään ❗.

Käytännössä kaikkien näiden tehtävien ratkaiseminen on täysin mahdollista käyttämällä if, for, while ja tavallisia listatoimintoja.

Miten algoritmi “suunnitellaan”?

Useimmiten algoritmit suunnitellaan iteratiivisesti. Mitä tämä tarkoittaa?

1. ✅ Pilko ongelma ensin pienempiin osiin.
  • Mieti ensisijaisesti, mitä algoritmi tarvitsee toimiakseen
    • Palauttaako sen arvon? boolean-arvon? Listan?
    • Tarvitsenko apufunktioita?

2. ❓ Onko olemassa “reunatapauksia”?
  • Mitä tapahtuu, jos syötät tyhjän listan tai tekstin?

3. ✅ Aloita vain yrittämällä luoda ratkaisu

4. ✅ Tarkista, että algoritmi toimii hyvin suoritusaikana
  • Kokeile suurempaa syötettä, kestääkö se kauan?

5. ❓ Mieti ratkaisusi, tarvitsetko kaikki käyttämäsi vaiheet?
  • Ovatko kaikki if-tarkistukset välttämättömiä?
  • Jos sinulla on enemmän kuin yksi for-silmukka, onko olemassa selkeitä tapoja tehdä tästä yksi for-silmukka?
    • Tämä on erilaista, jos sinulla on sisäkkäisiä silmukoita tai silmukoita peräkkäin. Peräkkäiset silmukat ovat usein vältettävissä.

6. ✅ Mieti äärimmäisiä skenaarioita syötteillä:
  • Esimerkki luvuista: suuret luvut, pienet luvut, negatiiviset luvut
  • Tekstiesimerkki: paljon tekstiä, paljon pieniä sanoja, ylimääräisiä välilyöntejä, suuria ja pieniä kirjaimia.

7. ❓ Onko hyödyllistä käyttää pseudo-koodia logiikan ymmärtämisen helpottamiseksi?

Easy Tehtävä 1 – Selvitä, sisältääkö lista tietyn luvun

Luo algoritmi (funktio), joka selvittää, sisältääkö lista tietyn luvun. Sen tulee palauttaa True tai False sen perusteella, onko luku olemassa listassa vai ei.

Tässä on lista testidatalla:

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. Ota lista ja listan arvo funktioon. Tässä tehtävässä on kyse luvuista, mutta se voi olla myös tekstiä.
  2. Käytä for-silmukkaa listan läpikäymiseen
  3. Jos luku on sama kuin tarkistusluku, palauta True
  4. Jos for-silmukka on päättynyt etkä ole löytänyt sitä, palauta False

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

Easy Tehtävä 2 – Summaukset

Luo algoritmi, joka laskee yhteen listan lukuja.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], antaa vastauksen 21.
  • [5, 1, 23, 68, 22, 13, 4], antaa vastauksen 136
  • [3, 3, -3, -3, 3] antaa vastauksen 3. Mahdollisesti voit jättää huomiotta negatiiviset luvut ja antaa vastauksen 9.

Tips til framgangsmåte
  1. Ota lista funktioon
  2. Tallenna väliaikainen summa arvoon 0.
  3. Käytä for-silmukkaa listan läpikäymiseen.
  4. return listan summa.

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

Medium Tehtävä 3a – Listan maksimiarvo

Luo algoritmi, joka löytää listan suurimman arvon.

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

Tips til framgangsmåte
  1. Ota lista funktioon
  2. Aseta väliaikainen arvo listan ensimmäiselle elementille.
  3. Käytä for-silmukkaa käydäksesi läpi listan ja vertaa sitä arvoon, jonka asetit kohdassa 2.
  4. Jos arvo on suurempi, aseta väliaikainen arvo uuteen arvoon.
  5. return tämä väliaikainen arvo.

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

    return largest

Easy Tehtävä 3b – Jos lista on tyhjä?

Lisää tarkistus, joka testaa, sisältääkö lista elementtejä. Jos ei, palauta 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 Tehtävä 4 – Laske tietyn alkion lukumäärä listassa

Luo algoritmi, joka laskee tietyn alkion lukumäärän listassa.

Test-data for algoritme:
  • ["apple", "banana", "orange", "apple", "apple", "banana"] med apple antaa vastauksen 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 antaa vastauksen 8.
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] med dog antaa vastauksen 3.
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] med 7 antaa vastauksen 5.
  • ["red", "blue", "green", "red", "yellow", "red"] med red antaa vastauksen 3.
  • [10, -2, -2, -2, 5, 10, 10, -2] med -2 antaa vastauksen 4.

Tips til framgangsmåte
  1. Ota lista ja tarkistusarvo funktioon
  2. Aloita väliaikaisella laskurilla, joka on asetettu arvoon 0.
  3. Käy läpi lista for-silmukalla.
  4. Jos elementti on sama kuin tarkistus, lisää laskurin arvoa yhdellä.
  5. Palauta laskurin arvo.

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

    return count

Medium Tehtävä 5 – Merkkijonon kääntäminen

Luo algoritmi, joka kääntää annetun merkkijonon.

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

Tips til framgangsmåte
  1. Ota string sisään funktioon
  2. Luo väliaikainen arvo tyhjän string:in tallentamista varten.
  3. Käy teksti läpi for-silmukalla range:n avulla. Voit käydä listaa taaksepäin, mutta tämän voi ratkaista myös menemällä eteenpäin listassa.
  4. Lisää jokainen merkki väliaikaiseen arvoon järjestyksessä.
  5. Palauta väliaikainen teksti.

Svaret (i python) 
def reverse(text):
    result = ""
    # Tämä rivi on hieman monimutkainen, mutta se alkaa
    # lopusta, menee (mukaan lukien) 0:aan (kirjoittamalla
    # -1 lopuksi) ja laskee alaspäin yhdellä kerrallaan
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Tarvittaessa voit käyttää algoritmia, joka lisää alkuun sen sijaan:

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # lisää alkuun sen sijaan
       result = text[i] + result
   return result

Medium Tehtävä 6 – Palindromialgoritmi

Luo algoritmi, joka tarkistaa, onko annettu sana palindromi. Esimerkkejä palindromeista ovat abba, racecar, regninger.

Tips til framgangsmåte
  1. Luo funktio, joka ottaa vastaan tarkistettavan tekstin.
  2. Käytä for-silmukkaa tarkistaaksesi, ovatko tekstin kummankin puolen kirjaimet samoja.
  3. Palauta False, jos jokin kirjain ei täsmää. Jos kaikki täsmäävät (for-silmukka päättyy), palauta True.

Lisä:
Näetkö, miten voit tehdä algoritmista kaksinkertaisesti nopeamman?

Hint

Sinun tarvitsee tarkistaa vain puolet!

Vastaus (pythonilla) 
def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True
Nopeampi algoritmi

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 Tehtävä 7 – Tarkista, onko lista lajiteltu

Luo algoritmi, joka tarkistaa, onko lista lajiteltu. Helpoin tapa tarkistaa tämä on aloittaa alusta ja verrata, onko seuraava alkio “suurempi”. Jos alkio ei ole “suurempi”, lista ei ole lajiteltu.

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

Tips til framgangsmåte
  1. Luo funktio, joka ottaa vastaan listan
  2. Käytä for-silmukkaa käydäksesi läpi koko listan (käytä range-funktiota listan pituuteen miinus 1 len(list) - 1)
  3. Vertaa elementtiä \(n\) elementtiin \(n + 1\), eli nykyistä elementtiä seuraavaan elementtiin.
  4. Jos \(n\) on pienempi kuin \(n + 1\), siirry seuraavaan vertailuun.
  5. Jos se ei ole pienempi, vaan suurempi, lista ei ole lajiteltu. Palauta False tässä.
  6. Jos pääset loppuun, lista on lajiteltu, palauta 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 Tehtävä 8 – Sekoitus

Luo algoritmi, joka sekoittaa listan asioita. Tähän on monia tapoja, mutta hyvä tapa on ns. Fisher-Yates shuffle -algoritmi. Voit lukea lisää tästä täältä Wikipedia.

Test Data
  • ["a", "b", "c", "d", "e"] → voi esimerkiksi muuttua ["c", "e", "a", "d", "b"]
  • [1, 2, 3, 4, 5, 6] → voi esimerkiksi muuttua [4, 1, 6, 3, 2, 5]
  • ["apple", "banana", "orange"] → voi esimerkiksi muuttua ["orange", "apple", "banana"]
  • ["x"] → pysyy edelleen ["x"]
  • [] → pysyy edelleen []

Se toimii näin:

Algoritmen
  1. Luo funktio, joka ottaa vastaan numerolistan.
  2. Luo uusi tyhjä lista, joka pitää sekoitetun tuloksen.
  3. Käytä random-funktiota valitaksesi satunnaisen indeksin listasta.
  4. Lisää tämä elementti tyhjään listaan ja poista se vanhasta listasta.
  5. Palauta uusi lista funktiosta.

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 Tehtävä 9 – Bogo-sort

Tässä tehtävässä luot (käytännössä) kauhean, mutta erittäin yksinkertaisen lajittelualgoritmin. Se on erittäin huono suurten listojen kanssa (se kestää ikuisuuden yli 12-13 elementillä). Level 2:ssa luomme paremman lajittelualgoritmin, bubble-sortin.

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]

Algoritmi toimii seuraavasti:

Algoritmen
  1. Luo funktio, joka ottaa vastaan lajittelemattomien lukujen listan
  2. Sekoita lista satunnaisesti (käytä tehtävästä 8 shuffle-funktiota).
  3. Tarkista, onko lista lajiteltu (käytä tehtävässä 7 luomaasi tarkistusta).
  4. Jos lista ei ole lajiteltu, toista vaiheet 2 ja 3.
  5. Toista, kunnes lista on lajiteltu, ja palauta sitten

Yksinkertaisesti selitettynä: bogo-sort sekoittaa koko listan ja toivoo, että se on lajiteltu.

Gru bogo sort meme
Lue Big O -notaatiosta Level 2:ssa.

Vinkki: Käytä mielellään tehtävästä 8 saatua shuffle-funktiota luodaksesi algoritmillesi järjestämätön lista.

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

Hard Tehtävä 10a – Tekstin etsiminen – “substring” (Vaikea!)

Luo algoritmi, joka voi etsiä avainsanan tekstistä. Eli jos sinulla on lause, kuten hello there, haluat palauttaa True avainsanalla hello ja False avainsanalla hahah. Tämän algoritmin tulee toimia kaikilla syötteillä ja tulosteilla.

Käytä alla olevaa tekstiaineistoa tarkistaaksesi, toimiiko algoritmisi.

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. Luo funktio, joka ottaa sisään kaksi string-muuttujaa, data ja hakusana.
  2. Käytä for-silmukkaa range-funktiolla käydäksesi läpi tekstin.
  3. Tässä on tärkeää miettiä, kuinka pitkälle silmukan tulee mennä.
  4. Luo väliaikainen muuttuja, joka kertoo, onko hakusana löydetty, aseta se oletusarvoisesti True.
  5. Käytä toista for-silmukkaa range-funktiolla verrataksesi, missä olet tekstissä, hakusanaan.
  6. Jos jokin hakusanassa ei täsmää tarkastamasi kohdan kanssa, aseta väliaikainen muuttuja arvoon True ja break poistu sisemmästä silmukasta.
  7. Jos pääset tekstin loppuun löytämättä mitään, palauta 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 Tehtävä 10b

Lisää myös ylimääräinen tarkistus, joka varmistaa, että hakusana ei ole pidempi kuin lause.

Vinkkejä toimintatapaan
  • Lisää tämä tarkistus ennen for-silmukkaa.

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 Tehtävä 11 – Lauseen sanojen kääntäminen (Vaikea)

Muista tehtävä 5, jossa käännettiin lause. Muokkaa (tai aloita alusta) algoritmi, joka kääntää jokaisen yksittäisen sanan lauseessa ja yhdistää ne sitten uudelleen.

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

Tips til framgangsmåte
  1. Luo funktio, joka ottaa vastaan string:in.
  2. ❗Jaa teksti käyttämällä .split(" ").
  3. Luo väliaikainen muuttuja lopullisen arvon tallentamista varten.
  4. Käytä for-silmukkaa käydäksesi läpi jokainen sana.
  5. Käytä samaa menetelmää kääntämiseen kuin Tehtävässä 5
  6. Käytä tulosta ja lisää se vaiheessa 2 luomaasi muuttujaan.
  7. Palauta lopullinen arvo

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

➕Lisää:

Cracked Tehtävä E1 – Duplikaattien poistaminen listasta

Oletetaan, että sinulla on lista, joka sisältää lukuja tai tekstiä, mutta haluat poistaa duplikaatit. Luo algoritmi, joka poistaa kaikki duplikaatit listasta ja sisältää vain ensimmäisen jokaisesta listassa esiintyvästä yksilöllisestä elementistä.

Tips til framgangsmåte
  1. Aloita funktiolla, joka ottaa vastaan listan
  2. Tässä käytämme while-silmukoita for-silmukoiden sijaan. Se helpottaa Pythonissa, muissa kielissä for toimii hyvin laskurimuuttujien kanssa.
  3. Luo laskurimuuttuja idx (lyhenne sanasta index, tai i)
  4. Käytä while-silmukkaa, joka käy listan pituuden läpi
  5. Vertaamme elementtiä kohdassa idx kaikkiin muihin elementteihin
  6. Luo laskurimuuttuja jdx (tai j), joka alkaa kohdasta idx + 1
  7. Vertaile elementtiä kohdassa idx elementtiin kohdassa jdx. Jos ne ovat samoja, poista jdx käyttämällä pop(jdx).
  8. MUISTA! Jos poistat elementin, lista lyhenee, joten meidän on siirryttävä yksi askel taaksepäin kohdassa jdx -= 1.
  9. Lisää jdx:ää yhdellä ja testaa seuraava elementti
  10. Sisemmän while-silmukan jälkeen lisää idx:ää yhdellä ja ulompi while-silmukka jatkaa
  11. Palauta lopuksi lista, josta on poistettu kaksoiskappaleet

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"]
    • Antaa: ["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 Tehtävä E2 - Laskentajärjestäminen

Laskentajärjestäminen on yksi harvoista lajittelualgoritmeista, jotka toimivat siinä, mitä kutsumme \(O(n)\) ajassa. Eli se ei kestä juurikaan kauemmin kuin listan elementtien määrä. Lue lisää Big O -merkinnästä Level 2:ssa.

Se riippuu hieman siitä, kuinka suuri elementtien vaihteluväli on. Jos pienin on 0 ja suurin 100000, se voi viedä hieman aikaa, joten tätä voidaan käyttää, jos arvojen vaihteluväli on pieni. Se ei myöskään toimi negatiivisilla luvuilla, mutta algoritmia voidaan muokata toimimaan negatiivisilla luvuilla.

Algoritmi toimii seuraavasti:

  • Selvitä suurin elementti, tallenna tämän elementin arvo \(k\):ksi.
  • Luo lista, joka sisältää \(k + 1\) elementtiä, count.
  • Käy läpi lajittelematon lista ja käytä luvun arvoa indeksinä. Eli jos elementin arvo on 47, siirry kohtaan count[47] ja lisää sitä yhdellä.
  • Käy läpi count-lista ja sijoita indeksin määrä lukuja. Esimerkki: Jos indeksissä 1 on 3, lisää kolme 1-lukua.

Testdata
Lajittelematon Data Lajiteltu 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. Aloita luomalla funktio, joka ottaa sisään listan
  2. Luo tyhjä output lista
  3. Käytä for-silmukkaa käydäksesi läpi koko listan
  4. Pidä kirjaa maksimiarvosta muuttujassa ennen for-silmukkaa
  5. Päivitä maksimiarvo, jos löydät jotain suurempaa
  6. Luo lista, joka sisältää tämän määrän nollia + 1. Esimerkki: suurin arvo on 47, jolloin luot listan, jossa on 48 nollaa. Voit tehdä tämän [0] * (maks + 1) -koodilla tai for-silmukalla. Kutsu sitä count.
  7. Käy läpi lista uudelleen for-silmukalla
  8. Käytä elementin arvoa indeksinä ja lisää 1. count[value] += 1
  9. Käytä for-silmukkaa käydäksesi läpi count listan.
  10. Käytä kunkin indeksin arvoa lisätäksesi sen määrän lukuja
  11. Palauta lajiteltu 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

    # tämä luo kasan nollia
    count = [0] * (max_val + 1)

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

    for i in range(len(count)):
        # käytä _ arvon jättämiseen huomiotta
        for _ in range(count[i]):
            output.append(i)

    return output