Algoritmos para passar o dia

Selecionei alguns algoritmos com os quais esbarrei durante o ano passado, mas acabei tendo pouco tempo para estudá-los com detalhes. São eles: crivo de Eratóstenes, algoritmo de Euclides e algoritmo de O'Beirne. Então aqui vou eu.

Crivo de Eratóstenes

Antes que me perguntem: sim, um crivo é uma peneira (por: albino vieira filhos).

O crivo de Eratóstenes é um algoritmo simples para achar todos os números primos até um inteiro n. Nossa estratégia será a seguinte:

1) Obter números do intervalo [2, n];

2) Deletar os números maiores que e divisíveis por 2;

3) Obter próximo primo p;

4) Se p for menor que a raíz quadrada de n, então:

4.1) Deletar os números maiores que e divisíveis por p;

4.2) Ir ao passo 3;

5) Senão:

5.1) Ir ao passo 6;

6) Fim.

Nada do outro mundo, mas não deixa de ser um algoritmo interessante. Bem, mas vamos "botar a mão na obra" implementando em Python:

import math

def crivo(n):

primos = []

p = 2

aux = 0

#Preencher a array primos com todos os valores de 2 a n.
for x in range(2, n):

primos += [x]

#Loop principal: processo de seleção de números primos.
while(p < math.sqrt(n)):

for x in primos:

if(x % p == 0 and x != p):

primos.remove(x)

aux += 1

p = primos[aux]

return primos

print 'Demonstração do crivo de Eratóstenes.'

n = input('Entre com um valor: ')

print ('Os números primos entre 2 e %s são %s' % (n, crivo(n)))

Algoritmo de Euclides

Euclides era um daqueles sujeitos que não cansam de ser bons.

O algoritmo de Euclides é um método bem prático para encontrar o MDC entre dois números, baseado em divisões sucessivas. Havendo dois números a e b, com a > b, o MDC pode ser calculado da seguinte forma:

1) Divida a por b e obtenha o resto;

2) Se o resto for 0, então:

2.1) O MDC entre a e b é b;

2.2) Ir ao passo 4;

3) Senão:

3.1) O número b torna-se o número a e o resto torna-se b;

3.2) Ir ao passo 1.

4) Fim.

Vamos testar com dois exemplos. Primeiro, calcular o mdc entre 20 e 4:

1) Dividindo 20 por 4, obtemos o resto 0;

2) O resto é 0, então:

2.1) O MDC entre 20 e 4 é 4;

2.2) Ir ao passo 4.

4) Fim.

Agora, entre 15 e 10.

1) Dividindo 15 por 10, obtemos o resto 5;

2) O resto é 0? Falso, ir ao passo 3;

3) O resto não é 0:

3.1) 10 torna-se a e 5 torna-se b;

3.2) Ir ao passo 1;

1) Dividindo 10 por 5, obtemos o resto 0;

2) O resto é 0, então:

2.1) O MDC entre 15 e 10 é 5;

2.2) Ir ao passo 4;

4) Fim.

Simples, não? Vamos implementar em Python (estou certo de haver uma implementação mais elegante, mas foi o que pensei na hora):

def mdc(a, b):

resto = 1

#Assegurar que a e b sejam números naturais não-nulos.

if(a <= 0 or b <= 0):

return 'opa, erro. Pelo menos um dos números é negativo ou nulo.'

#Assegurar que a seja o maior e b o menor número.

maior = (a + b + abs(a - b))/2

menor = (a + b - abs(a - b))/2

a = maior

b = menor

#Loop principal.

while(True):

resto = a % b

if(resto == 0):

break

else:

a = b

b = resto

return b

print 'Demonstração do algoritmo de Euclides.'

a = input('Digite o número a: ')

b = input('Digite o número b: ')

print ('O MDC entre %s e %s é... %s' % (a, b, mdc(a, b)))

Algoritmo de O'Beirne

Já aproveito para desejar Feliz Páscoa... um tanto adiantado, por sinal (fonte).

O algoritmo de O'Beirne é uma simples sequência matemática, com dez passos, para determinar a data do domingo da Páscoa em um ano x. Claro que a partir dele podemos calcular a terça-feira de carnaval, a sexta-feira santa e o Corpus Christi. Seja x o ano:

1. Divide-se x por 100 e anota-se o quociente (b) e o resto (c);

2. Toma-se 5b+c e divide-se por 19; chama-se a ao resto;

3. Calcula-se 3(b+25) e divide-se por 4; designa-se o quociente por δ e o resto por ɛ;

4. Calcula-se 8(b+11) e divide-se por 25; anota-se o valor do quociente (γ);

5. Calcula-se 19a+δ-γ e divide-se por 30; anota-se o valor do resto (h);

6. Calcula-se a+11h e divide-se por 319; anota-se o valor do quociente (μ);

7. Calcula-se 60(5-ɛ)+c e divide-se por 4; anota-se o valor do quociente (j) e do resto (k);

8. Calcula-se 2j-k-h+μ e divide-se por 7; anota-se o valor do resto (λ);

9. Calcula-se h-μ+λ+110 e divide-se por 30; anota-se o valor do quociente (n) e do resto (q);

10. Calcula-se q+5-n e divide-se por 32; o quociente deve ser nulo e ao resto chama-se p.

Ao fim dos 10 passos, o Domingo de Páscoa será no dia p do mês n do ano x. Novamente, agora a implementação em Python:

import datetime

def pascoa(x):

b = x / 100

c = x - 100 * b

a = (5 * b + c) % 19

d = (3 * (b + 25)) / 4

e = (3 * (b + 25)) % 4

g = (8 * (b + 11)) / 25

h = (19 * a + d - g) % 30

m = (a + 11 * h) / 319

j = (60 * (5 - e) + c) / 4

k = (60 * (5 - e) + c) % 4

l = (2 * j - k - h + m) % 7

n = (h - m + l + 110) / 30

q = (h - m + l + 110) % 30

quociente = (q + 5 - n) / 32

p = q + 5 - n

if quociente != 0:

return 'Erro!'

else:

return datetime.date(x, n, p)

print 'Demonstração do algoritmo de O\'Beirne.'

x = input('Entre com um ano: ')

pascoa = pascoa(x)

if(pascoa == 'Erro!'):

print 'Ops, deu erro.'

exit

carnaval = pascoa - datetime.timedelta(47)

sexta_santa = pascoa - datetime.timedelta(2)

corpus = pascoa + datetime.timedelta(60)

print('''No ano de %s, a Páscoa será em %s, o carnaval em %s, a sexta-feira

santa em %s e Corpus Christi em %s''' % (x, pascoa, carnaval, sexta_santa, corpus))