Encontrando o maior divisor comum em TypeScript
Primeiramente descrito no clássico livro de geometria Elementos, pelo matemático grego antigo Euclides (cerca de 300 a.C., no livro VII, proposição 2), o método de encontrar o maior divisor comum entre os números positivos e , sendo , consiste no conhecimento de que os divisores comuns de e são os mesmos de e . Portanto, podemos encontrar esse maior divisor comum substituindo o maior número () pela diferença entre os dois números (), repetidamente, até que os dois números sejam iguais. Em TypeScript, podemos fazer isso assim:
Este método pode ser muito lento se a diferença entre e for muito grande. Felizmente, existe outro método para encontrar o maior divisor comum entre dois números, que pode ser descrito da seguinte forma:
Para encontrar o maior divisor comum entre e , sendo , realize a divisão entre os dois números. Esta operação dará um quociente e um resto (que chamaremos de e , respectivamente). Assim, pode ser descrito como ; Se for igual a 0, paramos, porque descobrimos que o maior divisor comum de e é . Caso contrário, voltamos ao passo 1, fazendo de o novo e será o novo . Agora, podemos começar com a implementação do algoritmo acima:
A implementação é muito direta e pode ser lida exatamente como descrita nos passos 1 e 2. Podemos tornar a função mais simples, verificando diretamente se é igual a zero e só realizando a operação de resto depois disso. Portanto, se a função receber um que seja igual a zero, saberemos que é o maior divisor comum:
Esta variante é chamada de algoritmo euclidiano (em contraste com a primeira, que é o algoritmo de Euclides) e é significativamente mais rápida do que a primeira implementação.
Implementações alternativas
Também podemos adotar uma abordagem diferente. Em vez de chamar nossa função gcd recursivamente, podemos implementar nossa função usando um laço while
(análogo à nossa primeira implementação acima):
E esta é outra maneira (análoga à nossa segunda implementação acima):
Encontrando o maior divisor comum entre três ou mais números
O maior divisor comum de três ou mais números é igual ao produto dos fatores primos comuns a todos os números (exploraremos mais isso em um futuro artigo), mas, você também pode calcular o maior divisor comum entre pares desta lista de números com as mesmas funções que já mostramos. Então, vamos refatorar nossa funçãogcd
para receber múltiplos parâmetros:
Validando nossas entradas
Vamos garantir que nossas funções devem sempre receber, pelo menos, dois números e que todos os números deve ser positivos: