Turinys

Euklido algoritmas

Ką daro

Suskaičiuoja dviejų skaičių didžiausią bendrąjį daliklį.

Algoritmas

x ir y DBD apskaičiuojamas taip:

  1. jeigu x = 0, tai DBD yra y
  2. jei ne, tai:
    1. jeigu x > y:
      1. x priskiriame y reikšmę
      2. y priskiriame ankstesnę x reikšmę (sukeičiame x ir y vietomis)
    2. atėmę y iš x gauname naująją x reikšmę (visada atimame mažesnį iš didesnio, todėl juos ir reikia prieš tai sukeisti)
    3. kartojame pirmąjį žingsnį (1.)

Pavyzdys (raštu)

x = 160, y = 75, koks DBD?

  1. x > y, x = 160 - 75 = 85, y = 75
  2. x > y, x = 85 - 75 = 10, y = 75
  3. x < y, x = 10, y = 75 - 10 = 65
  4. x < y, x = 10, y = 65 - 10 = 55
  5. x < y, x = 10, y = 55 - 10 = 45
  6. x < y, x = 10, y = 45 - 10 = 35
  7. x < y, x = 10, y = 35 - 10 = 25
  8. x < y, x = 10, y = 25 - 10 = 15
  9. x < y, x = 10, y = 15 - 10 = 5
  10. x > y, x = 10 - 5 = 5, y = 5
  11. x = y, t.y. x nėra mažesnis už y, x = 5 - 5 = 0, y = 5
  12. x = 0

Ats.: 5

Pavyzdys (Pascal)

program Euklidas;
 
    var x, y : integer;
 
function gcd (u, v : integer) : integer;
        var t : integer;
 
    begin
        repeat
            if (u < v) then begin
                t := u;
                u := v;
                v := t;
            end;
            u := u - v;
        until u = 0;
        gcd := v;
    end;
 
 
begin
 
while not eof do begin
    readln (x, y);
    if ((x > 0) and (y > 0)) then
        writeln (x, ' ', y, ' ', gcd (x, y));
end;
 
end.

Resursai