18 de janeiro de 2011

Meu site no ar!

Coloquei hoje meu novo site no ar:
www.guilhermerey.com.br

Espero que gostem!

E calma, 2011 vem aí com promessa de mais posts no blog :)

1 de novembro de 2010

Busca Binária

Olá!

Hoje vamos ver um problema clássico na computação. A busca em um vetor ordenado.
Imagine o problema:

Dado um inteiro x e um vetor v[0 ... n - 1] crescente, encontrar um indice k tal que v[k] == x

Quando fiz um post sobre vetores, descrevi um algoritmo trivial para resolver esse problema. Você pode vê-lo aqui.
O que temos que nos perguntar é: "Tem alguma forma de encontrar o indice que queremos sem precisar comparar x com todos os elementos de v?". E a resposta é: Sim, pequeno padawan.
Para resolver o problema vamos utilizar a busca binária.

Vamos ilustrar essa técnica?
Imagine que você tenha um dicionário na mão e eu peço para você me dar a definição da palavra zootecnia.
Qual característica do dicionário é importantíssima para buscarmos alguma palavra nele?
Ele é ordenado alfabeticamente.
Então o que fazemos? Rasgamos ele no meio, tendo na mão agora dois dicionários menores. Verificamos se a palavra está na página do meio do rasgo. Se sim, pronto, achamos a palavra. Se não, precisamos procurar mais.
Sabemos que a letra Z não está na primeira metade, por isso jogamos ela fora. Então, pegamos a metade que sobrou e rasgamos no meio novamente. De novo vemos se a palavra está na folha do meio. Não? Então pergunte: A letra procurada está na primeira metade? Não, então jogamos fora e ficamos com a outra metade. Mais uma vez rasgamos no meio essa metade, e repetimos o processo. Fazendo isso, um momento acontecerá de sobrar uma página do dicionário, onde estará a letra e a palavra que você procura. E se a palavra não estiver no dicionário, você vai rasgar tudo até sobrar uma folha só, e ela não vai estar lá. E você não precisou comparar sua palavra com todas do dicionário pra descobrir alguma informação.

Isso é a busca binária!
Se queremos encontrar um inteiro x em um vetor crescente v, precisamos apenas dividir ele em dois, depois novamente em dois, depois novamente, até que a divisão sobre apenas x - ou, se não estiver no vetor, retorne -1.

Mas como implementar?
Poderíamos implementar tanto uma função iterativa quanto uma função recursiva. Hoje vamos de iterativa :)
Algoritmo de Busca Binária em C

Explicando o algoritmo:
Nós ficamos em um laço de repetição, que repete enquanto o limite inferior for menor ou igual ao limite superior. Ou seja, se eu tenho um vetor v[0 ... n - 1], ele primeiro tem limInf = 0 e limSup = n - 1. Então dividimos no meio: meio = (limInf + limSup) / 2.
Se x já estiver na posição do meio, retornamos x. Se não, nós fazemos a seguinte pergunta: "x é maior do que o elemento do meio?" Se sim, ele está na metade maior, então pegamos nosso limInf e atribuimos limInf = meio + 1. Se não, ele está na metade menor, e o que fazemos é atribuir o limSup = meio - 1.
Caso na primeira divisão o elemento x esteja na metade menor, nossos limites serão limInf = 0 e limSup = meio - 1.
Então, caso as divisões ocorram e nenhum k satisfaça v[k] == x, o algoritmo retorna -1.

Pronto! Esse é o algoritmo de busca binária - solução iterativa :)

Até a próxima!

21 de setembro de 2010

Fibonacci

Olá!

Hoje, mais um post sobre recursão, abordando a sequência de Fibonacci.
Se você perdeu o meu post sobre recursão, você pode acessá-lo aqui. E também há um sobre a função recursiva que faz a potência de números inteiros, que você pode ver por aqui.

A sequência de Fibonacci é uma sequência matemática definida da seguinte forma:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Como podemos observar, a sequência tem uma característica: Ela começa com 0, 1 e os próximos números são definidos pela soma dos dois anteriores.
Você observa pelas contas:

Dois primeiros: 0, 1
0 + 1 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
...

Tendo isso em mente, podemos definir a seguinte relação matemática:

F(n) =
   | 0, se n = 0
   | 1, se n = 1
   | F(n - 1) + F(n - 2), em outros casos

Utilizando essa definição, facilmente podemos construir uma função recursiva que calcule a sequência de fibonacci, certo?
Pensando em um caso base para nossa recursão, o que temos? Sabemos que quando n = 0 ou n = 1, não precisamos retornar nossa função de novo, e a resposta é o próprio n.

Agora, vamos definir o passo da recursão. Caso n não seja 0 ou 1, qual o valor da resposta? É a soma dos dois anteriores à n, certo? Ou seja:

Pronto! Construimos nosso algoritmo que calcula o número de fibonacci:

E para visualizar a sequência de Fibonacci como demonstrada no começo? Como fazer? Calma, pequeno padawan. Vamos utilizar um laço de repetição para poder calcular os números de fibonacci e imprimi-los na tela.

Agora, pra brincar, é preciso apenas chamar a função fibonacci com o número de elementos da sequência desejado!
fibonacci(5) Irá nos retornar a seguinte sequência:

0, 1, 1, 2, 3

Nessa hora muitas pessoas não compreendem o que exatamente está acontecendo pra que a sequência esteja certa. De onde estão vindo os números?
Tentei ilustrar como ocorrem as chamadas recursivas:

Veja, para cada iteração do laço for, um número fibonacci é calculado, e a função fibo realiza a recursão para este cálculo. Perceba que todas chegam até f(0) ou f(1), e vão retornando seus valores. Como em fibo(2), que precisa da resposta de f(1) + f(0), trazendo a soma 1 + 0, fazendo com que fibo(2) retorne 1.

Esse é um clássico da recursão. Sua solução recursiva é muito elegante, mas como se verifica na imagem, nem tanto eficiente. A solução iterativa é bem menos elegante, mas muito mais eficiente.

Postarei a solução iterativa em breve!
Até a próxima!