Inspirado por Cheap, Fast, Good , implementaremos un algoritmo que tiene exactamente dos de ellos.
Las matemáticas
Dados dos números enteros no nulos a y b , el GCF d es el mayor número entero que divide tanto una y b sin resto. Los coeficientes de Bézout son pares de enteros (x, y) de modo que ax + by = d . Los coeficientes de Bézout no son únicos. Por ejemplo, dado:
a = 15, b = 9
Tenemos
d = 3
x = 2
y = -3
Desde 15*2 + 9*(-3) = 30 - 27 = 3
.
Una forma común de calcular el MCD y un par de coeficientes de Bézout es usar el algoritmo de Euclides , pero de ninguna manera es la única forma.
El código
Su programa debe tomar dos enteros como entradas. Debería generar / devolver el máximo factor común y un par de coeficientes de Bézout.
Entrada de ejemplo:
15 9
salida de ejemplo
3 (2, -3)
La salida puede estar en cualquier orden y formato, pero debe quedar claro cuál es el MCD y cuáles son los coeficientes.
El deshonesto
Su programa tiene el potencial de ser barato, rápido y bueno. Desafortunadamente, solo pueden ser dos de esos a la vez.
- Cuando no es barato , el programa debe usar una cantidad excesiva de recursos del sistema.
- Cuando no es rápido , el programa debería tomar una cantidad excesiva de tiempo.
- Cuando no es bueno , la salida del programa debería ser incorrecta.
El programa debería poder hacer (bueno, no hacer) los tres. Lo que hace cuando depende de usted, podría basarse en el tiempo, el compilador, qué entrada es más grande, etc. Algunas notas adicionales:
- Obviamente, su programa no debe ser sencillo y debe pasar una inspección superficial. Sospecharía un poco si implementaras tres algoritmos separados.
- En el caso barato , "cantidad excesiva de recursos del sistema" es cualquier cosa que ralentizaría otros programas. Puede ser memoria, ancho de banda, etc.
- En el caso rápido , "tiempo excesivo" significa relativo a cómo funciona en los casos baratos y buenos . El programa aún debería terminar. Cuanto más cerca esté de "increíblemente frustrante pero no lo suficientemente frustrante como para detener el programa", mejor (más divertido).
- En el buen caso, la salida no debería ser obviamente incorrecta y debería pasar una inspección superficial. Sería muy sospechoso si me diera un MCD de "2 anna half".
Este es un concurso de popularidad, ¡así que la mayoría de los votos positivos gana!
EDITAR
Para aclarar, estoy buscando programas que pueden ser "rápidos y baratos" y "baratos y buenos" y "rápidos y buenos" en diferentes casos, no aquellos que solo hacen uno de ellos.
fuente
Respuestas:
C
Es barato y rápido. Obtienes mcd en un abrir y cerrar de ojos. Sin embargo, el tipo que lo hizo no tenía idea de ese "co-algo de Bézier", por lo que simplemente dividió ayb por mcd. (para empeorar las cosas, en ese punto ayb están bastante lejos de su valor inicial debido al algoritmo que eligió sabiamente)
fuente
C#
Esto calcula los coeficientes de Bézout. He utilizado el algoritmo de Euclides extendido .
fuente
Perl 5
No es barato: main () se llama de forma recursiva (llenando la pila) hasta que perl active una advertencia de "recursión profunda" que cerrará la aplicación debido al controlador __WARN__.
No rápido: cuando los algoritmos gcf () devuelven resultados correctos, el código solo se cuelga durante unos segundos (select () en main ()).
No es bueno: todos los resultados superiores a 99 (o inferiores a -99) son incorrectos.
En general, no es tan creativo; esperando respuestas más elegantes.
fuente
Pitón
Esto es barato y rápido, pero es malo en el hecho de que el rango está limitado a la entrada más grande, por lo que es posible que no encuentre un par de coeficientes.
Buen rompecabezas
fuente
Javascript
No es barato
Utiliza muchos recursos del sistema.
No rapido
Utilice una devolución de llamada, solo como un extra a prueba de fallas.
No está bien
Límite estricto de
gcf(10, 10)
, solo para ahorrar espacio en disco.fuente