Mozilla mais uma vez dentro dos prazos… Acaba de sair o Firefox 1.5 e o site do GetFirefox, agora redirecionando para Mozilla.com, tá com um design bem bonito pra comemorar a data… Só pra dar o recado! :)
OBS.: Ele ainda não saiu em português brasileiro…
Impressionante a quantidade de besteiras que todo programador faz… Às vezes, uma semana depois de fazer um programa ou um site, eu já sinto raiva do script que acabei de fazer e me sinto obrigado a refazê-lo. Brincando um pouco nas férias, estou refazendo vários problemas da OBI e cada vez mais percebo a quantidade de lixo que achamos nos nossos scripts. E o pior é perceber o tempo que eu levava pra fazer aqueles problemas que podiam ser resolvidos de maneira tão simples (e eu pensava que tinha uma solução muito boa)… Estou resolvendo a lista de tarefas da modalidade Programação Nível 2, mas apenas os problemas de grafos (todos eles eu já tinha resolvido, mas estou agora programando-os melhor). Confiram as besteiras que eu fiz nos primeiros deles:
Um problema de grafos? Não! Mas parece muito. Na verdade, se ele pedisse qualquer coisa mais do que o grau de cada vértice eu precisaria de representar usando grafos, mas a única coisa que ele quer é que eu conte a quantidade de vezes que cada número aparece na entrada.
A primeira solução deste problema, que agora já não está mais entre nós, foi feita no curso de programação básica da OBI 2004, em Campinas, quando começava a aprender grafos. Pra vocês terem uma idéia do drama, eu fiz uma busca em profundidade pra contar o número de arestas que cada vértice tem (pra medir o grau de cada vértice).
Confiram a básica solução que fiz ontem: (e que daqui a algum tempo posso vir a achar ridícula também… hehehe)
#include
#define AMAX 101
int main() {
int a, v, x, y, t[AMAX]; // t = tráfego, grau dos vértices
int i, maior, teste=1;
while (scanf("%d %d", &a, &v)&&a&&v) {
maior=0;
for (i=1; i<=a; i++) {
t[i]=0;
}
for (i=0; i
t[x]++;
t[y]++;
if (t[x]>maior) {
maior=t[x];
}
if (t[y]>maior) {
maior=t[y];
}
}
printf("Teste %d\n", teste++);
for (i=1; i<=a; i++) {
if (t[i]==maior) {
printf("%d ", i);
}
}
printf("\b\n\n");
}
return 0;
}
O objetivo é achar o caminho mínimo de peso de 1 a N. Uma simples busca em profundidade resolve o problema. Agora vejam a busca em profundidade que eu faria em 2004, que ainda não tirei da minha galeria de códigos: batuira.c e comparem com a que eu fiz ontem (e que ainda poderia ser melhorada):
#include
#include
#define NMAX 101
int n, marc[NMAX], g[NMAX][NMAX];
int resultado;
void buscaemprofundidade(int v, int soma) {
int w;
if (v==n) {
if (soma
}
} else {
marc[v]=1;
for (w=1; w<=n; w++) {
if (g[v][w]&&!marc[w]) {
buscaemprofundidade(w, soma+g[v][w]);
}
}
}
}
int main() {
int x, y, xy;
int i, j, teste=1;
while (scanf("%d", &n)&&n) {
resultado=MAXINT;
for (i=1; i<=n; i++) {
marc[i]=0;
for (j=1; j<=n; j++) {
g[i][j]=0;
}
}
while (scanf("%d %d %d", &x, &y, &xy)&&x&&y&&xy) {
g[x][y]=xy;
g[y][x]=xy;
}
buscaemprofundidade(1, 0);
printf("Teste %d\n%d\n\n", teste++, resultado);
}
return 0;
}
Esse foi com certeza meu maior susto. Foi por causa desse problema que eu resolvi escrever este artigo... Dá até vergonha de mostrar a busca em profundidade que usei para resolver o problema anteriormente. O objetivo do problema é descobrir partindo de que vértice do grafo o vértice que se encontra mais longe tem custo menor. Ou seja, é só fazer uma busca em largura com todos os vértices. Mas antigamente eu não simpatizava muito com a busca em largura, então fiz aquela besteira. E imaginem quanto tempo eu não levei pra fazer aquela joça... Bom... Pelo menos deve ter servido pra eu quebrar a cabeça naquela época! Vejam o código novo (sujeito a mudanças, é claro!):
#include
#include
#define NMAX 101
int main() {
int w, i, j, x, y, teste=1, g[NMAX][NMAX], n, d[NMAX], fim, ini, fila[NMAX], v, a, md[NMAX], c;
while (scanf("%d", &n)&&n) {
for (i=1; i<=n; i++) {
for (j=1; j<=n; j++) {
g[i][j]=0;
}
}
for (i=1; i
g[x][y]=1;
g[y][x]=1;
}
c=0;
md[0]=MAXINT;
for (v=1; v<=n; v++) {
for (i=1; i<=n; i++) {
d[i]=n;
}
md[v]=0;
d[v]=0;
ini=0;
fim=0;
fila[fim++]=v;
while (ini!=fim) {
a=fila[ini++];
if (d[a]>md[v]) {
md[v]=d[a];
}
for (w=1; w<=n; w++) {
if (g[a][w]&&d[w]==n) {
d[w]=d[a]+1;
fila[fim++]=w;
}
}
}
if (md[v]
}
}
printf("Teste %d\n%d\n\n", teste++, c);
}
return 0;
}
Bom... Simplificando... Se você não é programador, não seja; você vai ficar louco! :lol: Este problema que citei aqui não acontece só com esses problemas de olimpíadas mas também com vários scripts, principalmente os que vamos alterando com o tempo e adicionando novas features. Já recomecei do zero muitos sites para deixá-los decentes e muitos programas também (essa versão do aeroporto.c já é a terceira!) e não só esses de olimpíadas (o meu programa de ouvir música, em Bash, eu já fiz umas 10 vezes).
Quando eu acabar de re-resolver todos os problemas da seção de códigos lógicos eu vou publicar todos juntos. Por enquanto, vou deixar tudo do jeito que tá pra vocês apreciarem meus scripts mal-feitos. ;)
Quem costuma visitar meu blog perceberá que apareceu um ícone lá no canto inferior direito, escrito Bom Demais para o IE. A imagem, posicionada lá embaixo usando um position:fixed; (que o IE não suporta) é de uma campanha muito legal que você pode conhecer clicando no link. Participem e tenham um site "bom demais para o Internet Explorer"! :)
Acabou a OLIS e agora definitivamente o ano letivo. Comecei a rotina de estudos de leve… Por enquanto só relembrando aonde tinha parado: Brinquei um pouco de C, alocando memória, escovando bits até não aguentar mais; implementei alguns algoritmos em grafos (de problemas já anteriormente resolvidos, do site da OBI) e agora estou exercitando fluxos em rede. O primeiro passo foi me desviciar de usar busca em profundidade resolvendo vários programas anteriormente resolvidos de grafos agora com busca em largura e nessa próxima semana espero ter dominado o algoritmo de coloração, de bipartição e os fluxos em rede.
Pedi na Saraiva (temos que aproveitar o site inteiro em 12x sem juros e frete grátis) o livro Java – Como Programar, dos Deitel. Várias pessoas me recomendaram e acho que vai ser bom pra aprender Java de uma maneira mais “certinha” (não que pesquisando na internet não aprendemos de forma certa, mas com a didática de um livro tudo é bem mais fácil e a gente aprende as coisas numa ordem boa).
Estou acabando de reformular o site do Colégio, porque já que cada vez tem uma coisinha nova o design tava ficando muito cheio e o XHTML pouco acessível. Agora tá ficando mais clean e deve estar lá amanhã de tarde (só falta um pequeno detalhe: fazer funcionar em um troço da Microsoft que não pode ser considerado um navegador)
… além dos meus feeds. Agora eu criei um perfil público no Bloglines (idéia do Zé) e vocês podem ver meus feeds aqui.
Vi ontem no site da Olimpíada Regional de Matemática o resultado deste ano. Fiquei só com uma menção “horrorosa”, no nível 3. Até que tá bom… Eu já não esperava muito, porque em nenhuma das duas fases eu fui bem. Então aproveito pra pensar as coisas pelo lado bom: quem ganha menção honrosa é premiado primeiro na cerimônia de premiação da UFSC! :)
Meu irmão (Bruno) e o Ivo pegaram bronze na mesma categoria… Nas outras categorias, não sei como o pessoal do Colégio foi porque não sei o nome completo das criaturas que fizeram a prova.
Meu fórum, SOSPHP, voltou ao ar depois de uns problemas com o servidor; agora tá de servidor novo! (que chique…) Participem, pô!
Hoje foi minha última aula desse ano e abertura da OLIS (olimpíada do meu colégio). Começaram extra-oficialmente as férias. Finalmente vou ter um tempinho pra poder estudar informática, matemática e música; aproveitar a praia, viajar, ler… Demorou, hein?
Como toda pessoa organizada (categoria que eu não me enquadro, mas estou tentando), fiz meu “plano” para aproveitar bem essas férias e também para decidir o que eu vou querer no ano que vem. Aqui embaixo está publicado, e sujeito a mudanças (porque meus objetivos sempre podem mudar). Notem também que eu coloquei algumas coisas como “ganhar olimpíada” que seriam conseqüência das outras ações. Além disso, eu coloquei alguns objetivos que podem parecer “sonhos”, mas acho que sempre é bom traçar objetivos difíceis pra tentar ir o mais longe possível.
Acho que foi a área em que eu menos evoluí nesse ano. É que é incrível que quanto mais eu aprendo, mais percebo que ainda tenho cada vez mais coisa a aprender. Isso não faz sentido matematicamente falando… A informática é desafiante e a gente sempre tem a impressão de que somos ignorantes. É como o Zeh falou num post em seu blog: “O mais legal de ser programador é olhar pra certas coisas que você fez no passado, que achava uma grande idéia, e perceber que aquilo era algo extremamente fedorento.”
Mas vamos lá…
Nesse ano, fui mal nas duas olimpíadas (brasileira e catarinense) e mesmo ganhando medalha de bronze na Olimpíada de Maio, não fiquei muito contente. De qualquer maneira, sinto que estou evoluindo na matemática graças as aulas do Vavá e mesmo as do Fabiano, que são lerdas mas às vezes trazem uma novidade.
Física depois desse ano entrando na minha lista de matérias legais e que eu preciso estudar bastante pra passar no ITA… Vamos à lista…
Resolvi parar de trabalhar no Colégio, porque o salário era muito baixo (cerca de 200 reais é pouco, mesmo pra trabalhar 10 horas por semana) e o emprego fixo é muito chato (tem dias que eu vou lá e não faço nada, outros dias que tem um monte de coisa pra fazer e eu não consigo acabar nada; fora os alunos que vão lá no Lab. de Informática encher o saco – hehehe). Vou pegar mais freelances e acho que vou lucrar mais me dedicando só a isso e aos estudos, tanto financeiramente quanto nos aprendizados. Mas vou fazer uma proposta ao Colégio que é continuar mantendo o site deles (afinal, eles precisam de alguém pra fazer isso), mas fazer de casa e com isso só perder tempo quando precisar de alguma mudança, em casa!
Compras prioritárias que estou querendo fazer de livros e acessórios nesse ano… Aceito presentes! :D
Viagens [sendo] programadas…
No ano que vem, quero voltar a fazer aula de piano. Acho que farei com a mãe de uma amiga, que dá aula na ADMITA.
Nesse final de semana fomos pra Curitiba (quem acompanha meu feed viu as fotos no Flickr). Meu irmão Bruno fez vestibular pra música/violão na UNICAMP. Ele não achou a prova muito difícil e falou que acertou uns 80%. Ainda tem mais uma fase de prova de conhecimentos gerais e depois é a prova de aptidão (violão). Acho que ele passa… :)
Alguém tem notícias dos caras da UFSC? Já fizemos a final da Olimpíada Regional Catarinense de Matemática (por que eles não mudam o nome pra quem é de fora saber de onde que é e quem é de dentro não pensar que toda a Região Sul participa da olimpíada?) há dois meses, o ano já vai acabar, e NADA! (nem mesmo o gabarito da prova, mesmo sem o resultado final…)
Sempre que eu escrevo posts grandes, eu me perco no meio. Então se alguma parte ficou difícil de entender ou se tem algum erro de português aí, me avisem! :)