Miten etsitään suurimman yhteisen tekijän. esim. murtolukujen 4/8 suurin yhteinen tekijä on 4 (1/2)
google: "suurin yhteinen tekijä"
=> toinen tulos: http://fi.wikipedia.org/wiki/
Dim T1 Dim T2 T2 = 32 T1 = 24 For i = T2 To 0 Step -1 DoEvents For a = 0 To T2 DoEvents For u = 0 To T1 If i * a = T2 And i * u = T1 Then MsgBox i Exit Sub End If Next u Next a Next i
Ei nyt mikään älyttömän hyvä koodi, mut toimii ainaki pienemmillä luvuilla...
Hajotat ne ensin tekijöihin ja sitten vertailet. Eli vähemmän mukaan aina. Vaikkapa 72 ja 162, tekijöiksi tulee 2^3*3^2 ja 2*3^3, ja näistä otetaan siis yksi kakkonen ja kaksi kolmosta, yhteensä 18. Lopputuloksena on 4*18 ja 9*18.
Toisaalta voit hajottaa niitä yhtä aikaa (olisiko tuo ylläoleva juuri se, en jaksa katsoa :) Eli jos molemmat ovat jaollisia a:lla, kerrotaan tekijä ja jaetaan molemmat luvut a:lla.
Kannattaa todellakin tutustua tuohon Eukleideen algoritmiin (Euclidean algorithm), sillä se on isoillakin luvuilla nopea ja hyvinkin yksinkertainen toteuttaa.
Perässä englanninkielisestä wikipediasta kopioidut toteutukset C/C++:lle sekä rekursiivisena, että iteratiivisena toteutuksena.
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
int gcd(int a, int b) { int t; while (b != 0) { t = b; b = a % b; a = t; } return a; }
Suurinta yhteistä tekijää etsitään jakolaskun avulla. Edellisen laskun jakaja on seuraavan jaettava, ja edellisen laskun jakojäännös on seuraavan jakaja. Laskemista jatketaan, kunnes jakojäännös on 0. Suurin yhteinen tekijä on sen laskun jakaja. Esim. tutkitaan lukuja 30 ja 16.
30 / 16 = 1, jää 14 16 / 14 = 1, jää 2 14 / 2 = 7, jää 0
Nyt tiedetään, että suurin yhteinen tekijä on 2.
Teinpä vielä esimerkin QBasicille.
' palauttaa lukujen suurimman yhteisen tekijän FUNCTION SYT% (A%, B%) WHILE B% <> 0 U% = B% B% = A% MOD B% A% = U% WEND SYT% = A% END FUNCTION INPUT "Kirjoita osoittaja: ", o% INPUT "Kirjoita nimittäjä: ", n% j% = SYT%((o%), (n%)) PRINT PRINT o%; "/"; n%; "="; o% / j%; "/"; n% / j%
Aihe on jo aika vanha, joten et voi enää vastata siihen.