Ohjelmoinnin alkeet

Luku 12: Collatzin algoritmi

Olemme käyttäneet paljon for-silmukkaa, mutta ohjelmoinnissa on toinenkin silmukka: while-silmukka. Tämä silmukka toistaa koodia niin kauan kuin haluttu ehto on voimassa.

While-silmukka

While-silmukka toistaa koodia niin kauan kuin annettu ehto pätee. Esimerkiksi seuraavassa silmukassa ehtona on x <= 100, eli silmukka jatkuu niin kauan kuin x on enintään 100:

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

Ohjelman tulostus on seuraava:

1
2
4
8
16
32
64

Kiinnostava piirre while-silmukassa on, että emme tiedä välttämättä etukäteen, montako kertaa silmukassa oleva koodi suoritetaan. Itse asiassa emme tiedä ehkä edes sitä, päättyykö silmukka milloinkaan.

Collatzin algoritmi

Vuonna 1937 matemaatikko Collatz esitteli merkillisen algoritmin, jolle annetaan alkuarvona positiivinen kokonaisluku n. Jos n on parillinen, algoritmi jakaa sen kahdella, ja muuten algoritmi kertoo sen kolmella ja lisää yhden. Algoritmi toistaa samaa silmukassa, kunnes n on 1. Esimerkiksi jos alkuarvo n on 12, algoritmi käy läpi luvut 12, 6, 3, 10, 5, 16, 8, 4, 2 ja 1.

Voimme toteuttaa Collatzin algoritmin seuraavasti:

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

Huomaa, että käytämme jakolaskussa merkintää // tavallisen / sijasta, jotta tulos on kokonaisluku eikä siihen tule desimaaliosaa.

Esimerkiksi jos n on 12, ohjelman tulostus on seuraava:

12
6
3
10
5
16
8
4
2
1

Kysymys kuuluu: pysähtyykö Collatzin algoritmi kaikilla n:n arvoilla? Algoritmi pysähtyy selvästi ainakin, kun n on 12, ja monella muullakin alkuarvolla, mutta olisiko silti olemassa jokin suuri n, jolla algoritmi ei pysähdy? Kukaan ei tiedä asiaa.

---

Tehtävä 1 Ratkaisematon

Collatzin algoritmi tulostaa 10 lukua, kun alkuarvo on 12. Montako lukua algoritmi tulostaa, kun alkuarvo on 12345?

Kirjoita ohjelma tähän:

---

Tehtävä 2 Ratkaisematon

Seuraava luettelo kertoo, montako lukua Collatzin algoritmi tulostaa, kun sille annetaan alkuarvot 1...10:

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

Esimerkiksi alkuarvolla 7 algoritmi tulostaa 17 lukua. Tee ohjelma, joka tulostaa vastaavan luettelon alkuarvoille 1...100.

Kirjoita ohjelma tähän:

---

Tehtävä 3 Ratkaisematon

Kun alkuarvo on välillä 1...10, Collatzin algoritmi tulostaa enimmillään 20 lukua (alkuarvolla 9). Tee ohjelma, joka selvittää, montako lukua algoritmi tulostaa enimmillään, kun alkuarvo on välillä 1...1000.

Kirjoita ohjelma tähän:

---

Tehtävä 4 Ratkaisematon

Sinulle annetaan positiivinen kokonaisluku n. Jos n on parillinen, jaat sen kahdella. Jos taas n on pariton, vähennät siitä yhden. Jatkat samalla tavalla, kunnes n on 1.

Esimerkiksi kun n on aluksi 10, suoritat 4 askelta: 10 → 5 → 4 → 2 → 1. Tee ohjelma, joka laskee, montako askelta suoritat, kun n on aluksi 123¹²³.

Kirjoita ohjelma tähän:

---

Tehtävä 5 Ratkaisematon

Laitat säästöön 100 euroa ja saat korkoa joka vuosi 1 %. Esimerkiksi vuoden päästä koossa on 101 euroa ja kahden vuoden päästä koossa on 102.01 euroa. Monenko vuoden päästä säästössä oleva summa on ensimmäistä kertaa yli miljoona euroa?

Kirjoita ohjelma tähän:

---

Tehtävä 6 Ratkaisematon

Sinulle annetaan positiivinen kokonaisluku n. Saat joka siirrolla vähentää lukua x:llä, missä x on jokin luvussa oleva numero. Haluat saada luvusta nollan käyttäen mahdollisimman vähän siirtoja.

Esimerkiksi kun n on 23, pienin siirtojen määrä on 5. Siirtosarja on 23 → 20 → 18 → 10 → 9 → 0. Mikä on pienin siirtojen määrä, kun n on 12345?

Kirjoita ohjelma tähän:

---