Cvičení 18

Napište funkci, která určí největší společný dělitel dvou zadaných čísel a a b pomocí naznačeného Eukleidova algoritmu, který spočívá v tom, že se větší z čísel vydělí tím menším, pak se menší vydělí zbytkem po dělení a tak pořád dokola, dokud není zbytek nula. Největším společným dělitelem je pak poslední dělitel.

80 : 48 = 1
32
     48 : 32 = 1
     16
          32 : 16 = 2
           0

Vytvořte rovněž druhou funkci, která určí nejmenší společný násobek zadaných čísel. S výhodou k tomu můžete využít vlastnosti, že součin čísel a a b je roven součinu jejich největšího společného dělitele a nejmenšího společného násobku.

a × b = NSD × NSN

Užijte obě funkce v krátkém programu.

program ukol18;
uses crt;
var x,y:integer;

function nsd(a,b:integer):integer;  {nejvetsi spolecny delitel}
  var
    zbytek:integer;

  begin
    repeat                      {postupne deleni}
     zbytek:=a mod b;           {zjistovani zbytku po deleni}
     a:=b;
     if zbytek = 0 then break else b:=zbytek;
    until zbytek=0;

    nsd:=b;
  end;

function nsn(a,b:longint):longint;  {nejmensi spolecny nasobek}
  begin
   nsn:=(a*b) div nsd(a,b);
  end;

begin
  clrscr;
  write('Zadejte cislo x: ');
  readln(x);

  write('Zadejte cislo y: ');
  readln(y);

  writeln;
  writeln('Jejich nejvetsi spolecny delitel je: ', nsd(x,y));
  writeln('a jejich nejmensi spolecny nasobek je: ', nsn(x,y));
end.

Zpět na: Lekce 7