MAA11 Algoritmit ja lukuteoria

Johdanto Pythoniin, osa 3

While-silmukka

While-silmukka toistaa koodia niin kauan kuin tietty ehto pätee. Esimerkiksi seuraava silmukka toistaa koodia niin kauan kuin ehto a < 100 pätee. Jokaisen tulostuksen jälkeen muuttuja a:n arvo kaksinkertaistetaan.

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

Ohjelman tulostus on seuraava:

1
2
4
8
16
32
64

---

Tehtävä 1 Ratkaisematon

Tee ohjelma, joka tulostaa luvut 1, 3, 9, jne. eli luvun suuruus kolminkertaistuu joka askeleella. Ohjelman tulee tulostaa kaikki luvut, jotka ovat pienempiä kuin miljoona.

Ohjelman tulostuksen tulisi näyttää tältä:

1
3
9
27
81
...

Kirjoita ohjelma tähän:

---

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ä 2 Ratkaisematon

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

Kirjoita ohjelma tähän:

---

Funktio

Funktio voidaan määritellä def-sanan avulla. Komento return ilmaisee, minkä arvon funktio antaa tuloksena eli palauttaa. Esimerkiksi seuraava koodi määrittelee funktion f(x) = 2x + 5.

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

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

Koodin tulostus on seuraava:

7
9
11

Seuraava koodi näyttää funktion arvot, kun x on välillä 1..10:

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

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

Koodin tulostus on seuraava:

7
9
11
13
15
17
19
21
23
25

---

Tehtävä 3 Ratkaisematon

Tee ohjelma, joka näyttää funktion f(x) = x² + x + 2 arvot, kun x on välillä 1..100.

Ohjelman tulostuksen tulisi näyttää tältä:

4
8
14
22
32
...

Kirjoita ohjelma tähän:

---

Tehtävä 4 Ratkaisematon

Funktion f(x) = x² + x + 2 arvojen summa kokonaislukukohdissa välillä 1..5 on f(1) + f(2) + f(3) + f(4) + f(5) = 80.

Tee ohjelma, joka laskee vastaavasti funktion arvojen summan välillä 1..100.

Kirjoita ohjelma tähän:

---

Lisää funktioista

Funktion sisällä voi olla mitä tahansa koodia. Esimerkiksi seuraavan ohjelman funktio collatz kertoo, montako askelta Collatzin algoritmi suorittaa arvolla 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))

Ohjelman tulostus on seuraava:

1
6
4
10

---

Tehtävä 5 Ratkaisematon

Tulosta jokaiselle n:n arvolle välillä 1..100, montako askelta Collatzin algoritmi suorittaa. Tulostuksen tulee olla seuraavassa muodossa:

1 1
2 2
3 8
4 3
...

Kirjoita ohjelma tähän:

---

Tehtävä 6 Ratkaisematon

Kun n on välillä 1..100, suurin Collatzin algoritmin askelten määrä on 119 (kun n = 97).

Mikä on suurin Collatzin algoritmin askelten määrä, kun n on välillä 1..1000?

Kirjoita ohjelma tähän:

---

Seuraavaksi on kaksi vaikeampaa tehtävää, joiden avulla voit harjoitella lisää ohjelmoinnin perusteiden soveltamista.

---

Tehtävä 7 Ratkaisematon

Luvun 9⁹ = 387420489 numeroiden summa on 3+8+7+4+2+0+4+8+9 = 45. Tee ohjelma, joka ilmoittaa, mikä on luvun 99⁹⁹ numeroiden summa.

Kirjoita ohjelma tähän:

---

Tehtävä 8 Ratkaisematon

Luvussa 9⁹ = 387420489 esiintyy 2 kertaa numero 4. Tee ohjelma, joka ilmoittaa, montako kertaa luvussa 99⁹⁹ esiintyy numero 4.

Kirjoita ohjelma tähän:

---