April « 2005 « Legacy tiagomadeira.net

Archive for April, 2005

Desafios Lógicos e Sites

Thursday, April 14th, 2005

No Orkut, adicionei alguns caras que manjam de algoritmos, lógica, informática, Linux, ER, etc., como por exemplo Aurélio Marinho Jargas, Piter Punk (Roberto Freires Batista), Fábio Dias Moreira e Helder Suzuki. E com isso, pra minha felicidade total, recebi dois desafios lógicos! (destes últimos dois) :D

Permutação

O primeiro é sobre permutação. O Helder leu meu post sobre permutações e sugeriu a criação de um programa que, sem fazer as operações anteriores, determinasse o n-ésimo elemento de uma permutação. Ainda não fiz porque tô atolado de coisas pra fazer, mas pensei que posso descobrir cada letra a partir do seguinte…

Vou supôr que tenho uma cadeia ABC, tamanho=3, letras=3

As permutações seriam feitas na seguinte ordem:

a a a
a a b
a a c
a b a
a b b
a b c
a c a
a c b
a c c
b a a
b a b
b a c
b b a
b b b
b b c
b c a
b c b
b c c
c a a
c a b
c a c
c b a
c b b
c b c
c c a
c c b
c c c

A primeira letra se alterna a cada 9 (3^2) vezes. A segunda a cada 3 (3^1). A terceira 1 (3^0). Portanto, eu acho que consigo descobrir cada uma das letras! Vamos supor que quero o décimo primeiro elemento.

11o. elemento

Está entre 10 e 18 – portanto a primeira letra é B

Está entre 10 e 12 – portanto a segunda letra é A

É 11 – A B C, A B C, A B C, A B!

BAB!

Sabendo disso fica fácil… Demorei pra pensar nisso, mas agora vou escrever o algoritmo, implementar e vencer o desafio! :)

Bom, e além do desafio, o Helder me falou uma coisa que eu achei muito legal! O vestibular do ITA só tem português, inglês, matemática, física e química. Ou seja, as matérias que mais precisaria estudar (biologia principalmente e história e geografia) não existem! emoticon Ultimamente, estive pensando em que universidade vou entrar. Estou na dúvida entre ITA e Unicamp, mas acho que prestarei vestibular para as duas.

MMC/MDC

O segundo desafio foi do Fábio Dias Moreira. Na verdade, não foi bem um desafio, foi uma idéia sobre o post do MMC.

E-mail dele

Eu li o seu post sobre cálculo de MMCs, e acho que você deveria tentar explorar as identidades a seguir:

mmc(x, y) * mdc(x, y) = x * y
mmc(mmc(x, y), z) = mmc(x, y, z)

Como calcular mdc é uma tarefa simples (já que mdc(x, y) = mdc(x, y % x)), que leva tempo O(log x), a conta mdc(x_1, x_2, …, x_n) deve levar tempo O(n log x).

Ainda não implementei tudo completamente, mas fiz alguns testes, que publiquei na seção de scripts.

mdc.c – Calcula o Máximo Divisor Comum de vários termos
mdc-2.c – Calcula o Máximo Divisor Comum entre 2 termos
mmc-2.c – Calcula o Mínimo Múltiplo Comum entre 2 termos

Tô chegando lá… Só falta fazer uma função que calcule o MMC dividindo em várias partes e fazendo vários MDCs. :p

Frações Egípcias

Bom, pra fazer eu pensar mais ainda, uma garota de 19 anos chamada Tatiane, que também leu o script do MMC, me enviou alguns e-mails sobre um algoritmo pra transformar frações próprias em frações egípcias. Só que o problema é que não pode usar funções, vetores, quase nada! Só pode usar os tipos char e int, e tem bastante regras que não deixam a pessoa sonhar muito. No fim, não consegui fazer, mas ela fez e parece que funcionou tudo certo. Em outro post, falarei mais sobre isso (depois que entender o algoritmo dela).

Meetweb

Hmmm… Uma empresa de construção de sites chamada MeetWeb me contratou pra programar para um site com um design já construído no Dreamwaver. Estou programando (PHP + Banco de dados MySql) e pretendo acabar em menos de 20 dias. Achei uma boa oferta, mesmo com uma pequena falta de tempo e o site exigir bastante coisinha de JavaScript (que eu não gosto muito – mas tô aproveitando pra aprender mais) e muita coisa repetida (o site é 100% administrável). É sempre bom pegar sites pra fazer, sempre acabo aprendendo mais alguma coisinha e um dinheirinho a mais sempre é bom também!

Site novo do Colégio

Esta semana comecei a fazer um site novo para o Colégio (o Salesiano, onde que eu estudo e trabalho), totalmente administrável também, com código válido e tableless, Flash… Uma coisa bem linda, leve e simples de administrar.

SOSPHP

Pra finalizar, o “meu” fórum, a SOSPHP tá com um movimento um pouco baixo e por isso tô fazendo um movimento para reanimá-lo. Então participem também! Entrem em www.sosphp.com.br e ajudem o fórum a crescer! Estou mandando mensagens para moderadores que estão sem visitar ultimamente, chamando mais gente e pedindo opiniões dos membros para melhorar o fórum (e é claro, pondo as opiniões em prática).

Posted in Lógica | 1 Comment »

Biologia, Torres de Hanói, Long Double, Mandriva e Expressões Regulares

Thursday, April 7th, 2005

Hoje fiz uma prova de biologia. Minha média em biologia estava em 7,93 (8 em um trabalho, 5,8 em uma prova, 10 em participação) e acho que com essa prova vai continuar na mesma, se não piorar. Acredito que eu vá tirar no mínimo 8,5 nessa prova e no máximo 9,5. Pelo menos foi melhor que na outra em que eu tirei 5,8. Bom, só pra não parecer que eu sou burro, minhas notas nas outras matérias nas provas que eu recebi essa semana foram:

10 em inglês
10 em português (e mais 10 numa redação)
10 em matemática
10 em geografia
10 em história
9,5 em química (e mais 10 num trabalho)
9,5 em física

Hmmm… Acho que dá pra perceber que meu problema é biologia mesmo…

Sinceramente, eu odeio essa matéria. Nas outras disciplinas a gente aprende e desenvolve raciocínio lógico. Biologia é só uma decoreba. Não compreendo qual é a utilidade de saber a função das bactérias para nossa vida ou, como um enunciado da prova dizia, “Se você capturasse exemplares de piranhas no Pantanal Mato-grossense, o que você faria pra descobrir de que cadeia alimentar elas fazem parte com base somente nesses exemplares?” Qual a utilidade disso aí? Se eu quisesse ser biólogo até beleza, mas isso aí é inútil. Em matemática, aprendemos coisas úteis. Em biologia, só aprendemos coisas assim… Se ainda fosse como ano passado onde estudávamos atualidades biológicas como células-tronco, AIDS, DSTs, Gripe do Frango, etc., tava ótimo mas esse ano tá um “saco”.

Acho que essa gente que gosta de biologia só pensa no vestibular ao dizer que ela é útil… O básico dela até pode ser útil, mas metade do que a gente aprende na escola de biologia não é útil.

Bom, parando de falar sobre isso… Vamos para as Torres de Hanói

Ontem eu deixei o laptop a noite inteira fazendo as Torres de Hanói com 30 pinos. Utilizando o algoritmo que está implementado em torresdehanoi.c o programa ficou 728 minutos (12 horas) testando e não conseguiu chegar a um fim. Com outros testes, consegui os seguintes tempos:

10 pinos – 0 s
15 pinos – 1 s
20 pinos – 20 s
25 pinos – 20 min
30 pinos – mais de 12 horas

É assombroso a maneira com que vai aumentando…

Bom, utilizando o tipo long double do C eu fiz a conta de 2^64 para ver o custo da “Lenda de Brama” (é esse o nome?)

2^64=18.446.744.073.709.551.616

Ou seja, 18 quinquilhões e meio… Isso é muita coisa.

O interessante é que eu nunca tinha usado o long double com números tão grandes e então fiz alguns testes. Eu cheguei ao resultado de 2^1000, 2^10000 e cheguei a conclusão de que o último número que ele consegue escrever sem dizer que é inf (infinito?) é 2^16383, ou seja, 2^(2^14-1). Saiu umas 40 linhas no console, é muito grande!

Hmmm, demonstrei mais alguns teoremas como a Relação Fundamental da Trigonometria (usando o teorema de Pitágoras – basta dividir os dois lados por a^2), fórmula de Bhaskara, o volume de um cubo inscrito numa esfera pode ser calculado através do raio da esfera, etc. (não lembro de todos). Na verdade, não fui eu que demonstrei. Demonstramos no treino da Olimpíada de Matemática. Eu, o Vavá e o Bruno.

A Mandrakesoft comprou a Conectiva, formando o Mandriva. Eu achei uma pena que uma distribuição importante do Brasil (a primeira) acabou assim. Ela foi muito importante no software livre do Brasil, da América Latina e do mundo. Porém, acredito que a distro Mandriva vai crescer e se popularizar. Quando sair alguma, eu queimo um CD pra testar.

Peguei a música Estrada do Sol (Tom Jobim) no piano (uma versão muito boa escrita por Paulo Jobim e disponível no site www.tomjobim.com.br) e estou pegando Falando de Amor. Assim que der tempo, eu queria gravar algumas músicas que eu toco pra colocar aqui…

Acabei de ler o livro do Aurélio sobre expressões regulares e aprendi bastante coisa interessante. Expressões Regulares são MUITO úteis!

Posted in Diversos | No Comments »

Algoritmo de Permutação e Expressões Regulares

Monday, April 4th, 2005

permutar (dicionário Priberam)

permutar | v. tr. | v. tr. e int.

Conjugar
do Lat. permutare

v. tr.,
dar reciprocamente;

trocar uma coisa por outra;
cambiar;

v. tr. e int.,
trocar reciprocamente os lugares.

Em matemática, estuda-se a análise combinatória apenas no segundo ano do Ensino Médio (sinceramente, acho isso tão errado quanto não ensinarem a fórmula de Heron ao invés de b.h/2), mas por ser muito útil nas olimpíadas de matemática, acabei aprendendo antes. A permutação que o meu programa faz é com elementos repetidos. Dando a ele um limite de números (naturais) e o número de algarismos de cada saída, ele imprime todas as possibilidades na tela.

Permutação

#include


#define NMAX 101 //Esta é uma constante que define o tamanho do vetor

#define NIVELMAX 5 //Esta constante define o número de níveis (número de caracteres numa permutação)

#define NUMEROS 2 //Esta constante define o número de números pelo qual a permutação passa.
int n[NMAX]; //Define o vetor "n" que contém os números pelo qual a permutação vai passando.
void permuta(int nivel) { //Inicia função que faz a permutação

        int i; //Define a variável i (contadora)
        if (nivel< =NIVELMAX) { //Se o nível for menor ou igual o nível

                for (i=1; i<=NUMEROS; i++) { //Laço para chamar uma função para cada valor diferente desse.

                        n[nivel]=i; //Define o número atual para i (o valor do laço)

                        permuta(nivel+1); //Chama a função (continua a recursão)

                } //Fim-para

        } else { //Senão

                //Imprime todas os números

                for (i=1; i<=NIVELMAX; i++) { //Laço para pegar os números de todas as funções

                        printf("%d", n[i]);

                } //Fim-para

                printf("\n"); //Pula uma linha

        } //Fim-se

} //Fim da função
int main(void) { //Começa a função "main"

        int i; //Define a variável i (contadora)
        //Primeiro, zeramos o vetor "n" que contém os números que vão ser escritos.

        for (i=1; i<=NIVELMAX; i++) { //Laço

                n[i]=1;

        } //Fim-para

//Chama a função com nível 1. permuta(1); } //Fim-função

Esse código tá tão comentado que tá até difícil de entender...

O que você dá para o programa são as três constantes nas linhas 3, 4 e 5.

Gostei de fazer esse programa. Eu tive que pensar um pouco até na hora de escolher trabalhar com vetores, pois fazer permutações parece uma coisa mais simples mas é difícil. Fiz vários rascunhos de algoritmos no papel, mas aí só tá implementado em C. (eu nunca digito meus algoritmos... :blink: )

Comecei a estudar mais expressões regulares (para desenvolver um novo sistema de bbcodes e sintaxe colorida) e estou achando super legal. É um pouco complicado, mas tem muita lógica e tem muitas coisas úteis que dá pra fazer com elas, principalmente na construção de sites interativos em PHP. Estou lendo o livro do Aurélio que está disponível em guia-er.sourceforge.net. É muito bom! :)

Esse cara é um pouco maluco, mas o que ele faz com expressões regulares é muito legal! Desde setembro/2004, eu utilizo um programa em Bash dele chamado Funções ZZ. As funções ZZ são vários aplicativos simples que utilizam expressões regulares para facilitar tarefas do dia-a-dia. Por exemplo, o conceito de permutação que eu utilizei acima foi de um dicionário on-line das funções ZZ.

Consultando as estatísticas hoje, fiquei feliz ao ver meu blog citado em projetando.blogspot.com. Nunca sei se meus textos estão sendo compreendidos e por isso acho legal quando vejo que alguém linkou para meu site.

Posted in Lógica | No Comments »

Demonstrações matemáticas, IE 7, Bash, GeSHi

Friday, April 1st, 2005

Ultimamente não tenho me dedicado muito a resolução de problemas lógicos utilizando algoritmos e não tenho programado em C, mas andei estudando um pouco LaTeX e demonstrando teoremas matemáticos. Quarta-feira, o professor Vavá sugeriu ao nosso grupo de estudo da Olimpíada de Matemática provar 10 teoremas da matemática (entre eles, a fórmula de Bhaskara, o Teorema de Pitágoras, Relação Fundamental da Trigonometria, etc.) e estou tentando demonstrá-los com até q.e.d. no fim… :D

Bom, já que estava estudando LaTeX e o objetivo era provar de forma clara os teoremas, acabei transformando alguns em PDF.

O Ivo me falou sobre a fórmula de Bhaskara e eu consegui provar que o produto de dois números pares é necessariamente um número par (essa é totalmente ridícula). Tem duas propriedades logaritmicas que há algum tempo eu sabia demonstrar, mas agora não lembro. E algumas outras coisas que ainda não faço idéia de como provar… :blink:

Quarta-feira, antes do encontro de matemática, minha banda (Zibian) ensaiou (foi um ensaio totalmente precário, mas fazia tempo que a gente não ensaiava).

Sexta-feira (ontem), fui num dos melhores shows da minha vida. Yamandu Costa, Paulo Moura, Armandinho (pelo amor de Deus, não é o cara do reggae) e Robertinho Silva tocaram no CIC em Florianópolis interpretando obras de Tom Jobim em homenagem aos 10 anos desde a morte desse grande compositor. Foi muito bom. Os caras tocando música instrumental de primeira com as lindas músicas do Tom.

Ontem também li sobre um artigo na página do Bruno Torres falando sobre os developers do IE 7 implementando no novo navegador (se é que aquilo é digno de ser chamado de navegador) uma engine da Gecko (do Mozilla) modificada. “Um engenheiro da microsoft, do time que está trabalhando no desenvolvimento da nova versão de seu pseudo-browser do ícone azul, afirmou extra-oficialmente que ele e seus pares estão trabalhando em uma adaptação de um engine open-source de renderização HTML e CSS, o gecko (lagartixa em português, por isso comendo mosca), usado pelos navegadores mozilla e firefox, além do Netscape.” (trecho do artigo). É uma pena que depois tenha descoberto que se tratava apenas de uma brincadeira de primeiro de abril e o nome do engenheiro era “Adrem Resworb” que ao contrário fica “Browser Merda”.

Tenho criado alguns scripts em Bash para resolver grandes problemas (é incrível a utilidade desses pequenos scripts!) e estou refazendo o QueimaCD, agora em dialog para o Sinapx (a distro que eu e um grupo de pessoas estamos desenvolvendo no SOSPHP).

Andei testando o GeSHi (é um syntax highlighter – um programinha pra deixar os códigos coloridos na página) e estou pensando em colocar aqui na página (mesmo antes de trocar de site, porque aquele novo design tava muito apagado e por isso, vou deixar a página assim mesmo até ter uma idéia melhor). É legal ele ter opções de várias linguagens e fica bonitinho… :)

Nos últimos dias, também li alguns trechos do “Algoritmos: Teoria e Prática”. Esse livro é bem complicadinho… No fim, tem 70 páginas (da 820 a 890) somente falando sobre propriedades das somatórias! Mas é totalmente bem explicado e tem muito conteúdo. Acho que foi uma ótima coisa ter comprado ele. Acho que o custo-benefício dele tá ótimo.

Hoje configurei o Slackware inteiro do Héliton via SSH (ainda bem que a internet tava boa nos dois lados), toquei um pouco de pandeiro (oO, tô quase igual o Robertinho Silva… :lol: ), respondi alguma coisa em fóruns, ouvi música, assisti televisão… No fim, fiquei cheio de trabalho de escola pra fazer amanhã.

Bom… Mês que vem é a prova da OBI, o Papa morreu (90000 pessoas no Vaticano!? Alguém quer tentar calcular a densidade demográfica?), houve uma chacina totalmente cruel na Baixada Fluminense, assassinaram a Terri nos EUA… Acontece tanta coisa no mundo! :blink:

Posted in Diversos | 1 Comment »