MAA11 Algoritmer och talteori

Introduktion i Python, del 3

While-loop

While-loopen upprepar koden så länge ett visst villkor gäller. Till exempel upprepar följande loop koden så länge villkoret a < 100 gäller. Efter varje urskrift fördubblas värdet för variabeln a.

a = 1
while a < 100:
    print(a)
    a = 2*a

Programmets utskrift är följande:

1
2
4
8
16
32
64

---

Uppgift 1 Olöst

Gör ett program som skriver ut talen 1, 3, 9, osv. dvs. talets storlek tredubblas vid varje steg. Programmet ska skriva ut alla tal, som är mindre än en miljon.

Programmets utskrift ska se ut så här:

1
3
9
27
81
...

Skriv ditt program här:

---

Collatz algoritm

År 1937 presenterade matematikern Collatz en märklig algoritm som ges ett positivt heltal n som startvärde. Om n är ett jämnt tal, dividerar algoritmen det med två, och i annat fall multiplicerar algoritmen det med tre och adderar ett. Algoritmen upprepar samma i loopen tills n är 1. Till exempel om startvärdet n är 12, går algoritmen igenom talen 12, 6, 3, 10, 5, 16, 8, 4, 2 och 1.

Vi kan genomföra Collatz algoritm på följande sätt:

print(n)
while n != 1:
    if n%2 == 0:
        n = n//2
    else:
        n = 3*n+1
    print(n)

Observera att vi använder beteckningen // vid division istället för det vanliga /, så att resultatet är ett heltal utan decimaler.

Till exempel om n är 12, är utskriften följande:

12
6
3
10
5
16
8
4
2
1

Frågan lyder: stannar Collatz algoritm med alla värden för n? Algoritmen stannar tydligt åtminstone när n är 12, och på många andra startvärden, men finns det ändå ett stort n, som algoritmen inte stannar på? Det finns ingen som vet.

---

Uppgift 2 Olöst

Collatz algoritm skriver ut 10 tal, när startvärdet är 12. Hur många tal skriver algoritmen ut när startvärdet är 12 345?

Skriv ditt program här:

---

Funktion

Funktionen kan definieras med ordet def. Kommandot return uttrycker vilket värde funktionen ger som resultat, dvs. returnerar. Till exempel följande kod definierar funktionen f(x) = 2x + 5.

def f(x):
    return 2*x+5

print(f(1))
print(f(2))
print(f(3))

Kodens utskrift är följande:

7
9
11

Följande kod visar funktionens värden när x är på intervallen 1..10:

def f(x):
    return 2*x+5

for i in range(1,11):
    print(f(i))

Kodens utskrift är följande:

7
9
11
13
15
17
19
21
23
25

---

Uppgift 3 Olöst

Gör ett program som visar funktionens f(x) = x² + x + 2 värden när x är på intervallen 1..100.

Programmets utskrift ska se ut så här:

4
8
14
22
32
...

Skriv ditt program här:

---

Uppgift 4 Olöst

Summan av funktionens f(x) = x² + x + 2 värden på intervallen 1..5 är f(1) + f(2) + f(3) + f(4) + f(5) = 80.

Gör ett program, som beräknar summan av funktionens värden på intervallen 1..100.

Skriv ditt program här:

---

Mer om funktioner

Inuti funktionen kan det finnas vilken kod som helst. Till exempel följande programs funktion collatz berättar hur många steg Collatz algoritm genomför på värdet n.

def collatz(n):
    c = 1
    while n != 1:
        c += 1
        if n%2 == 0:
            n = n//2
        else:
            n = 3*n+1
    return c

print(collatz(1))
print(collatz(5))
print(collatz(8))
print(collatz(12))

Programmets utskrift är följande:

1
6
4
10

---

Uppgift 5 Olöst

Skriv ut för varje n:s värde mellan 1..100, antalet steg Collatz algoritm utför. Utskriften ska vara i följande format:

1 1
2 2
3 8
4 3
...

Skriv ditt program här:

---

Uppgift 6 Olöst

När n är mellan 1..100, är det största antalet steg på Collatz algoritm 119 (närn = 97).

Vilket är det största antalet steg på Collatz algoritm, när n är mellan 1..1 000?

Skriv ditt program här:

---

Uppgift 7 Olöst

Talet 9⁹ = 387420489 siffrornas summa är 3+8+7+4+2+0+4+8+9 = 45. Gör ett program som anger summan av siffrorna i talet 99⁹⁹.

Skriv ditt program här:

---

Uppgift 8 Olöst

I talet 9⁹ = 387420489 förekommer siffran 4 två gånger. Gör ett program som anger hur många gånger siffran 4 förekommer i talet 99⁹⁹.

Skriv ditt program här:

---