Eukleideen algoritmi takaperin(?)

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Ongelma: Määritä eräät sellaiset kokonaisluvut x ja y, että 127x-87y=1.

Käsittääkseni tämä pitäisi tehdä Eukleideen algoritmilla takaperin (sillä Syt(127,87)=1), mutta en täysin ymmärtänyt miten se toimii, joten en saanut vastausta. Osaisiko joku auttaa sen kanssa? vai voiko tämän ratkaista jollain muulla tavalla?

Kommentit (5)

Vierailija

Jos olet jo Eukleideen algoritmin tehnyt, niin viimeisellä rivillä sinulla on 5=2*2+1. Siirrä nyt se näin: 1= 5-2*2 ja jatka siitä ratkaisemalla seuraavat rivit, niin että lopulta sinulla on 1=127a+87b. Toivottavasti ohjeet eivät ole liian vaikeat!

Vierailija

toinen ongelma on seuraava:
Nukketeatterin pääsymaksu oli 1,80 euroa aikuisilta ja 75 senttiä lapsilta. Eräänä iltana pääsymaksuja kertyi yhteensä 90 euroa. Kuinka monta maksanutta katsojaa oli esityksessä, kun oletetaan, että aikuisia oli enemmän kuin lapsia?

--> 1,8x+0,75y=90. Jos teen sen samalla tavalla kuin edellisen tehtävän, saan x=-12 ja y=30. Eli miten se pitäisi tehdä siten, että ei tulisi negatiivista x:ä tai y:tä?

Vierailija

Eli tästä saadaan diofantoksen yhtälö:

1.8x + 0.75y = 90

Diofantoksen yhtälö on muotoa ax + by = c ja sen yleinen ratkaisu on
x= x0 + n * b/syt(a,b)
y= y0 - n * a/syt(a,b)

(Oikeastaan a:n, b:n ja c:n pitäisi olla kokonaislukuja, mutta en jaksanut nyt muuttaa niitä, koska vastaus on kuitenki sama. Jos haluut muuttaa ne kokonaisluvuiksi ni muuta kaik noi hinnat senteiksi.

Eukleideen algoritmilla haetaan eka syt(1.8,0.75)=0.15
Siitä saadaa lineaarikombinaatiolla notta 0.15 = -2 * 1.8 + 5 * 0.75
Kun toi kerrotaan 600:lla saadaan 90 = -1200*1.8 + 3000*0.75
Eli alkup. Diofantoksen eräs ratkasu. Nyt lätkitää toi syt(1.8,0.75) ja saatu ratkasu toho yleisee muotoon, jolloin saadaan että
x= -1200 + n*0.75/0.15
y= 3000 - n*1.8/0.15
eli
x= -1200 + 5n
y= 3000 - 12n

Koska aikuisia piti olla enemmän, muodostetaan yleisestä ratkasusta epäyhtälö: -1200 + 5n > 3000 - 12n josta n on yhtäsuuri tai suurempi kuin 248.

Nyt viel sijotetaan n toho yleiseen ratkasuun ni saadaan että
x= -1200 + 5*248
y= 3000 - 12*248

eli x= 40 ja y = 24

Eli vastaus on notta yleisössä oli 40 aikuista ja 24 lasta, jotka olivat maksaneet.

Vierailija

Hieno ratkaisu.

[size=75:2wohw1od](Sivuhuomiona maksaneita voi olla myös 45 aikuista + 12 lasta tai 50 aikuista ilman lapsia.)[/size:2wohw1od]

Uusimmat

Suosituimmat