2Eva_IIT2011_T1 Algoritmo de Euclides MCD

2da Evaluación II Término 2011-2012, Enero 31, 2012 /ICM00794

Tema 1 (20 puntos). El Algoritmo de Euclides es considerado el más antiguo y no trivial para encontrar el “máximo común divisor” (mcd) entre dos números a y b.
El paso esencial que garantiza la validez del algoritmo consiste en mostrar que el mcd de a y b es:

  • considerar que a > b  y b≥0
  • si b es cero, mcd es igual a a
  • en otro caso, si b>0, es igual al mcd entre b y el residuo de a dividido por b

Realice una función recursiva mcdeuclides(a,b) siguiendo el algoritmo de Euclides, y muestre una prueba de escritorio para a=15 y b=6.

Rúbrica: Definición de función (5 puntos), Recursividad (10 puntos), Prueba de escritorio (5puntos).


Prueba de escritorio:

>>> mcd_euclides(15,6)
a:  15 b:  6 residuo: 3
a:  6 b:  3 residuo: 0
3
>>> mcd_euclides(72,16)
a:  72 b:  16 residuo: 8
a:  16 b:  8 residuo: 0
8
>>>