Kirjautuminen

Haku

Tehtävät

Keskustelu: Ohjelmointikysymykset: C, QB, VB6: Suurin yhteinen tekijä

ilja88 [04.04.2006 08:44:39]

#

Miten etsitään suurimman yhteisen tekijän. esim. murtolukujen 4/8 suurin yhteinen tekijä on 4 (1/2)

tn [04.04.2006 16:45:39]

#

google: "suurin yhteinen tekijä"
=> toinen tulos: http://fi.wikipedia.org/wiki/Eukleideen_algoritmi

Tumppu [04.04.2006 16:56:01]

#

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...

Metabolix [04.04.2006 18:54:47]

#

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.

Sami [04.04.2006 20:58:53]

#

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;
}

Antti Laaksonen [05.04.2006 20:11:20]

#

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%

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Tietoa sivustosta