Algoritmo para hallar el M.C.D de dos números naturales (a,b)

Comienzo:

                   Mientras sea a  <> b, efectuar:

   Si es a > b entonces llamar a al resultado de a-b,

   si no,                        llamar b al resultado de b-a

                   El M.C.D es a.
 

Fin.

 

Versión 1: Máximo Común Divisor. Lenguaje TurboPascal

Program MCD;

{Numeros naturales restringidos al rango del tipo word de TurboPascal}
Var a, b: 1..65535;
Begin
  Repeat
    Write('Dos numeros naturales (<=65535): '); ReadLn(a, b);
  Until (a > 0) and (b > 0);
  While a <> b do
     If a > b then a:= a - b else b:=b - a;
  WriteLn('El MCD es: ', a);
  ReadLn;
End.

Versión 2: Concepto de TAD, uso de función. Lenguaje TurboPascal

Program PruebaMCD;

{TAD natural, implementacion restringida al rango del tipo word}

Type natural = 1..65535;
Var   a, b: longInt;

Function EsNatural(x: longInt): boolean;
{Verifica pertenecia al TAD natural}
Begin    EsNatural:= (x > 0) and (x < 65536);  End;
Function MCD(x, y: longInt): natural;
Begin
    If EsNatural(x) and EsNatural(y)
    then Begin  
           While x <> y do  If x > y then x:= x - y else y:=y - x;
           MCD:=x;
         End
    else MCD:=1;
End;
Begin {Accion Programa principal}
  Repeat
    Write('Dos numeros naturales (<65536): '); ReadLn(a, b);
  Until EsNatural(a) and EsNatural(b);
  WriteLn('El MCD es: ', MCD(a,b));            ReadLn;
End.

Versión 3: Concepto de Clase (POO). Lenguaje TurboPascal

Program O_MCD;
{----------------------------------------------------------
   Prueba de Clase 'natural'. Restringida al rango de word
 ----------------------------------------------------------}
Uses Crt;
Const   MAX_WORD = 65535;
Type    natural = Object      {TAD: numeros naturales}
            n: word;
            Procedure Lee(Texto: string);
            Procedure Asigna(m: longInt);
            Function  Valor: word;
            Procedure Muestra(Texto: string);

End;
{----------------------------------------------------------
   IMPLEMENTACION de la Clase: natural
 ----------------------------------------------------------}
Procedure natural.Lee(Texto: string);
Var s: string; m: longInt; ec: integer;     col, lin: byte;
Begin  Write(Texto,': ');  col:=WhereX;  lin:=WhereY;
  Repeat
    Repeat
      GotoXY(col,lin); ClrEol; ReadLn(s);
      System.Val(s,m,ec);  {Conversion de string a longInt}
    Until ec = 0;          {ec=0: entrada numérica válida}
  Until (m > 0) and (m <= MAX_WORD); {dentro del rango word}
  n:=m;
End;      
Procedure natural.Asigna(m: LongInt);
Begin
  If   (m > 0) and (m <= MAX_WORD) then n:=m
  else Begin
         WriteLn('Error: Asignacion invalida; se asigna 1');
         n:=1;
End;   End;
Function natural.Valor: word;
Begin    Valor:=n;      End;

Procedure natural.Muestra(Texto: string);

Begin     Writeln(Texto,': ',n);  End;

{----------------------------------------------------------
       Calculo del Maximo Comun Divisor de dos naturales
 ----------------------------------------------------------}
Function MCD(x, y: natural): word;
Begin
  While x.Valor <> y.Valor do
     If x.Valor > y.Valor then x.Asigna(x.Valor - y.Valor)
                      else y.Asigna(y.Valor - x.Valor);
  MCD:=x.Valor;
End;

{----------------------------------------------------------}

Var a, b, c: natural;

Begin  {Accion Programa principal}
  ClrScr;
  a.Lee('Entre valor natural para a');
  b.Lee('Entre valor natural para b');
  c.Asigna( MCD(a,b) );       
  c.Muestra('El MCD es');

  ReadLn;
End.

lamialgo Jul 17 1998