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