Nessa aula, vamos ver algoritmos um pouco mais elaborados. Mas, sabendo que vamos usar algo com um maior grau de sofisticação, que tal pensar em testes?
De uma forma geral, para verificar o funcionamento de um programa, podemos escrever testes que verificam o funcionamento em algumas situações específicas.
Dado que o primeiro problema que queremos resolver é um algoritmo que encontra o n-ésimo número de Fibonacci. Por que não começar com testes?
Uma forma de se fazr testes, e de forma manual, mas isso não é reprodutível. A melhor maneira de se fazer testes, é de forma automatizada, ou seja criar código que teste código. Isso pode parecer complicado, mas vamos ver abaixo que não é.
Em uma busca rápida, podemos ver que a sequência de Fibonacci é definida da seguinte forma, os dois primeiros elementos \(F_1\) e \(F_2\) valem 1, em seguida temos a fórmula \(F_n = F_{n-1} + F_{n-2}\). Mas, antes de pensar em resolver o problema vamos pensar em como testar.
Já sabemos os primeiros valores, além disso, através de uma busca rápida, podemos descobrir alguns valores da sequência como \(F_5 = 5\) e \(F_{12} = 144\). Supondo que a função para o cálculo do n-ésimo número de Fibonacci chamará fibo(). Podemos escrever o seguinte trecho de código:
function testafibo_versao1()
if fibo(1) == 1
println("Deu certo para 1")
end
if fibo(2) == 1
println("Deu certo para 2")
end
if fibo(5) == 5
println("Deu certo para 5")
end
if fibo(12) == 144
println("Deu certo para 12")
end
println("Final dos testes")
endtestafibo_versao1 (generic function with 1 method)A função de testes acima verifica se a função fibo() devolve o resultado correto para três casos. Mas, ela tem um defeito, ela imprime mensagens demais, o que pode ser ruim. Considerando isso, vamos ver o primeiro fundamento importante com relação a testes automatizados.
Se o teste passou, ele deve indicar apenas que deu certo!
Levando em conta o que foi escrito acima, podemos mudar o nosso teste para:
function testafibo()
if fibo(1) != 1
println("Não deu certo para 1")
end
if fibo(2) != 1
println("Não deu certo para 2")
end
if fibo(5) != 5
println("Não eu certo para 5")
end
if fibo(12) != 144
println("Não deu certo para 12")
end
println("Final dos testes")
endtestafibo (generic function with 1 method)Agora de posse da nossa função de testes, podemos pensar em escrever a nossa função de Fibonacci. Vamos ao caso fácil de n for menor que 2, a resposta é 1. Como vemos abaixo:
function fibo(n)
if n <= 2
return 1
else
# ainda não sabemos o que colocar aqui...
end
endfibo (generic function with 1 method)Mas, a resposta está na própria definição da função, ou seja: \(F_n = F_{n-1} + F_{n-2}\). Se o \(n\) for maior do que 2, temos que fazer a soma dos valores de Fibonacci de \(n-1\) e de \(n-2\). Ou seja:
function fibo(n)
if n <= 2
return 1
else
return fibo(n - 1) + fibo(n - 2)
end
end
fibo(10)55É interessante notar que apesar de ser um dos exemplos clássicos de uso de recursão, o algoritmo acima é extremamente ineficiente. A razão é simples, cada vez que é feita a chamada, toda os valores de Fibonacci são recalculados para os valores de \(n\) e \(n-1\).
Como Julia é uma linguagem moderna podemos usar o conceito de Memoização, que evita calcular o que já foi calculado. O Memoize tem que ser instalado no Julia com os comandos import Pkg e Pkg.add("Memoize").
using Memoize
@memoize function fibo(n)
if n <= 2
return 1
else
return fibo(n - 1) + fibo(n - 2)
end
end
fibo(10)55As diferenças de tempo das duas versões podem ser verificada com o comando @time. Da seguinte forma:
@time fibo(10) 0.000001 seconds55Esse tipo de comando, que começa com @ é conhecido como anotação, e tem o poder de mudar o comportamente de partes do código.
Vamos ao segundo algoritmo da aula, o MDC (Máximo Divisor Comum). A ideia é usar o algoritmo de Euclides.
Basicamente ele diz que o MDC de dois números a e b, é igual ao MDC de b e r, onde \(r=a\% b\). Quando esse resto for zero, chegamos a solução, que é b.
Vamos começar com os testes para alguns valores bem conhecidos. Por sinal começar pelos testes antes de escrever o código é uma boa prática de programação conhecida por TDD (Test Driven Design).
function testaMDC()
if MDC(3298, 2031) != 1
println("deu erro, para 3298 e 2031")
end
if MDC(120, 36) != 12
println("deu erro, para 120 e 36")
end
if MDC(36, 120) != 12
println("deu erro, para 36 e 120")
end
println("Acabaram os testes")
endtestaMDC (generic function with 1 method)Vamos pensar na função agora. Dessa vez, se o resto for 0, temos que devolver o segundo termo. Caso contrário temos que continuar com a regra
function MDC(a, b)
r = a % b
if r == 0
return b
else
return MDC(b, r)
end
end
testaMDC()Acabaram os testesAté agora usamos o modo interativo do Julia para fazer os nosso códigos. Mas, existe oura forma bem mais reutilizável, ou seja escrever o texto em arqivos. Isso é relativamente simples, basta usar um editor de texto (puro) da sua preferência, como o notepad, nano, juno, atom, vscode ou outro e salvar um arquivo com a extensão .jl.
Mas, para que algo seja executado é importante colocar uma chamada ao final. Veja abaixo um possível arquivo mdc.jl.
function testeMDC()
if mdc(70, 5) != 5
println("Não funcionou para 70 e 5")
end
if mdc(13, 7) != 1
println("Não funcionou para 13 e 7")
end
if mdc(127, 15) != 1
println("Não funcionou para 127 e 15")
end
if mdc(20, 15) != 5
println("Não funcionou para 20 e 15")
end
if mdc(42, 3) != 3
println("Não funcionou para 42 e 3")
end
if mdc(42, 8) != 2
println("Não funcionou para 42 e 8")
end
println("Final dos testes")
end
function mdc(a, b)
r = a % b
if r == 0
return b
else
mdc(b, r)
end
end
testeMDC()
println("O mdc entre 1227 e 321 é ", mdc(1227, 321))Final dos testes
O mdc entre 1227 e 321 é 3