Programmeringens grunder

Kapitel 9: Mer sökningar

Ibland formas lösningen på ett problem av flera variabler. Då kan vi hitta lösningen genom att skapa kapslade slingor som går igenom kombinationer av variabler.

Kapslade slingor

Vi granskar följande program som exempel:

for a in range(1,4):
    for b in range(1,4):
        print(a,b) 

Programmets utskrift är följande:

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Här går huvudslingan igenom talen 1...3 med hjälp av variabel a och den kapslade slingan går igenom talen 1...3 med hjälp av variabel b. På så sätt kan vi gå igenom alla sätt att välja värden för variablerna a och b i intervallet 1...3.

På motsvarande sätt kan vi gå igenom flera kombinationer av variabler genom att skapa fler kapslade slingor.

Resväskans kod

Nu är vi redo att lösa följande uppgift:

Resväskans lås har en kod som består av fyra siffror i intervallet 1–9. Du har dock glömt bort koden och minns bara att den första och tredje siffran är densamma och att summan av siffrorna är 13. Vilka koder måste du gå igenom när du vill hitta rätt kod?

Vi kan lösa uppgiften med hjälp av ett program som går igenom alla möjliga koder och skriver ut dem som uppfyller villkoren. Koden består av fyra siffror varav var och en är i intervallet 1...9, så vi skapar fyra kapslade slingor.

Följande program söker koderna:

for a in range(1,10):
    for b in range(1,10):
        for c in range(1,10):
            for d in range(1,10):
                if a == c and a+b+c+d == 13:
                    print(a,b,c,d)

När vi kör programmet gör det upp en lista över alla koder som uppfyller samtliga villkor:

1 2 1 9
1 3 1 8
1 4 1 7
1 5 1 6
1 6 1 5
1 7 1 4
1 8 1 3
1 9 1 2
2 1 2 8
2 2 2 7
2 3 2 6
2 4 2 5
2 5 2 4
2 6 2 3
2 7 2 2
2 8 2 1
3 1 3 6
3 2 3 5
3 3 3 4
3 4 3 3
3 5 3 2
3 6 3 1
4 1 4 4
4 2 4 3
4 3 4 2
4 4 4 1
5 1 5 2
5 2 5 1

Vi kan också genomföra programmet så att det bara räknar hur många koder som uppfyller villkoren existerar och inte skriver ut dem alla. Detta åstadkommer vi så här:

s = 0
for a in range(1,10):
    for b in range(1,10):
        for c in range(1,10):
            for d in range(1,10):
                if a == c and a+b+c+d == 13:
                    s += 1
print(s)

Nu är utskriften för programmet följande:

28

För att vi säkert ska hitta rätt kod räcker det alltså med att vi prövar 28 koder.

---

Uppgift 1 Olöst

Resväskans kod består av fyra siffror i intervallet 1–9. Du har glömt bort koden men minns att produkten av siffrorna är 252. Hur många sådana koder finns det?

Skriv ditt program här:

---

Uppgift 2 Olöst

Resväskans kod består av fyra siffror i intervallet 1–9. Du har glömt bort koden men minns att varje siffra i koden är större än den föregående siffran. Hur många sådana koder finns det?

Skriv ditt program här:

---

Uppgift 3 Olöst

Resväskans kod består av fyra siffror i intervallet 1–9. Du har glömt bort koden men minns att koden har fyra olika siffror. Hur många sådana koder finns det?

Skriv ditt program här:

---

Uppgift 4 Olöst

Du kastar tärningen fem gånger, och varje kast producerar ett resultat 1–6. På hur många sätt kan du producera summan 15? Ett möjligt sätt är 4+2+1+6+2 = 15.

Skriv ditt program här:

---

Uppgift 5 Olöst

Positiva heltal a, b och c är en pythagoreisk trippel om a < b < c och a² + b² = c². Till exempel är talen 3, 4 och 5 en pythagoreisk trippel.

Det finns 6 pythagoreiska tripplar där c är högst 20: (3,4,5), (5,12,13), (6,8,10), (8,15,17), (9,12,15) och (12,16,20). Hur många pythagoreiska tripplar finns det där c är högst 50?

Skriv ditt program här:

---

Uppgift 6 Olöst

Det finns 16 sätt att placera en svart och en vit dam på ett 3x3-schackbräde så att de inte hotar varandra. Hur många sätt finns det på ett 8x8-schackbräde?

Skriv ditt program här:

---