Este artículo describe el algoritmo de Java para resolver el mayor divisor común de dos enteros no negativos. Compártelo para su referencia, como sigue:
Funciones de código:
1. Implementación de Java (código fuente completo con casos de prueba);
2. Resuelva el mayor divisor común de dos enteros no negativos P y Q (P> = Q);
3. Dos soluciones: método de bucle y método recursivo;
Código fuente completo:
/ * GCD: Divisor Common */public class GCD {public static void main (string args []) {/ * test case */int p = 32; int q = 24; System.out.println ("El mayor divisor de"+P+"y"+Q+"is /n"+"[GCD1]:"+GCD1 (P, Q)+" /N"+"[GCD2]:"+GCD2 (P, Q)); } // (q % gcd == 0 y p % gcd == 0 [gcd de q a 1]) public static int gcd1 (int p, int q) {int gcd = 1; int d = q; while (d> 0) {d--; if (q%d == 0 && p%d == 0) {gcd = d; romper; }} return gcd; } // gcd (p, q) = gcd (q, p%q) [if q = 0, gcd = p] public static int gcd2 (int p, int q) {if (q == 0) return p; int r = p%q; //System.out.println("("+q+","+R+ ")"); return gcd2 (q, r); }}Ejecución de captura de pantalla:
Explicación del código:
Método circular GCD1 (P, Q)
Descripción del lenguaje natural: el método de bucle resuelve el mayor divisor común de dos enteros no negativos P, Q (P> = Q), es decir, resuelve el valor máximo del divisor común de Q que es p. Deje que D (dividido) disminuya de P (paso de disminución = 1) D es siempre "el valor máximo de la condición que está a punto de ser satisfecho". Cuando d cumple con la condición (puede dividirse por P y divisible por P), D es el divisor común de P y Q, y D es el mayor divisor común de P y Q;
Método recursivo GCD2 (P, Q)
Descripción del lenguaje natural: el método recursivo resuelve el mayor divisor común de dos enteros no negativos P, Q (P> = Q). Cuando Q es igual a 0, el mayor divisor común es P; De lo contrario, tome el resto de P y Q para obtener R = P%Q, y el mayor divisor común de P y Q es el mayor divisor común de Q y R;
Experiencia en el código:
Con respecto al método de bucle, al principio, lo que pensaba era escribir un método para resolver divisores comunes, usar una matriz entera para almacenar todos los divisores comunes de un entero no negativo, y luego comparar y descubrir el divisor común más grande común en P y Q, que es el mayor divisor común de dos números. Más tarde, pensé, ya que es encontrar el máximo, ¿no sería más fácil disminuir directamente desde la parte posterior al frente? La disminución de la parte posterior a la parte delantera puede garantizar que este número sea siempre el más grande en la actualidad, porque las personas que son más grandes de lo que no cumplen con las condiciones (pueden dividirse por P y Q al mismo tiempo) se eliminan, lo que evita el problema de encontrar el máximo inicialmente. Aunque hay muchas maneras de encontrar el máximo, si ha necesitado o no para probar y buscar, jaja, ¿por qué se siente un poco sobre la filosofía?
Con respecto a la recursión, lo que puedo entender completamente en base a mi intuición es la única oración que el mayor divisor común de P y Q es el mayor divisor común de Q y R (r = P%q), que es el comienzo del anillo, pero todavía no entiendo que la condición final del anillo es 0, y return P;
Aunque es una solución muy simple para el mayor algoritmo de divisor común, tengo que escribirlo de dos maneras, principalmente para sentir el método de recursión con el que no estoy muy familiarizado. En el pasado, vi la fórmula clara del algoritmo de recursión para resolver la Torre Hannover y los números de Fibonacci que se iluminó allí, ¡y estaba suspirando que esto es completamente matemático! La sensación que aprendí hoy fue aún más impactante que ese momento. Me preguntaba qué pasó y lo resolví extrañamente. En ese momento, no me importaba mucho la memoria, la eficiencia y otros indicadores. Solo pensé que los chicos que podían pensar en esto eran realmente inteligentes. Para ellos, ya sea una computadora o un lenguaje de programación, era solo una herramienta para resolver el problema. Algunas personas dicen que la recursión es un algoritmo que permite que el cerebro piense en las computadoras calcule, y se siente realmente apropiado.
Referencias
Serie de programación Turing: Algoritmos (4ª edición) Robert Sedgewick (autor), Kevin Wayne (autor), Xie Luyun (traductor)
Para obtener más información sobre los algoritmos de Java, los lectores interesados en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""
Espero que este artículo sea útil para la programación Java de todos.