MAA11 Algoritmit ja lukuteoria

Kokonaislukuyhtälöitä

Yhtälön ratkaisua voidaan etsiä yhden tai useamman silmukan avulla. Ideana on käydä läpi kaikki mahdolliset ratkaisut ja näyttää ratkaisut, jotka toteuttavat halutut ehdot.

Tarkastellaan esimerkkinä tehtävää, jossa haluamme etsiä kokonaisluvut a ja b, jotka toteuttavat yhtälön a²+3b = 99. Hakualue on rajattu niin, että a:n ja b:n tulee olla välillä 1..50. Seuraava ohjelma toteuttaa haun:

for a in range(1,51):
    for b in range(1,51):
        if a**2+3*b == 99:
            print(a,b)	

Ohjelma käy läpi kaikki tavat valita muuttujille a ja b arvo väliltä 1..50 ja tulostaa ratkaisut, jotka toteuttavat yhtälön. Ohjelman tulostus on seuraava:

3 30
6 21
9 6

Tämä tarkoittaa, että mahdollisia ratkaisuja yhtälölle ovat:

• a = 3, b = 30
• a = 6, b = 21
• a = 9, b = 6

Huomaa, että tällaisessa ohjelmassa täytyy aina valita hakualue, jonka ohjelma käy läpi. Jos ratkaisu on hakualueen ulkopuolella, niin ohjelma ei löydä sitä.

---

Tehtävä 1 Ratkaisematon

Tee ohjelma, joka etsii kaikki positiiviset kokonaisluvut a ja b, joille pätee a² + b² = 250. Tässä riittää tarkastella lukujen a ja b arvot välillä 1..15, sillä 16² = 256 on jo liian suuri.

Ohjelman tulee antaa vastaus samalla tavalla kuin esimerkissä.

Kirjoita ohjelma tähän:

---

Tehtävä 2 Ratkaisematon

Tee ohjelma, joka etsii ratkaisut yhtälölle a² + b² ≡ 0 (mod 97), kun a:n ja b:n tulee olla välillä 1..50.

Tässä on siis vaatimuksena, että a² + b² on jaollinen luvulla 97. Yksi ratkaisu on a = 7 ja b = 40, koska silloin tulos on 7² + 40² = 1649 = 17*97.

Ohjelman tulee antaa vastaus samalla tavalla kuin esimerkissä.

Kirjoita ohjelma tähän:

---

Tehtävä 3 Ratkaisematon

Tee ohjelma, joka etsii ratkaisut yhtälölle a² + b² = c², kun a:n, b:n ja c:n tulee olla välillä 1..30.

Vastauksen tulisi näyttää seuraavalta:

3 4 5
4 3 5
5 12 13
6 8 10
7 24 25
...

Kirjoita ohjelma tähän:

---