Maior divisor comum com java

“O maior divisor comum, o GCD abreviado, também é conhecido como o maior fator comum, abreviado H.C.F.”

Significado do maior divisor comum

Um divisor é um número inteiro (número inteiro) que entrará em outro número inteiro sem um restante. O maior divisor comum é melhor explicado com uma ilustração. A tabela a seguir mostra dois números: 60 e 108, com todos os seus divisores maiores que 1.

Existem divisores na tabela que não são comuns a 60 e 108. No entanto, 2 é um divisor comum para os números 60 e 108, mas não é o maior divisor comum a 60 e 108. Divisor 3 é descrito de maneira semelhante. Por inspeção da tabela, o maior divisor que é comum a 60 e 108 é 12. Nenhum divisor acima de 12 é comum em 60 e 108. Então 12 é o maior divisor comum para 60 e 108.

O objetivo deste artigo é explicar como obter o maior divisor comum por subtração ou divisão; Com a programação feita em java.

GCD por subtração

Por inspeção da tabela acima, o GCD para 60 e 108 é 12. Isso significa que se 12 for adicionado repetidamente, o resultado se tornará 60, o menor dos dois números. Se a adição de 12 continuar, o resultado se tornará 108, maior dos dois números. Aquilo é:

12 + 12 +12 +12 + 12 = 60

12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108

Aquilo é:

60 + 12 + 12 + 12 + 12 = 108

Que significa:

60 + 48 = 108

Se a adição de GCD puder levar a ambos os números, talvez alguma forma de subtração contínua para baixo possa levar ao GCD. Isso é um fato, conforme ilustrado pelas etapas a seguir, começando com a diferença de 108 e 60:

108 - 60 = 48
60 - 48 = 12
48 - 12 = 36
36 - 12 = 24
24 - 12 = 12
12 - 12 = 0

Entre 60 e 108, 108 é o número maior. Depois disso, a diferença da diferença resultante (48 para a primeira etapa) e o subtrahend (60 para o primeiro passo) são obtidos repetidamente até que a resposta seja zero. Nas etapas, o número menor é subtraído, o número maior. Na última etapa, o minuenda e o subtrahend são os mesmos. Esse mesmo valor é o maior divisor comum.

Deixe os números cujo GCD é necessário ser A e B. Se esses números não têm GCD maior que 1, significa que seu maior divisor comum é 1. Na programação, a complexidade do tempo para encontrar o GCD por subtração é O (a+b). Se A é 1 e B for 5, as etapas sem programação serão:

5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0

O GCD aqui é 1. Existem cinco etapas aqui e não seis etapas por (a + b). No entanto, na programação, o número máximo possível de operações de código é o que é considerado como a complexidade do tempo.

Codificação GCD por subtração

A classe e o método para o maior divisor comum por subtração em Java são:

classe GCDS
int gcds (int a, int b)
se (a == b)
retornar a;
se (a> b)
retornar GCDs (A-B, B);
retornar GCDs (A, B-A);

Começa com uma declaração para a última etapa matemática quando os dois números resultantes são iguais. As próximas duas declarações subtraem o número menor do número maior recursivamente. Uma classe principal de Java e o método principal Java, para ir com a classe acima, é:

classe pública principal
public static void main (string args [])
Gcds obj = new gcds ();
int ret = obj.GCDS (108, 60);
Sistema.fora.println (ret);

A saída é 12.

GCD por divisão

A tabela acima é repetida aqui para facilitar a referência:

Os dois números cujo GCD é necessário são 60 e 108, sendo 108 o número maior. A explicação acima para a subtração começou com:

12 + 12 +12 +12 + 12 = 60

12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108

Aquilo é:

60 + 12 + 12 + 12 + 12 = 108

Que significa:

60 + 48 = 108

Divisão Modulo é uma divisão em que a resposta é todo o número parte do quociente, e o restante também é levado em consideração. Considere o restante ao dividir 108 por 60 e restantes dos quocientes resultantes e seus divisores correspondentes.

108 % 60 = 48 (i.e 1 r 48)
60 % 48 = 12 (i.e 1 r 48)
48 % 12 = 0 (i.e 4 r 0)

A divisão do módulo termina quando o restante é 0. O GCD é o divisor da última etapa. Já se sabia, do outro método acima, que o maior divisor comum é 12.

108 mod 60 não é zero. Se o GCD entre 60 e 108 tivesse que ser encontrado por subtração, a primeira diferença para o GCD entre 60 e 108 seria 48, e pode -se mostrar que o GCD entre 60 e 108 é 12. 60 mod 48 não é zero. Se o GCD entre 60 e 48 (o restante anterior) tivesse que ser encontrado por subtração, a primeira diferença para o GCD entre 60 e 48 seria 12, e pode -se mostrar que o GCD entre 60 e 48 é 12. 48 mod 12 é zero e tem 0 restos. Se o GCD entre 48 e 12 tivesse que ser encontrado por subtração, a primeira diferença para o GCD entre 48 e 12 seria 36. 36 não é o GCD entre 48 e 12; No entanto, 36 é um múltiplo de 12, que é o GCD.

Usando qualquer meio, o leitor pode provar com as etapas acima que, dado que o GCD para 60 e 108 é 12, o GCD para 60 e 48 também é 12; e o GCD para 48 e 12 ainda é 12.

Considere outro exemplo para encontrar o GCD pela divisão. O problema agora é: encontrar o GCD por divisão para os números 18 e 30.

Solução:

30 % 18 = 12 (i.e. 1 r 12)
18 % 12 = 6 (i.e. 1 r 6)
12 % 6 = 0 (i.e. 2 r 0)

O GCD é 6, lido da última linha, onde o módulo é 0.

30 mod 18 não é zero. Se o GCD entre 30 e 18 tivesse que ser encontrado por subtração, a primeira diferença para o GCD entre 30 e 18 seria 12, e pode -se mostrar que o GCD entre 30 e 18 é 6. 18 mod 12 não é zero. Se o GCD entre 18 e 12 tivesse que ser encontrado por subtração, a primeira diferença para o GCD entre 18 e 12 seria 6, e pode -se mostrar que o GCD entre 18 e 12 é 6. 12 mod 6 é zero. Se o GCD entre 12 e 6 tivesse que ser encontrado por subtração, a primeira diferença para o GCD entre 12 e 6 seria 6, e pode -se mostrar que o GCD entre 12 e 6 é 6. 6 também é um múltiplo de 6, que é o GCD.

Usando qualquer meio, o leitor pode provar com as etapas acima que, dado que o GCD para 30 e 18 é 6, o GCD para 18 e 12 também é 6; e o GCD para 12 e 6 ainda é 6.

Agora considere o GCD obtido de 1 e 5 por divisão:

5 % 1 = 0 (i.e. 5 r 0)

Há apenas um passo (uma linha) aqui. Para encerrar nesta seção, observe que o divisor na última linha, ao procurar o GCD por divisão, é o GCD.

Além disso, observe que:

GCD (A, B) = GCD (B, R)

onde "a" e "b" são dois números inteiros diferentes e "r" é o restante da divisão entre a e "b."" B "pode ​​ser maior que" A "ou" A "pode ​​ser maior que B que B. Isso significa que, se o restante de uma divisão não for zero, o maior divisor comum entre os dois números é o mesmo que o maior divisor comum entre o divisor e o restante. A prova para esta declaração foi ilustrada acima.

Isso pode descer até a divisão Modulo, como experimentado acima até que o restante seja zero. Quando o restante é zero, essa regra de repetição não mantém. Estritamente falando, na divisão Modulus, não importa se "A" é maior que B ou B é maior que "A"; o restante é o mesmo número inteiro positivo.

Codificação GCD por divisão

Se o maior divisor comum pela divisão entre 60 e 108 for necessário matematicamente, as etapas serão

108 % 60 = 48 (i.e 1 r 48)
60 % 48 = 12 (i.e 1 r 48)
48 % 12 = 0 (i.e 4 r 0)

Observe que é o número maior que está dividindo, o número menor. A classe Java e o método para fazer esta divisão é:

classe GCDD
int gcdd (int a, int b)
if (a % b == 0)
retornar b;
retornar GCDD (B, A % B);

A primeira declaração no método é responsável pela última etapa matemática. A segunda declaração faz a divisão Modulo. Ambas as declarações chamam o método recursivamente. A complexidade do tempo para o GCD pela divisão é O (log (a + b)). Uma boa classe principal e o método principal para este código são:

classe pública principal
public static void main (string args [])
Gcdd obj = new gcdd ();
int ret = obj.GCDD (108, 60);
Sistema.fora.println (ret);

A saída é 12.

Conclusão

O maior divisor comum pode ser obtido subtraindo primeiro o número menor do número maior e depois continuando a subtrair o minuend da diferença ou diferença do minuenda, dependendo de qual número é maior.

O maior divisor comum também pode ser obtido dividindo primeiro o número maior pelo número menor usando a divisão de módulo; e continuando a dividir o restante pelo divisor ou pelo divisor pelo restante, dependendo de qual é maior, ainda por divisão de módulo. Estritamente falando, na divisão Modulus, não importa se "A" é maior que B ou B é maior que "A"; o restante é o mesmo número inteiro positivo.

Isso é feito programaticamente recursivamente.