Este artigo descreve o algoritmo de Java para resolver o maior divisor comum de dois números inteiros não negativos. Compartilhe -o para sua referência, como segue:
Funções de código:
1. Implementação Java (código -fonte completo com casos de teste);
2. Resolva o maior divisor comum de dois números inteiros não negativos p e q (p> = q);
3. Duas soluções: método de loop e método recursivo;
Código fonte completo:
/ * GCD: Greatheast Common Divisor */public class GCD {public static void main (string args []) {/ * case de teste */int p = 32; int q = 24; System.out.println ("O maior divisório de"+p+"e"+q+"is /n"+"[gcd1]:"+gcd1 (p, q)+" /n"+"[gcd2]:"+gcd2 (p, q)); } // (q % gcd == 0 e 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; quebrar; }} retornar GCD; } // gcd (p, q) = gcd (q, p%q) [se q = 0, gcd = p] public static int gcd2 (int p, int q) {if (q == 0) retornar p; int r = p%q; //System.out.println("("+q+","+R+ ")"); retornar gcd2 (q, r); }}Running Screenshot:
Explicação de código:
Método circular GCD1 (P, Q)
Descrição da linguagem natural: O método de loop resolve o maior divisor comum de dois números inteiros não negativos P, Q (p> = Q), ou seja, resolve o valor máximo do divisor comum de Q que é p. Seja D (dividido) decremento de p (etapa de decréscimo = 1) D é sempre "o valor máximo da condição que está prestes a ser satisfeita". Quando D atende à condição (ela pode ser dividida por P e divisível por P), D é o divisor comum de P e Q, e D é o maior divisor comum de P e Q;
Método recursivo GCD2 (P, Q)
Descrição da linguagem natural: O método recursivo resolve o maior divisor comum de dois números inteiros não negativos P, Q (p> = q). Quando Q é igual a 0, o maior divisor comum é P; Caso contrário, pegue o restante de p e q para obter r = p%q, e o maior divisor comum de P e Q é o maior divisor comum de Q e R;
Experiência de código:
Em relação ao método de loop, no início, o que eu pensava era escrever um método para resolver divisores comuns, usar uma matriz inteira para armazenar todos os divisores comuns de um número inteiro não negativo e, em seguida, comparar e descobrir o maior divisor comum comum em P e Q, que é o maior divisor comum de dois números. Mais tarde, pensei, como é encontrar o máximo, não seria mais fácil diminuir diretamente das costas para a frente? Diminuir das costas para a frente pode garantir que esse número seja sempre o maior no momento, porque as pessoas que são maiores do que não atendem às condições (podem ser divididas por P e Q ao mesmo tempo) são eliminadas, o que evita o problema de encontrar o máximo inicialmente. Embora existam muitas maneiras de encontrar o máximo, se você tiver ou não precisar provar e pesquisar, haha, por que você se sente um pouco sobre filosofia?
Em relação à recursão, o que eu posso entender completamente com base na minha intuição é a única frase de que o maior divisor comum de P e Q é o maior divisor comum de Q e R (r = P%Q), que é o começo do anel, mas ainda não entendo bem que a condição final do anel é 0 e retorna p;
Embora seja uma solução muito simples para o maior algoritmo de divisor comum, tenho que escrever de duas maneiras, principalmente para sentir o método de recursão com o qual não estou muito familiarizado. No passado, vi a fórmula clara do algoritmo de recursão para resolver os números Hannover Tower e Fibonacci que foi iluminado lá, e eu estava suspirando que isso é completamente matemático! O sentimento que aprendi hoje foi ainda mais chocante do que aquela época. Eu me perguntei o que aconteceu e resolveu estranhamente. Naquela época, eu não me importava muito com memória, eficiência e outros indicadores. Eu apenas pensei que os caras que podiam pensar nisso eram realmente inteligentes. Para eles, seja um computador ou uma linguagem de programação, era apenas uma ferramenta para resolver o problema. Algumas pessoas dizem que a recursão é um algoritmo que permite que o cérebro pense nos computadores calcular, e parece realmente apropriado.
Referências
Turing Programming Series: Algoritmos (4ª edição) Robert Sedgewick (autor), Kevin Wayne (autor), Xie Luyun (tradutor)
Para obter mais informações sobre os algoritmos Java, os leitores interessados neste site podem visualizar os tópicos: "Estrutura de dados Java e tutorial de algoritmo", "Resumo das dicas de nó da operação Java Dom", "Resumo de dicas de operação de Java e Operação de Java" e "Resumo de Java cache" Tips "TIPS"
Espero que este artigo seja útil para a programação Java de todos.