Neste exemplo, você aprenderá a encontrar o GCD de dois números usando dois métodos diferentes: função e loops e algoritmo Euclidiano
Para entender este exemplo, você deve ter conhecimento dos seguintes tópicos de programação Python:
- Funções Python
- Python Recursion
- Argumentos da função Python
O maior fator comum (HCF) ou o maior divisor comum (GCD) de dois números é o maior inteiro positivo que divide perfeitamente os dois números fornecidos. Por exemplo, o HCF de 12 e 14 é 2.
Código fonte: usando loops
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Resultado
O HCF é 6
Aqui, dois inteiros armazenados nas variáveis num1 e num2 são passados para a compute_hcf()função. A função calcula o HCF desses dois números e os retorna.
Na função, determinamos primeiro o menor dos dois números, pois o HCF só pode ser menor ou igual ao menor número. Em seguida, usamos um forloop para ir de 1 a esse número.
Em cada iteração, verificamos se nosso número divide perfeitamente os dois números de entrada. Nesse caso, armazenamos o número como HCF. Na conclusão do loop, terminamos com o maior número que divide perfeitamente ambos os números.
O método acima é fácil de entender e implementar, mas não é eficiente. Um método muito mais eficiente para encontrar o HCF é o algoritmo euclidiano.
Algoritmo euclidiano
Este algoritmo é baseado no fato de que o HCF de dois números também divide sua diferença.
Nesse algoritmo, dividimos o maior pelo menor e pegamos o restante. Agora, divida o menor por este resto. Repita até que o resto seja 0.
Por exemplo, se quisermos encontrar o HCF de 54 e 24, dividimos 54 por 24. O restante é 6. Agora, dividimos 24 por 6 e o restante é 0. Portanto, 6 é o HCF necessário
Código-fonte: Usando o Algoritmo Euclidiano
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Aqui, fazemos um loop até que y se torne zero. A instrução x, y = y, x % yfaz a troca de valores em Python. Clique aqui para saber mais sobre como trocar variáveis em Python.
Em cada iteração, colocamos o valor de y em xe o restante (x % y)em y, simultaneamente. Quando y torna-se zero, temos HCF em x.
