Programmeringens grunder

Kapitel 12: Collatz algoritm

Vi har använt for-slingan en hel del, men det finns också en annan slinga i programmering, while-slingan. Denna slinga upprepar koden så länge som önskade villkor gäller.

While-slingan

While-slingan upprepar koden så länge som det givna villkoret gäller. Till exempel i följande slinga är villkoret x <= 100, dvs. slingan fortsätter så länge som x är högst 100:

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

Programmets utskrift är följande:

1
2
4
8
16
32
64

Ett intressant drag hos while-slingan är att vi inte nödvändigtvis vet på förhand hur många gånger koden i slingan upprepas. I själva verket vet vi inte ens om slingan alls upphör.

Collatz algoritm

År 1937 presenterade matematikern Collatz en märklig algoritm, som ges ett positivt heltal n som utgångsvä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 fortsätter med samma sak i en slinga tills n är 1. Om utgångsvärdet till exempel ä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)

Märk väl att för att resultatet ska vara ett heltal och inte ha en decimaldel använder vi i division beteckningen // istället för den vanliga /.

Om n till exempel är 12, är programmets utskrift 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 i varje fall tydligt om n är 12 och också med flera andra utgångsvärden, men skulle det ändå kunna finnas något stort n, med vilket algoritmen inte stannar? Ingen känner till svaret.

---

Uppgift 1 Olöst

Om utgångsvärdet är 12, skriver Collatz algoritm ut 10 tal. Hur många tal skriver algoritmen ut om utgångsvärdet är 12345?

Skriv ditt program här:

---

Uppgift 2 Olöst

Följande lista visar hur många tal Collatz algoritm skriver ut med utgångsvärdena 1...10:

1 1
2 2
3 8
4 3
5 6
6 9
7 17
8 4
9 20
10 7

Om utgångsvärdet till exempel är 7, skriver algoritmen ut 17 tal. Skriv ett program som producerar en motsvarande lista för utgångsvärdena 1...100.

Skriv ditt program här:

---

Uppgift 3 Olöst

Collatz algoritm skriver ut högst 20 tal när utgångsvärdet är mellan 1...10. Hur många tal som högst skriver algoritmen när utgångsvärdet är mellan 1...1000?

Skriv ditt program här:

---

Uppgift 4 Olöst

Du har ett positivt heltal n. Om n är ett jämnt tal, dividerar du det med två, och i annat fall subtraherar du ett. Du fortsätter med samma sak tills n är 1.

Om n till exempel är 10, ska du genomföra 4 steg: 10 → 5 → 4 → 2 → 1. Skriv ett program som räknar ut hur många steg ska du genomföra om n är 123¹²³.

Skriv ditt program här:

---

Uppgift 5 Olöst

Du har sparat 100 euro och får 1 % ränta varje år. Om ett år har du 101 euro, om två år har du 102.01 euro, etc. Om hur många år har du mer än en miljon euro?

Skriv ditt program här:

---

Uppgift 6 Olöst

Du har ett positivt heltal n. På varje drag får du subtrahera x från talet, där x är en siffra i talet. Ditt mål är att hitta det minsta antal drag som behövs för att producera talet 0.

Om n är 23, är det minsta antal drag 5 eftersom du kan genomfåra följande drag: 23 → 20 → 18 → 10 → 9 → 0. Vad är det minsta antal drag om n är 12345?

Skriv ditt program här:

---