10. Var är robotkatten?

En robotkatt är försvunnen någonstans i Nordopolis och en pojke är jätteledsen! Roboten Else får i uppdrag att hitta den.

När en robotkatt blir rädd gömmer den sig i en städskrubb och stannar där tills någon aktiverar kattens trygghetsprogram. Det gäller att hitta katten så snabbt så möjligt, om den är rädd i mer än 24 timmar måste minnet återställas. Else behöver därför använda en algoritm för att hitta katten så snabbt så möjligt.

Det finns två städskrubbar på varje våningsplan, båda är nära en hiss. Dessa kallas A och B i koden. Else måste leta i alla städskrubbar tills hen har hittat robotkatten.

Katten sågs senast på våning 49, men den kan ha följt med hissarna till andra våningsplan. Att ta hissen mellan två våningar tar oftast 1 minut, men om det är kö och mycket folk kan det ta 10 minuter. Att ta sig mellan städskrubbarna på ett våningsplan tar 7 minuter.

Här ser du två olika algoritmer som Else kan använda för att leta efter katten. Algoritmen avslutas när Else hittar katten. Nu gäller det att välja den algoritm som går snabbast att utföra!

våningAttUndersöka = 48
repetera tills våningAttUndersöka = 1
     undersökStädskrubbA
     undersökStädskrubbB
     våningAttUndersöka = våningAttUndersöka - 1

våningAttUndersöka = 49
repeterat tills våningAttUndersöka = 200
     undersökStädskrubbA
     undersökStädskrubbB     
     våningAttUndersöka = våningAttUndersöka - 1

våningAttUndersöka = 1
repetera tills våningAttUndersöka = 200
     undersökStädskrubbA
     våningAttUndersöka = våningAttUndersöka + 1

repeterat tills våningAttUndersöka = 1
     undersökStädskrubbB     
     våningAttUndersöka = våningAttUndersöka - 1

1. Katten gömmer sig i städskrubb A på våning 40. Hur lång tid tar det för Else att hitta den med algoritm 1: Om hissen alltid tar 10 minuter? Om hissen alltid tar 1 minut? Gör en tabell och skriv in båda dina uträkningar!

2. Om Else istället använder algoritm 2, hur lång tid tar det då att hitta katten? Skriv i tabellen och jämför svaren med förra uppgiften. Vilken algoritm var snabbast om hissen tog 10 minuter? Om den tog 1 minut?

3. Fundera ut en egen algoritm för att leta efter katten. Skriv algoritmen med pseudokod. Fyll sedan i tabellen och se hur lång tid det tar för Else att hitta katten med den nya algoritmen!

Du kan ofta skapa flera olika algoritmer för att lösa ett problem. Olika algoritmer har olika fördelar. Ofta kanske du tittar på vilken som går snabbast, och då kan du undersöka hur lång tid det tar i snittfallet, i bästa fallet och i värsta fallet. I exemplet med kattsökningen beror vad som är bästa och värsta fallet både på var katten gömmer sig och hur lång tid hissarna tar.