.NET - O Algoritmo de Euclides
.NET - O Algoritmo de Euclides
EUCLIDES, (360-300 a.c.) nasceu na Síria e foi um dos maiores matemáticos de todos os tempos.
Euclides teve um grande prestígio devido a forma brilhante como ensinava Geometria e Álgebra. Lecionava na Escola de Alexandria para onde foi convidado pelo rei Ptolomeu do Egito.
Euclides demonstrou que os números primos formam uma sucessão infinita. Elaborou também, um resultado importante: O ALGORÍTMO de EUCLIDES (assunto deste artigo.)
O algoritmo de Euclides é um método simples e eficiente de encontrar o máximo divisor comum(MDC) entre dois números inteiros diferentes de zero. É um dos algoritmos mais antigos, conhecido desde que surgiu nos Livros VII e X da obra Elementos de Euclides por volta de 300 a.C. O algoritmo não exige qualquer fatoração.
O ALGORÍTMO DE EUCLIDES aparece como solução à Proposição VII-2 da obra ELEMENTOS:
Dados dois números inteiros não negativos a e b, não primos entre si, é sempre possível encontrar o máximo divisor comum entre eles ( MDC(a,b) ).
O roteiro para calcular o maior divisor comum - MDC - entre dois números X e Y onde X > Y pode ser descrito da seguinte forma:
Assim o MDC de dois números inteiros é o maior número inteiro que divide ambos sem deixar resto.
Ex: Determinar o máximo divisor comum entre os números 17154 e 357.
MDC(17154,357) ?
 |
O máximo divisor comum - MDC é o último resto diferente de zero, que é igualmente o último dividendo, ou seja MDC(17154,357)=3.
Implementando o Algoritimo de Euclides
Vamos implementar o algoritmo de Euclides de três forma distintas.
A primeira implementação do algoritmo de Euclides vamos criar um método estático com dois parâmetros inteiros e retornar um inteiro que representa o MDC entre os dois números.
O método é estático de forma que ele pode ser chamado facilmente a partir do método principal sem ter que instanciar objetos. (Você pode decidir implementá-lo como um método de instância)
Abra o Visual C# 2010 Express Edition e crie um novo projeto do tipo Windows Forms Application com o nome AlgoritmoEuclides_CSharp;
A seguir no formulário form1.cs inclua os controles Label, Button e TextBox conforme o leiaute abaixo:
 |
No menu Project clique em Add Class e informe o nome MDC.cs;
A seguir digite o código abaixo nesta classe:
| using System; namespace AlgoritmoEuclides_CSharp { public class MDC { public static int GetMDCPorSubtracao(int valor1, int valor2) { while (valor1 != 0 && valor2 != 0) { if (valor1 > valor2) valor1 -= valor2; else valor2 -= valor1; } return Math.Max(valor1, valor2); } } } |
Public Class MDC Public Shared Function GetMDCPorSubtracao(ByVal valor1 As Integer, ByVal valor2 As Integer) As Integer While valor1 <> 0 AndAlso valor2 <> 0 If valor1 > valor2 Then valor1 -= valor2 Else valor2 -= valor1 End If End While Return Math.Max(valor1, valor2) End Function End Class |
| CSharp | VB .NET |
Vamos definir outra implementação para calcular o MDC melhorando um pouco a primeira implementação.
Na primeira implementação o número de iterações no laço while pode ser excessivo. Se um dos dois valores é muito maior do que o outro, quer no início do processo ou mais tarde, com a redução dos valores, o mesmo valor pode ser subtraído muitas vezes.
Podemos reduzir o número de iterações usando o operador módulo.( % no C# e Mod no VB .NET)
Aplicando o operador módulo para os dois valores e trocando o maior valor para o resultado tem o efeito da aplicar múltiplas subtracções simultaneamente.
Por exemplo, se os dois números forem o 10 e o 3, o 3 seria subtraído três vezes para do numero 10 para chegarmos ao valor de resto 1.
Usando o módulo obtemos a valor um em uma única iteração, como 10 % 3 = 1 (10 Mod 3 =1 no VB .NET). Como o resultado do módulo é zero, o MDC foi encontrado.
A seguir o código da implementação em C# e VB .NET com a criação do método GetMDCPorModulo() na classe MDC:
| public static int GetMDCPorModulo(int valor1, int valor2) { while (valor1 != 0 && valor2 != 0) { if (valor1 > valor2) valor1 %= valor2; else valor2 %= valor1; } return Math.Max(valor1, valor2); } |
Public Shared Function GetMDCPorModulo(ByVal valor1 As Integer, ByVal valor2 As Integer) As Integer While valor1 <> 0 AndAlso valor2 <> 0 If valor1 > valor2 Then valor1 = valor1 Mod valor2 Else valor2 = valor2 Mod valor1 End If End While Return Math.Max(valor1, valor2) End Function |
| CSharp | VB .NET |
Vamos fazer mais uma implementação do Algoritmo usando o recurso da recursão para obter o resultado.
O método recursivo tem dois resultados possíveis:
A nova chamada passa o segundo valor, o qual é assumido como sendo o número menor, e o módulo dos dois números.
Cada chamada reduz progressivamente os valores até que o MDC seja encontrado.
Se o segundo inteiro for maior do que o primeiro a chamada inicial irá trocar os valores.
Abaixo temos esta implementação no método GetMDCRecursivo() na linguagem CSharp e VB .NET:
| public static int GetMDCRecursivo(int valor1, int valor2) { if (valor2 == 0) return valor1; else return GetMDCRecursivo(valor2, valor1 % valor2); } |
Public Shared Function GetMDCRecursivo(ByVal valor1 As Integer, ByVal valor2 As Integer) As Integer If valor2 = 0 Then Return valor1 Else Return GetMDCRecursivo(valor2, valor1 Mod valor2) End If End Function |
| CSharp | VB .NET |
Assim vimos o conceito e a implementação do algoritmo de Euclides de 3 formas diferentes possíveis usando a linguagem C# e VB .NET
Pegue os projetos completos
aqui: 
AlgoritmoEuclides_CSharp.zip e
AlgoritmoEuclides_VBNET.zip
1Jo 1:8
Se dissermos que não temos pecado nenhum, enganamo-nos a nós mesmos, e a verdade não está em nós.1Jo 1:9
Se confessarmos os nossos pecados, ele é fiel e justo para nos perdoar os pecados e nos purificar de toda injustiça.1Jo 1:10
Se dissermos que não temos cometido pecado, fazemo-lo mentiroso, e a sua palavra não está em nós.Referências: