[ Foro de Python ]

Python MCD y algoritmo de Euclides con variantes a imprimir

09-May-2016 18:00
Invitado (Shayla Dunn)
1 Respuestas

Buenas agradeceria si me pueden brindar ayuda en el siguiente ejercicio en Python:
Usted debe escribir un programa en Python3 que implemente una función ndmcd(a, b) que calcula el máximo común divisor de a y b mediante el algoritmo de Euclides.
Adicionalmente, esta función calcula las otras medidas durante su ejecución. Específicamente, la función n calcula el mcd de a y b, el número de divisiones (l neas de la forma a = b*q + r) y el número de cocientes diferentes generados durante el llamado.
Para lograr que una función en Python devuelva más de un valor, coloque los valores a retornar en una lista. La instrucción return [a, b, c] devuelve esos 3 valores.
En el programa principal se puede escribir [val1, val2, val3] = ndmcd(a, b), con lo cual a, b y c se retornan en val1, val2 y val2, respectivamente.

Un ejemplo completo del uso de este programa se muestra a continuación:
$ python3 ndivsmcd.py
Digite valor rango mínimo >= 2: 100
Digite valor rango máximo >= 3: 200
Digite mínimo valor del mcd: 3
Digite número de divisiones mínimas: 5
Digite número mínimo de cocientes diferentes: 4
MCD( 156 , 129 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 159 , 126 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 171 , 141 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 174 , 141 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 177 , 135 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 177 , 144 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 183 , 126 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 183 , 135 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 183 , 141 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 183 , 144 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 183 , 156 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 186 , 129 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 189 , 150 ) = 3 , divisiones: 5 , cocientes diferentes: 4
MCD( 192 , 141 ) = 3 , divisiones: 5 , cocientes diferentes: 4
Una manera de calcular el número de cocientes diferentes es definir una variable di q = [] una lista vacía. Luego, en un if se pregunta si el cociente recién calculado este en la lista di q. Si no está, se agrega con append. Quedara asi: if q not in di q: di q.append(q). Al final, la longitud de la lista indica el número de cocientes diferentes.
Se recomienda escribir por separado otro programa que lee a y b, y llama a la función MCD(a, b), la cual va imprimiendo cada línea de la forma a = b*q + r, con la cual se puede comprobar si ciertos números, digamos 192 y 141 realmente producen 5 líneas con 4 cocientes diferentes y un mcd = 3.


20-May-2016 23:10
Nacho Cabanes (+83)

¿Cual es la duda?

El algoritmo de Euclides es sencillo y lo puedes encontrar incluso en la Wikipedia:

https://es.wikipedia.org/wiki/Algoritmo_de_Euclides
 






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)