Programmeringens grunder

Kapitel 8: Sökprogram

Eftersom datorer är effektiva kan vi lösa flera uppgifter automatiskt genom att gå igenom alla möjliga lösningar och välja en lösning som uppfyller de önskade villkoren.

Gåta 1

Vi börjar med att lösa följande gåta:

Vi vet att Maija är fem år yngre än Uolevi och om vi dessutom multiplicerar deras åldrar med varandra får vi talet 594. Hur gamla är Maija och Uolevi?

För att vi ska kunna lösa gåtan måste vi ge den en form som datorn kan förstå. I detta fall kan vi beteckna Maijas ålder med x, vilket betyder att Uolevis ålder är x+5. Vi vill söka en lösning där villkoret x*(x+5) == 594 gäller.

Följande program söker lösningen på gåtan genom att gå igenom alla alternativ för Maijas ålder med hjälp av slingan. Programmet antar att Maija är minst 0 år och mindre än 120 år, dvs. programmet går igenom värdena 0...119 för x. Programmet kontrollerar om gåtans villkor gäller för varje ålder och om det gäller skriver programmet ut åldrarna.

for x in range(120):
    if x*(x+5) == 594:
        print(x,x+5)

När vi kör programmet får vi följande resultat:

22 27

Detta betyder att Maija är 22 år gammal och Uolevi är 27 år gammal. Det stämmer att 27–22 = 5 och 22*27 = 594, dvs. lösningen är korrekt.

Gåta 2

Låt oss lösa en gåta till:

Liisa har en påse kulor. Om hon delar kulorna i fyra grupper blir tre kulor över. Om hon delar kulorna i fem grupper blir fyra kulor över. Om hon delar kulorna i sju grupper blir tre kulor över. Hur många kulor har Liisa sammanlagt?

Vi betecknar antalet kulor med x och vi vill hitta en lösning som uppfyller de tre villkoren: x%4 == 3, x%5 == 4 och x%7 == 3. Eftersom vi vill att alla villkor ska gälla samtidigt, kombinerar vi dem med and-ordet.

Ännu behöver vi en övre gräns för antalet kulor för slingan. Vi antar att kulorna är färre än tusen stycken, dvs. vi går igenom värdena 0...999 för x. Resultatet är följande program:

for x in range(1000):
    if x%4 == 3 and x%5 == 4 and x%7 == 3:
        print(x)

När vi kör programmet skriver det ut följande lösningar:

59
199
339
479
619
759
899

Det finns alltså sju lösningar för intervallet 0...999 och uppgiften har inte en entydig lösning. Den minsta möjliga lösningen är att Liisa har 59 kulor.

Om vi bara vill hitta en lösning kan vi ändra programmet så här:

for x in range(1000):
    if x%4 == 3 and x%5 == 4 and x%7 == 3:
        print(x)
        break

Här åstadkommer kommandot break att slingan avslutas genast då vi hittar lösningen. Då skriver programmet endast ut den minsta lösningen:

59

---

Uppgift 1 Olöst

Kotivalo är ett år äldre än Justiina, som är ett år äldre än Aapeli. Om vi multiplicerar deras åldrar med varandra får vi talet 42840. Hur gammal är Aapeli?

Skriv ditt program här:

---

Uppgift 2 Olöst

Väinö är nu två gånger äldre än Anna, men för 20 år sedan var han tre gånger äldre än Anna. Hur gammal är Anna nu?

Skriv ditt program här:

---

Uppgift 3 Olöst

Vad är det minsta positiva tal som är delbart med 12, 34 och 56?

Skriv ditt program här:

---

Uppgift 4 Olöst

I intervallet 1...10 finns det 6 tal som är delbara med ett eller flera av talen 3, 5 och 7. De här talen är 3, 5, 6, 7, 9 och 10.

Hur många tal i intervallet 1...1000 är delbara med ett eller flera av talen 3, 5 och 7?

Skriv ditt program här:

---

Uppgift 5 Olöst

Hitta ett heltal x som löser ekvationen x³ - 60x² + 60x = 59.

Skriv ditt program här:

---

Uppgift 6 Olöst

Vi börjar att addera talen 1+2+3+... Om vi vill att summan är åtminstone 100, måste vi addera 14 tal, eftersom 1+2+3+...+14 = 105. Hur många tal måste vi addera om vi vill att summan är åtminstone en miljon?

Skriv ditt program här:

---