Felipe Tonello

Analisando Número de Fibonacci e Recursividade

2009-01-30T15:38:37Z

O número de Fibonacci é bem conhecido no mundo da computação. Ele é representado por uma função recursiva:

Calculando

Tendo isso em mente é bem fácil criar um algoritmo que calcule o número de Fibonacci, certo?
Na internet normalmente encontramos um algoritmo usando um método de recursão simples. Algo parecido com:

Felipe: Esse artigo usa apenas exemplos em C++

fibo1.cpp

#include <iostream>
#include <cstdlib>
 
int F(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return F(n - 1) + F(n - 2);
}
 
int main(int argc, char *argv[])
{
    int n = atoi(argv[1]);
    std::cout << F(n) << std::endl;
    return 0;
}

código no pastebin

Compilando:

g++ -o fibo1 fibo1.cpp

Rodando:

./fibo1 8

Deu 21, certo? Isso mesmo.

Analisando a Função

Mas digo para você: Não use esse programa! É totalmente ineficiente. O número de chamadas para calcular é exatamente . A função calcula recursivamente o mesmo número quantas vezes a chamar. Como podemos ver, a taxa de crescimento do número de Fibonacci tende a Proporção áurea:

Lembrando que a razão áurea é definida por:

Sim, fibo1.cpp é uma função exponencial com Big Theta Notation, em função do tempo, de:

O tempo de execução para computar é vezes mais demorado que para calcular . Por exemplo, já que e percebemos que nosso computador leva um segundo para calcular , então levará mais de um minuto para calcular e mais de uma hora para calcular .

Podemos verificar isso calculando e

pet@felipe-opensuse:~/Projetos/C++/algoritmos> time ./fibo1 36
14930352

real 0m1.077s
user 0m1.040s
sys 0m0.008s
pet@felipe-opensuse:~/Projetos/C++/algoritmos> time ./fibo1 45
1134903170

real 0m54.927s
user 0m54.547s
sys 0m0.092s

Em contraste, usando o método de programação dinâmica temos um tempo proporcional a N.

Programação dinâmica

Esse método consiste em guardar os valores dos números já calculados em um array. Fazendo isso, apenas checamos se o array já foi memorizado, e então retornamos o número, caso contrário calculamos recursivamente e assim por diante.
Lembrando que para um int de 32 bits, será o maior numero a ser calculado.

fibo2.cpp

#include <iostream>
#include <cstdlib>
 
namespace Fibonacci {
    int *memory;
    int F(int n)
    {
        // int inicializa como 0
        if (memory[n] != 0) return memory[n];
        int aux = n;
        if (n < 0) return 0;
        if (n > 1) aux = F(n-1) + F(n-2);
        return memory[n] = aux;
    }
}
 
int main(int argc, char *argv[])
{
    int n = atoi(argv[1]);
    Fibonacci::memory = new int[n+1];
    std::cout << Fibonacci::F(n) << std::endl;
    delete [] Fibonacci::memory;
    return 0;
}

código no pastebin

Compilando:

g++ -o fibo2 fibo2.cpp

Rodando:

./fibo2 8

Deu 21, de novo? =)

Aplicamos aqui uma técnica chamada bottom-up dynamic programming. Se aplica em uma função recursiva que podemos salvar tempo por armazenar valores anteriores que serão usados depois. Essa técnica tem sido usada para uma gama grande de algoritmos e aplicações. E essa simples mudança fez com que nosso algoritmo passasse de exponencial para linear.

Agora temos uma função, em relação ao tempo, proporcional ao N.

Comparando

Fazendo vários testes, podemos chegar em uma tabela de resultados, em função do tempo:

arquivo
fibo1.cpp	0m0.009s	0m1.156s	0m54.927s	1m29.403s
fibo2.cpp	0m0.007s	0m0.007s	0m0.006s	0m0.007s

fibo2.cpp é constante? Sim! Para N relativamente pequeno fibo2.cpp calcula em tempo constante.

Será interessante ver até quanto esse algoritmo agüenta(ta errado né? hehe ¬¬) fazer em tempo constante. Alguém se habilita?

ack, um grep melhorado

2009-01-25T18:10:00Z

Se você é fan do grep(especialmente com o -drecurse), mas sempre vendo o .svn ou outro diretório irritante, você precisa do ack.

Descobri esse programinha num blog do KDE e gostei muito!

Algumas coisas legais:

output bonitinho(colorido)
highlight
boa organização
fácil configuração
e até mesmo documentação

Digitar menos, o que você quer mais?

Exemplo:

Josephus Problem, resolvendo-o de maneira simples

2009-01-09T18:31:05Z

Josephus Problem é um problema bem legal que estudei no livro Concrete Mathematics.

Josephus foi um historiador judeu do primeiro século. A lenda conta que ele e 40 de seus homens estavam presos em uma caverna pelos Romanos. Eles decidiram suicidar-se à ser capturados. Formaram um circulo e começaram a se matar, da 3ª à 3ªa pessoa em ordem da fila. Como Josephus não queria morrer, ele foi capaz de escolher o melhor lugar, afim de sobreviver, e juntar-se os Romanos que o capturaram.

O Problema

Na prática o problema teria N pessoas em um círculo, iria ser percorrido M - 1 pessoas e o M iria ser morto, assim por diante, até sobrar uma única pessoa.

A Solução

Podemos representar a solução por uma função recursiva, para N par e M = 2:

e para N ímpar e M = 2, temos:

Não vou postar a solução genérica aqui pois exige uma grande explicação e esse não é o objetivo do post. Você pode ver na wikipedia ou então comprar o livro, caso queria saber mais.

O interessante é que o algoritmo para solução genérica é bem simples em C++. Usando listas ligadas(linked lists) é simples, fácil de entender e super rápido a execução do programa.

Josephus.cpp

#include <iostream>
#include <cstdlib>
 
struct Pessoa {
	int num;
	Pessoa *prox;
	Pessoa(int x, Pessoa *p) {
		num = x;
		prox = p;
	}
};
 
int main(int argc, char *argv[]) {
	//'a' recebe primeira pessoa criada
	//e 'a' é linkado para si mesmo
	//depois 'b' é criado apontado para 'a'
	int N = atoi(argv[1]), M = atoi(argv[2]);
	Pessoa *a = new Pessoa(1, 0);
	a->prox = a;
	Pessoa *b = a;
 
	// Aloca na memória todas as pessoas
	// e 'b' recebe a última(enésima pessoa)
	// pois a contagem começa pela primeira('a')
	for (int i = 2; i <= N; ++i)
		b = (b->prox = new Pessoa(i, a));
 
	// Loop enquanto 'b' não estiver apontado
	// o próximo para ele mesmo
	while (b != b->prox) {
		// 'b' recebe a emésima pessoa
		for (int i = 1; i < M; ++i)
			b = b->prox;
		a = b->prox;
		b->prox = a->prox;
		delete a; // 'a' é morto =/
	}
 
	// O sobrevivente _o/
	std::cout << b->num << std::endl;
}

Ou então se preferir um link para o pastebin.

Analisando o Resultado

após compilar

g++ -o Josephus Josephus.cpp

rode o programa com N = 10 e M = 2

./Josephus 10 2

O valor deu 5? Verifique com a função. Bateu os valores?
Agora vá testando para 1 <= N <= 16 e M = 2.

for n in `seq 16`; do echo -n “$n: “; ./Josephus $n 2; done

Saída do loop:

1: 1
2: 1
3: 3
4: 1
5: 3
6: 5
7: 7
8: 1
9: 3
10: 5
11: 7
12: 9
13: 11
14: 13
15: 15
16: 1

Perceberam um certo padrão entre as respostas? A função genérica usa justamente esse padrão binário para solução.

Ultimamente eu estou mais dedicado ao estudo de algoritmos, C++, C e Python(é claro). Depois pretendo postar uma analise desse algoritmo passo a passo.

Voltando com TUDO!

2008-12-09T15:26:17Z

Eu fiquei um bom tempo sem postar nada aqui, sem escrever nenhum tutorial ou artigo. Não posso mentir e dizer que só estava ocupado, mas realmente fiquei com um poco de preguiça. Agora nas férias o projeto RobotQt voltará com tudo! Até criei uma página no Ohloh para o projeto para quem quiser acompanhar mais de perto o projeto. Também organizei todas minhas to-do’s list. Como:

Atualizar plugin wp-catshow
Criar plugin wp-fileupload(novidade )
Atualizar mais o blog com artigos e tutoriais hehe
Contribuir para o KDE4
Continuar ferozmente meus estudos de algoritmos

Agora bola pra frente e vamos lá!

PyConBrasil 2008 lá vou eu!

2008-08-13T00:48:26Z

Galera, é com muita alegria que estou postando novamente aqui.

Primeiramente gostaria de dizer que mudei de trabalho. Estou trabalhando remotamente, em casa, para uma empresa canadense de Open Source e Linux chamada Savoir-faire Linux! Uma maravilha hehehehe

Segundo, é que voltei a trabalhar com coisas que gosto, como Python, C++ e KDE4.

Portanto estarei indo para a PyConBrasil 2008, que vai ser no Rio de Janeiro.

Nós da GruPy-SP estamos tentando fazer algum arranjo para ir de onibus fretado e ficar num hotel por lá, vai ser super legal!

E você, vai?

Ajude a sustentar a Wikipédia e outros projetos, sem colocar a mão no bolso, e concorra a um Eee PC!

2008-07-25T18:29:47Z

Ajude a sustentar a Wikipédia e outros projetos, sem colocar a mão no bolso, e concorra a um Eee PC!
…e também a pen drives, card drives, camisetas geeks, livros e mais! O BR-Linux e o Efetividade lançaram uma campanha para ajudar a Wikimedia Foundation e outros mantenedores de projetos que usamos no dia-a-dia on-line. Se você puder doar diretamente, ou contribuir de outra forma, são sempre melhores opções. Mas se não puder, veja as regras da promoção e participe - quanto mais divulgação, maior será a doação do BR-Linux e do Efetividade, e você ainda concorre a diversos brindes!

Brinder Br-Linux e Efetividade.net

Nóis é muito burro!

2008-07-17T19:17:09Z

Esse é meio que um desabafo e engraçado ao mesmo tempo

A história começa quando vim para o Canadá para trabalhar com Java e no fim das contas comecei a trabalhar com ASP.NET. Eu não tenho nada contra ASP.NET, pelo contrário, é uma ótima tecnologia.
Mas o problema é que aqui na empresa onde trabalho, eles não utilizam meu potencial(não que eu tenha muito). Aqui eu fico arrumando layout e controller ASP.NET, tabulando, fazendo relatórios e assim por diante. PELO AMOR NÉ?
E eu percebi que estava enferrujando em programação, prática e inclusive meu conhecimento.

Mas tudo bem. 5 Meses passaram…

Quando eu e o Luiz Vitor estavamos resolvendo o exercício do Alien Numbers (Google Code Jam 2007). E depois de 5 horas conseguimos hehe aquela alegria!!!

from __future__ import alien_number

Aí começamos a fazer do Maze(Labirinto). Tentamos, tentamos, tentamos e aí não deu mais tempo porque comecou o Google Code Jam 2008.

Os 2 primeiros exercícios da primeira fase eram fáceis. Um era sobre serach engine e outro era de esquema de trens. Não era necessários algoritmos complexos para resolver, apenas lógica.
Aí tudo bem, comecei a fazer o primeiro. Depois de uns 15 minutos entendi o que era para fazer e fui jantar. Jantando fui pensando o que iria fazer para resolver o problema. E tinha chegado numa conclusão simples.
Cheguei no meu computador e fui começar meu código. Em 30 min +- mandei minha versão e bééééééé: ERRADO. Aí fui repensar e vi o que estava errado e mandei de novo: bééééééé.
Aí comecei a ficar encucado. E em quanto isso o Bruno Gola e Lameiro já tinham resolvido. E eu e o Luiz nos elogiando: “Cara, nós somos muito burros!!!! hahahah” “Eu sou uma porta, pelo amor!!!”

Hoje comecei o exercício dos treins. Mais fácil do que o primeiro. Entendi a lógica, comecei a codar. E NADA hehehe Fiz um monte de coisa, vários davam certo mas uns davam errado e percebi de novo que era erro de código. Aí agora desisti já, nóis é muito burro e ano que vêm estamos aí. Só agora vou estudar muito! Comprei uns livros feras d+ de algoritmos, que por sinal recomendo a todos que querem ser bons programadores!

Mas falando a verdade, o Bruno Gola e o Lameiro e inclusive o Luiz são muito bons, muito melhor que eu. Mas eu fiquei injuriado pelo fato de eu não ter conseguido CODAR esses problemas, que estavam resolvidos na minha cabeça.

E agora a moral da história, voltando ao começo do post.

Nunca, mas NUNCA, vá trabalhar em um lugar(ou o que seja) onde não te estimulem e exija seu potencial! NUNCA

Poison

Sinceramente, se eu não tivesse para mudar de empresa agora no final do mês, eu largava tudo aqui, tudo mesmo. E voltava para o Brasil.
Prefiro ser pobre, morar num lugar onde a política é sinônimo de palhaçada, ao que desaprender tudo e ser um inútil.

“Eu vou virar freelancer” - Já pensaram isso?

2008-06-24T15:52:27Z

Conversando com o Jader fui inspirado a escrever esse post.

Muitos, assim como eu, tiveram essa grande idéia de virar freelancer. Ser seu próprio chefe, escolher seus trabalhos, trabalhar com o que gosta, são idéias atrativas né?
Mas tudo o que é bom pode ficar ruim, ou péssimo!
Por que estou falando isso? Não é para assustar não, mas para você refletir sobre sua situação.

Perguntas para reflexão:
- Você já possui um trabalho? Você não gosta dele? Você têm benefícios(refeição, seguro, saúde …)?
Lembrete: como freelancer você não terá mais nada disso

- O que te faz pensar que como freelancer será melhor?
- Contato é a coisa mais importante para um freelancer, você têm bons contatos?
- Você é responsável? Cumpre horário? É disciplinado?
Lembrete: Você terá que acordar cedo, se policiar em msn/plurk/twitter

- Têm responsabilidades para com família? O que eles esperam de você?

- Está disposto a correr os riscos?
Se você responder que sim. Espero que seja o melhor!
É um desafio e não é dos fáceis. Mas pode trazer ótimos frutos e realizações.

Freelancer é uma boa, eu fui por 6 meses. Aprendi bastante, ralei bastante. Fiz palestras, projetos opensource, ajudei em projetos e etc. Foi muito proveitoso para mim. Mas no meu caso o que me atrapalhou foi a questão da disciplina.

Então, antes de tomar uma decisão pense! pense muito! E sejamos todos felizes!

E você? É freelancer? Relate sua experiência e dicas!

Você gosta do seu emprego? Em busca do emprego perfeito?

2008-05-29T17:24:53Z

É impressionante como todo mundo que se forma em uma faculdade sai com aquela esperança de revolucionar o mundo, criar uma empresa como o Google ou até mesmo ir para lá como desenvolvedor super power em Python.

É, dizem que nada é impossível mesmo. Mas até quando temos que ficar sonhando?

Bom, apesar de ter menos de 2 anos de experiência eu já trabalhei em 4 empresas, desde pequenas até gigantes. Sempre tentando achar um emprego perfeito.

Como você define algo bom? Salário? Benefícios? Projetos? Tecnologia usada? Aprendizado?

Para nós que somos geeks(linuxeros) isso é mais difícil ainda! Gostamos de Python, PHP, Linux, Vim etc etc. Mas muitas vezes temos que engulir seco por trabalhar com ASP.NET (meu caso).
É, estou me cansando de novo. Não gosto da environment de trabalho, do projeto e principalmente da tecnologia usada. Meu direito, certo?

Mas até onde compensa ficar pulando de trabalho em trabalho, tentando achar algo que você se adapte? Ou então trabalhar por conta?
Muitas vezes você não pode fazer isso. Por falta de oportunidade ou “simplesmente” responsabilidades a cumprir.

Bom, eu já estava deixando essa coisa de ter emprego perfeito de lado. Até que me apareceu uma oportunidade para trabalhar com Linux, Python, PHP, C++/Qt GTK. Tudo opensource. Parece até um sonho. Aceitei na hora!

Mas e você? Acha que um dia vai para ser um Guido van Rossum do Google? O que faz para que isso um dia possa ser realizado? Vale a pena lutar por isso? Ou, talvez, não esquenta cabeça mais com isso?

Aqui eu dei um exemplo pessoal, mas não necessariamente você gosta de Linux.

Conte sua história

Mudei de VIM

2008-05-22T18:25:48Z

Infelizmente o VIM é porcamente suportado no Mac OS X(meu atual SO).

Mas felizmente o Mac OS sempre tem suas saídas, e a melhor de todas é o TextMate.

O TextMate simplesmente é sensacional!! Ele foi feito exatamente para substituir os fãs de Emacs ou VIM, ao estilo Mac OS de ser. É eu já virei fã do Mac, mas de leve.

Pena que não é freeware e muito menos open-source, o que significa que é pago. Massss, é um dindin bem investido.
Como o Aurélio mesmo disse: “O Textmate é bom pra baralho”