Maior divisor comum com python

Um fator é um número que pode entrar em outro número sem um restante. Um dividendo divide um divisor para dar o quociente. Se o dividendo e o divisor for um número inteiro e se o quociente tiver um restante de zero (sem restante), o divisor é chamado de fator do dividendo. O maior divisor comum é abreviado, g.C.D ou simplesmente GCD. Outro nome para o maior divisor comum é o maior fator comum, abreviado H.C.F.

Encontrando g.C.F por definição

O problema é encontrar o maior fator comum também chamado de maior divisor comum para os números 108 e 240.

Solução:

Todos os fatores maiores que 1 são colocados na tabela a seguir:

108: 2 3 4 6 9 12 18 27 36 54 108
240: 2 3 4 5 6 8 10 12 15 16 20 24 30 48 60 120 240

A primeira linha tem os fatores de 108 em ordem crescente. A segunda linha tem os fatores de 240 em ordem crescente.

Fatores comuns (divisores) para 108 e 240 são: 2, 3, 4, 6 e 12.

Por inspeção, o maior fator (divisor) que é comum aos números 108 e 240 é 12. Isto é, GCD ou H.C.F para 108 e 240 é 12.

Escrever um programa que encontrará o GCD, como explicado acima, levará muito tempo. Dois métodos mais curtos para encontrar o GCD são: GCD por subtração e GCD por divisão.

GCD por subtração

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

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

Aquilo é:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Que significa:

108 + 132 = 240

Se o GCD puder ser adicionado repetidamente para fornecer qualquer um dos números (108 e 240) do qual o GCD é necessário, pode ser possível fazer algum tipo de subtração repetidamente, começando com os números especificados para ter o GCD. De fato, é possível fazer um tipo específico de subtração repetidamente e obter o GCD. Isso começa com a diferença dos números dados.

Problema: Encontre o maior divisor comum (fator comum mais alto) para 108 e 240 por subtração.

Solução:

240 - 108 = 132
132 - 108 = 24
108 - 24 = 84
84 - 24 = 60
60 - 24 = 36
36 - 24 = 12
24 - 12 = 12
12 - 12 = 0

Entre 108 e 240, 240 é o número maior. Após a diferença desses números dados, a diferença da diferença resultante (132 para a primeira etapa) e o subtrahend (108 para a primeira etapa) são obtidos repetidamente até que a diferença final seja zero. Nas etapas, o número menor é subtraído do 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' for 1 e B for 6, as etapas sem programação serão:

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

O GCD aqui é 1. Existem seis etapas aqui e não sete 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 função do maior divisor comum por subtração, em Python, é:

Def GCDS (a, b):
Se A == b:
retornar a
Se A> B:
Retorne GCDs (A - B, B)
outro:
Retorne GCDs (A, B - A)

A primeira declaração cuida da última etapa de matemática. A próxima declaração composta (se/else) faz a subtração entre o minuend e a diferença, dependendo de qual é maior.

Veja profundamente as subtrações matemáticas do GCD

240 - 108 = 132
132 = 12 x 11 (132 tem 12 como fator)
132 - 108 = 24
24 = 12 x 2 (24 tem 12 como fator)
108 - 24 = 84
84 = 12 x 7 (84 tem 12 como fator)
84 - 24 = 60
60 = 12 x 5 (60 tem 12 como fator)
60 - 24 = 36
36 = 12 x 3 (36 tem 12 como fator)
24 - 12 = 12
12 = 12 x 1 (12 tem um fator ou 12 - em si)
24 - 12 = 12
12 = 12 x 1 (12 tem um fator ou 12 - em si)

O último passo tem a diferença de 0. Marca o fim das etapas da subtração e dá o GCD como subtrahendo ou minuenda.

GCD por divisão

Entre 108 e 240, o GCD é maior que 1.

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

Aquilo é:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Que significa:

108 + 132 = 240

Aquilo é:

12 x 9 + 12 x 11 = 240

Além disso, 108 = 12 x 9 e 240 = 12 x 20.

Agora, se o GCD puder ser multiplicado por um número inteiro (número inteiro positivo) para fornecer qualquer um dos números (108 ou 240) do qual o GCD é necessário, pode ser possível fazer algum tipo de divisão repetidamente, começando com o dados números para ter o GCD. De fato, é possível fazer um tipo específico de divisão repetidamente e obter o GCD. Esta divisão é uma divisão de módulo de repetição especial. Começa com a divisão do módulo dos números dados.

Na divisão Modulus, quando o dividendo é dividido pelo divisor, o restante do quociente é a resposta.

Problema: Encontre o maior divisor comum (fator comum mais alto) para 108 e 240 pela Divisão de Modulus:

Solução:

240 % 108 = 24 (i.e. 2 r 24)
108 % 24 = 12 (i.e. 4 r 12)
24 % 12 = 0 (i.e. 2 r 0)

Na última linha, onde o restante é zero, o divisor é o maior divisor comum (maior fator comum).

Este problema é encontrar o GCD entre 108 e 240 por divisão. A solução aqui deu 3 passos. O problema anterior era semelhante, mas era procurar o mesmo GCD por subtração; E tinha 8 etapas. Embora a complexidade do tempo para o método de subtração seja O (a + b), a complexidade do tempo para o método de divisão é O (log (a + b)).

Na divisão de módulos, não importa se 'a' é maior que B ou B é maior que 'A'; o restante é o mesmo número inteiro positivo.

Encontre matematicamente, o maior divisor comum por divisão, para os números, 5 e 2.

Solução:

5 % 2 = 1
1 % 1 = 0

O GCD é 1. Isso precisava de duas etapas matemáticas.

Codificação GCD por divisão

A palavra "Divisão" aqui se refere à divisão de módulos. A função é:

Def GCDD (a, b):
if (a % b == 0):
retornar b
outro:
Retornar GCDD (B, A % B)

A parte IF do if/elle-construir cuida da última declaração matemática, para as etapas da Divisão de Modulus. A parte else cuida da divisão de módulo real (resultando no restante). Na divisão de módulos, não importa se 'a' é maior que B ou B é maior que 'A'; o restante é o mesmo número inteiro positivo.

Para ligar e imprimir um GCD, o código a seguir pode ser usado:

ret = gcdd (240, 108)
Imprimir (ret, end = '\ n')

Observe as divisões de matemática do GCD

240 % 108 = 24 (o GCD entre 240 e 108 é 12)
24 = 12 x 2 (24 tem 12 como fator)
108 % 24 = 12 (o GCD entre 108 e 24 é 12)
12 = 12 x 1 (12 tem 12 como fator, por si só)
24 % 12 = 0 (o GCD entre 24 e 12 é 12)

Foi demonstrado aqui, 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. Assim, 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. Isso diminui em etapas diferentes até que o restante seja zero, mesmo que o GCD seja 1.

O último passo tem um restante de 0. Marca o fim das etapas da divisão do módulo e o GCD é o divisor.

Conclusão

O maior divisor comum pode ser determinado por subtrações repetidas ou divisões de módulo repetidas.

Se for por subtração, após a subtração dos números dados, o restante das subtrações está entre a diferença e o minuenda, dependendo de qual é maior. Quando a diferença é zero, o subtrahend é igual ao minuenda, e qualquer um é o GCD.

Se for por divisão, as divisões repetidas são divisões de módulo. Nesta situação, após a divisão do módulo dos números dados, o restante das divisões do módulo está entre o divisor e o restante, dependendo de qual é maior. Quando o restante é zero, o divisor é o GCD. 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.