martes, 12 de octubre de 2010

.: MCD Recursivo :.

:: MCD (Recursivo) Nueva Edición ::



Materia. Lab de Leng de Progr

Hora. V1 (Jueves)

Que tal compañeros, sé que es muy tarde para hablar de esto, pero ¿recuerdan cuando las clases de recursividad en la cual dijeron el pseudocódigo para el Máximo Común Divisor en recursivo?

Si no mal recuerdo, podíamos tener los casos en que un número era mayor al otro, y por lo tanto era ahi donde se mandaba llamar la función nuevamente.

Las operaciones que se realizaban en la recursividad más que nada eran restas si no mal recuerdo.

Bueno. En mi afan de ayudar a una amiga con el mismo tema, decidi realizar el mismo código pero por mi parte.

En el caso del pseudocódigo de nuestros compañeros, había momentos en que el primer número era mayor que el segundo, y luego en otras ocasiones en que el primero era menor que el segundo, por lo que podía entrar en las dos condiciones de recursividad que habían planteado.

Mi modificación tiene varias diferencias, las cuales son:
  1. En ese pseudocódigo se usaban restas. Mi código se basa en divisiones y residuos.
  2. Si al inicio de la recursividad, el primero número es mayor al segundo, así se mantiene durante todo el proceso de la función. No hay cambios de ser primero el mayor y luego el menor.
  3. Mi código obtiene el MCD para tres números.
Fundamentos.

Como tenía que saber cierta información antes de hacer el código, encontre ciertos datos en los cuales me base: "El Algoritmo de Euclides Tradicional", que según Wikipedia (no podía faltar, ya saben), dice lo siguiente:

Al dividir a entre b (números enteros), se obtiene un cociente q y un residuo r. Es posible demostrar que el máximo común divisor de a y b es el mismo que el de b y r. Éste es el fundamento principal del algoritmo. También es importante tener en cuenta que el máximo común divisor de cualquier número a y 0 es precisamente a. Para fines prácticos, la notación mcd(a,b) significa máximo común divisor de a y b.
Para que lo asimilen más claramente, veamos el siguiente ejemplo paso a paso con la siguiente tabla:
Para calcular el máximo común divisor de 2366 y 273 se puede proseguir de la siguiente manera:

Resultado: 91

Código del MCD
Fuente
Wikipedia. "Algoritmo de Euclides". http://es.wikipedia.org/wiki/Algoritmo_de_Euclides

1 comentario: