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!

18 de setembro de 2010

As matrizes

Já vimos o conceito de vetores, anteriormente. Veremos agora o que chamamos de vetores bi-dimensionais, ou ainda arrays bi-dimensionais.

Matriz, de acordo com a wikipedia: "In mathematics, a matrix (plural matrices, or less commonly matrixes) is a rectangular array of numbers". Ou: "Em matemática, a matriz é um vetor retangular de números".

Amplamente utilizado nas ciências matemáticas, esse conceito ajuda a resolver problemas de álgebra linear, resolução de sistemas lineares, análise numérica, etc. E como a Ciência da Computação é muito matemática, as matrizes também são utilizadas. Uma área bem interessante que se aplica - e muito - é a da computação gráfica. Matrizes de projeção, transformação, etc, são a base de todo trabalho gráfico renderizado pelo computador que estamos acostumados a ver.

Uma matriz A é composta por m linhas e n colunas, e é representada matematicamente da seguinte maneira:
A = ( 123)
456

Nesse caso, A é 2 x 3.

Em computação nós dizemos que uma matriz é um vetor de vetores. Hã?
Calma, pequeno padawan. Imagine um vetor v, com 2 posições. Imaginou? Agora, imagine outros dois vetores, k e r, com 3 posições cada, e preenchidos com números inteiros qualquer.
Se v for um vetor de vetores, atribuimos as duas primeiras posições de v para k e r:

k = { 1
     ,2
     ,3 };

  r = { 4
       ,5
       ,6 };

v[0] = k;
v[1] = r;


Agora, podemos dizer que v é um array bi-dimensional. Porque? Porque podemos acessar, por exemplo, o número 5 da seguinte maneira: v[1][1]. Assim, acessamos o número na segunda linha, na segunda coluna.

Entendeu, pequeno padawan? v é uma matriz, um vetor de vetores.

Vamos ilustrar como se faz o algoritmo de soma de duas matrizes:


O algoritmo faz o seguinte:

  • Inicializamos as variáveis i e j, para poder iterar sobre a matriz

  • Inicializamos a matriz a, que é 2 x 3 e a matriz b, de mesmo tamanho.

  • Criamos a matriz c, para poder guardar o valor da soma de a e b.

  • Vem a parte que realiza a soma. Aqui, iteramos com dois laços de repetição, dois for's. O primeiro for faz o loop pelas linhas, enquanto o segundo faz o loop pelas colunas. Ou seja, para cada linha, o for de j itera em todas as colunas. Assim, colocamos a soma dos valores de a[i][j] com b[i][j] em c[i][j].

Por hoje é isso! Em breve, passarei as operações básicas sobre matrizes.

23 de fevereiro de 2010

Recursão - Potência

Olá!

Você lembra das famosas potências? Daquelas do tipo 2³?
Hoje vamos criar duas formas de realizar esse cálculo.
Queremos criar uma função que receba um número inteiro a (base) e outro n (expoente) e retorne o resultado da multiplicação de a por ele mesmo n vezes (ou, de um modo mais fácil, a elevado à n).

Primeiro, vamos pensar numa versão iterativa, utilizando laços de repetição.
Criamos uma variável para guardar o nosso resultado. Assim, para realizar a multiplicação de a por ele mesmo n vezes, podemos realizar com um laço for: E pronto! temos nossa função potencia:

Como já temos nossa versão iterativa, vamos agora pensar na versão recursiva.
Qual seria o caso base da nossa recursão?
Uma linha de raciocínio seria pensar em um a = 2 e n = 3.
2³ = 2 * (2²)
Certo? Pensando assim, podemos continuar:
2³ = 2 * (2²) = 2 * (2 * (2¹)) = 2 * (2 * (2 * (2^0)))
Logo, o nosso caso base é quando o expoente é zero, ou n == 0, que sabemos que o resultado é 1[1]. E nosso passo da recursão é dado por base * potencia(base, expoente - 1).
Colocando assim, temos:
Potencia(a, n) = a * Potencia(a, n - 1).

Pronto! Temos nossa função recursiva!
Obs.: Perceba que a função funciona adotando n >= 0. Não estamos preocupados em tratar exceções como n = -1, por enquanto =)

Eu acho a função recursiva bem mais elegante =P
Mas é isso ai! Apenas mais um exemplo de recursão!

Até a próxima!

[1] Curiosidade: Pra quem não sabe o porque de um número elevado a zero resultar em 1, o processo é esse: x/x = x¹ : x¹ = x1 - 1 = 1. Explicando: Se você tem 2 objetos e quer dividir para 2 pessoas, sabemos que o resultado é 1. Qualquer número dividido por ele mesmo resulta em 1. Logo, por propriedades de potência, quando há divisão de potências de mesma base pode-se manter a base e subtrair os expoentes, resultando em 2^0. =)

18 de fevereiro de 2010

Recursão

Olá!
Quando você começa a estudar a Ciência da Computação, você aprende (ou pelo menos deveria aprender) muita matemática. Uma técnica matemática aplicada à essa ciência é recursão.
De acordo com o verbete Recursion, da Wikipedia:
"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.[1] The approach can be applied to many types of problems, and is one of the central ideas of computer science."
ou, em Português:
"Recursão na ciência da computação é um método onde a solução de um problema depende de soluções de problemas menores em instâncias do mesmo problema. O método pode ser aplicado em vários tipos de problemas, e é uma das ideias centrais da ciência da computação."

Há também uma frase muito legal para entender a recursão, que diz:
"Para entender a recursão, é preciso primeiro entender a recursão"

Hã? Calma, pequeno padawan. =)
Imagine o seguinte problema: Você está no seu colegial, e o seu professor de matemática que você adora tanto que até deixou você de recuperação pra não sentir saudades, pede uma lista enorme, só com fatoriais. Você, um aluno calmo e consciente, respira fundo e pensa, dentre seus pensamentos matemáticos: "Qual será a relação matemática entre todos esses fatoriais?"
Então, você tem uma luz, daquelas que iluminam quarteirão em dia de apagão, e escreve:

fatorial(n) =
| 1 ,se n = 0
| n * fatorial(n - 1) ,se n > 0

Claro! Se o número que ele pedir for zero, então eu sei que o resultado é 1, por definição. Mas se for maior do que zero, o resultado nada mais é do que ele vezes o fatorial do número anterior à ele! E então você faz no seu rascunho algumas provas reais:

fatorial(1) = 1 * fatorial(0) = 1 * 1 = 1
fatorial(2) = 2 * fatorial(1) = 2 * 1 = 2
fatorial(3) = 3 * fatorial(2) = 3* ( 2*fatorial(1)) = 3* ( 2* ( 1* fatorial(0))) = 3*2*1*1 = 6

Você acaba de entender a recursão!

Passar esse conceito para um algoritmo em C, é fácil. Ficaria dessa forma:
Perceba a estrutura recursiva da função.
Temos o caso base, que encerra a recursão em algum momento, para não entrar em algo infinito:
E então, o passo da recursão, que reduz o problema a uma instância menor, chamando a mesma função
Na grande maioria dos casos (pra não dizer todos), uma solução recursiva pode ser escrita de forma iterativa. Veja o exemplo que eu dei quando falei sobre laços de repetição: A função fatorial, em sua versão iterativa.

Uma função recursiva é, sem dúvida, muito elegante. Hoje, muitas pessoas que estão na área da computação não conseguem utilizar recursão, outras não a entendem, e outras sequer sabem da sua existência. Então, é algo que merece um pouco de estudo e atenção.
E lembre-se: Para fazer um procedimento recursivo, é preciso ter fé! =)

Vou postar mais alguns problemas com resoluções recursivas e, para comparação e estudo, suas soluções iterativas.

Até lá!

10 de fevereiro de 2010

Vetores

Um vetor (ou array) é uma estrutura de dados que é capaz de armazenar objetos do mesmo tipo em uma sequência, ocupando posições consecutivas na memória.
Falarei hoje sobre a busca em vetores.

Um vetor v de tamanho n posições é dado pela notação v[n] .

Esse vetor possui objetos armazenados em suas posições v[0 ... n-1] , ou seja, se o vetor v possui 5 posições, o último objeto estará armazenado em v[4] .

A declaração de um vetor de inteiros possuindo 5 posições é dada por: int v[5];

A busca

Vamos pensar que nos foi dado um vetor v de números inteiros ( int ) de tamanho n, e nos pedem para encontrar certo número x.

Então, temos o vetor representado da seguinte maneira:

indices 0 n-1
valores 14 26 12 18 12

Então, temos que encontrar um índice k tal que v[k] == x .

Você deve estar pensando: "E se x não estiver no vetor? Ou quem sabe n = 0? O que fazer?".
Calma, pequeno padawan. Se isso ocorrer, podemos simplesmente devolver -1 para quem estiver perguntando. =)

Pensando assim, temos que conseguir uma forma de entrar nesse vetor e achar o que estão nos pedindo. Como fazer?
É isso ai! Esse algoritmo efetua a busca, e retorna o índice que representa a posição do valor pedido no vetor dado. =)

14 de janeiro de 2010

Laços de Repetição

Olá!

Hoje vou falar sobre os famosos laços de repetição. Estruturas bem simples e poderosas do mundo da computação.
Os laços de repetição se encarregam de repetir determinada instrução enquanto uma determinada condição for verdadeira.
A partir de agora vamos chamar esses laços de loops. Assim sendo, temos basicamente dois tipos de loops: O for e o while.

No portugol, o while seria algo mais ou menos assim:

inteiro i := 1
ENQUANTO i < 10 FAÇA
  imprima(i)
  i = i + 1

E o for, assim:

PARA i = 0 de 1 a 10 FAÇA
  imprima(i)


Ou seja, nos dois casos ele vai ter que repetir a instrução imprima(i) até que a variável i seja igual a 10.

Na linguagem de programação C, isso ficaria assim:

O laço while tem uma variação, que se chama Do..While. No primeiro caso, quando fazemos o while normal, primeiro é verificado se i é menor do que 10 e então a instrução é executada. Já, quando utilizamos dessa forma:
Primeiro é executada a instrução, e depois a condição é testada.

Cuidado!
É muito fácil de cair sem perceber no famoso loop infinito.
Dê uma olhada no banner do blog. Vê aquele "while( 1 > 0 ) printf("Bem vindo!");" ?
Isso é um loop infinito. Quando não se queria um desses, pode causar muita dor de cabeça. Agora, quando você precisar de um desses, dentro do escopo do loop tem que haver alguma instrução que execute o break (instrução que força o término do loop), que quebra o loop infinito.


Para terminar, que tal escrever uma função que, dado um número inteiro n, retorne o seu fatorial?

Em C:


É isso! Até a próxima!

Voltando com tudo

Bom, sem mais delongas, só queria me pronunciar sobre o ano de 2010.
Tomara que eu consiga manter isso aqui atualizado sempre! =]

Abraços!