Estou hospedado na casa do meu irmão, em Campinas, desde ontem de manhã (viajei domingo a noite de ônibus). Hoje foi o primeiro dia do curso preparatório para a seletiva da IOI2006, que começou às 9h00 devagarinho.

O dia hoje serviu para “nivelar” os participantes e treinar um pouquinho a resolução de problemas. De manhã, algumas pessoas tiveram uma aula sobre estruturas de dados, grafos e o básico de programação dinâmica e outras (a maioria) resolveram três problemas da Universidade de Valladollid:

412 – Pi

Enunciado – Minha Solução

Não é um problema muito complexo, mas eu usava um algoritmo muito demorado para determinar se dois números tinham ou não um fator comum, que não passava por tempo limite excedido. Então, o Fábio Dias Moreira nos passou uma propriedade bem interessante de MDC (Máximo Divisor Comum):

mdc(x, y) = mdc(x%y, y)

(onde o % é o resto da divisão, no C)

Aí dá pra fazer uma função recursiva mdc bem rápida, que eu apliquei na [minha solução][3].

441 – Lotto

Enunciado – Minha Solução

Esse problema nem tem muito o que comentar. Implementação de dois minutos… hehehe… Eu podia ter feito uma função recursiva pra ficar um pouco mais “decente” (e poder mudar de 6 para outro número no futuro), mas não tinha necessidade, então ficou assim mesmo (e passou de primeira no site).

543 – Goldbach’s Conjecture

Enunciado – Minha Solução

O objetivo é provar a Conjectura de Goldbach para todos os pares menores que 1000000. Meu programa ainda não roda dentro do tempo, mas depois vou continuar a adapta-lo. Eu posso, por exemplo, ir fazendo a média entre o maior possível e o menor possível (aquele “algoritmo” que usamos quando alguém fala: “Pensei num número de 1 a 100. Tente advinhar…”) ao invés desses loops, o que já vai tornar o programa mais rápido (não sei se o suficiente).

Nesse problema, o Fábio me lembrou do Crivo de Eratóstenes. Bem interessante, nunca tinha implementado. :)

Provavelmente pela primeira vez, o almoço dos participantes do curso não foi no “bandeijão”, mas sim num restaurante chique perto do IC. Achei bem legal… Além de andar menos, o ambiente é melhor e a comida também.

Durante a tarde, o Fábio nos passou o algoritmo de Longest Common Subsequence (esse eu já sabia… hehehe) e depois o algoritmo que resolve o problema Subseqüências que caiu na prova da segunda fase (esse um pouquinho mais complicado!). Esse segundo eu pretendo implementar e depois até fazer um artigo sobre…

Depois, o Fábio nos deu algumas dicas, principalmente sobre os cálculos problemáticos que o computador faz com pontos flutuantes (algo bem interessante, que eu não entendia porque acontecia). Por exemplo, quando criamos um double x=0.1 o seu valor não é 0.1, mas sim o 1/1010 (em binário) que dá uma dízima periódica! E isso não é muito agradável, pode gerar até loops infinitos… Então, ele sugeriu que criássemos uma função para comparar dois números reais, com um código como esse:

/*
USO: Substituir...
x == y <==> cmp(x, y) == 0
x != y <==> cmp(x, y) != 0
x < y <==> cmp(x, y) < 0
x ### y <==> cmp(x, y) ### y

O "###" é "qualquer-coisa". Hehehe...
*/

#include <math.h>

const double EPS = 1.0e-10

int cmp(double x, double y) {
	if (fabs(x-y)<EPS) {
		return 0;
	} else if (x>y) {
		return 1;
	} else {
		return -1;
	}
}

Foi um bom ponto de partida legal, começamos de leve. Ainda não sei sobre o quê será a aula de amanhã…

Seletiva IOI

Neste ano vão haver quatro provas para selecionar os quatro participantes que irão representar o Brasil na Olimpíada Internacional de Informática em agosto, no México. As três primeiras, identificadas como “testes” no calendário da seletiva, terão apenas um problema e durarão duas horas cada uma. A última será no domingo, às 7h45min, terá três questões e durará cinco horas (pô, vou perder o comecinho do jogo de Brasil contra Austrália!). Achei legal esse método, mas como o César Kawakami disse: dessa maneira, não treinamos a estratégia, que é algo importante para a prova da IOI.

Por enquanto é só. Se der tempo, pretendo colocar um post por dia sobre o curso até o final dessa semana. :)

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:

1. a a a
2. a a b
3. a a c
4. a b a
5. a b b
6. a b c
7. a c a
8. a c b
9. a c c
10. b a a
11. b a b
12. b a c
13. b b a
14. b b b
15. b b c
16. b c a
17. b c b
18. b c c
19. c a a
20. c a b
21. c a c
22. c b a
23. c b b
24. c b c
25. c c a
26. c c b
27. 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.

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.

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

Calcula o Máximo Divisor Comum (MDC) de vários termos

//MDC (Máximo Divisor Comum)
#include <stdio.h>
#include <values.h>

#define NMAX 101

int mdc(int *n, int tam) {
	int i, menor, desista, j;

	menor=MAXINT;
	for (i=0; i<tam; i++) {
		if (n[i]<menor) {
			menor=n[i];
		}
	}

	for (i=menor; i>=1; i--) {
		desista=0;
		for (j=0; j<tam; j++) {
			if (n[j]%i) {
				desista=1;
				j=tam;
			}
		}
		if (!desista) {
			return i;
		}
	}

}

int main() {
	int n[NMAX], tam, i;

	printf("Digite o número de termos: ");
	scanf("%d", &tam);
	for (i=0; i<tam; i++) {
		printf("%do. número: ", i+1);
		scanf("%d", &n[i]);
	}

	printf("MDC = %d\n", mdc(n,tam));
}

Calcula o Máximo Divisor Comum (MDC) entre 2 termos

//MDC (Máximo Divisor Comum) entre dois números
#include <stdio.h>

int mdc(int x, int y) {
	int i, menor;

	if (x<y) {
		menor=x;
	} else {
		menor=y;
	}

	for (i=menor; i>=1; i--) {
		if (!(x%i)&&!(y%i)) {
			return i;
		}
	}

	return 0;
}

int main() {
	int x, y;

	printf("Digite o primeiro número: ");
	scanf("%d", &x);
	printf("Digite o segundo número: ");
	scanf("%d", &y);

	printf("MDC ( %d , %d ) = %d\n", x, y, mdc(x,y));
}

Calcula o Mínimo Múltiplo Comum (MMC) entre 2 termos

//MMC - Mínimo Múltiplo Comum, para dois números

int mdc(int x, int y) {
	int i, menor;

	if (x<y) {
		menor=x;
	} else {
		menor=y;
	}

	for (i=menor; i>=1; i--) {
		if (!(x%i)&&!(y%i)) {
			return i;
		}
	}

	return 0;
}

int mmc(int x, int y) {
	return x*y/mdc(x,y);
}

int main() {
	int x, y;

	printf("Primeiro número: ");
	scanf("%d", &x);
	printf("Segundo número: ");
	scanf("%d", &y);

	printf("MMC (%d, %d): %d\n", x, y, mmc(x,y));
}

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).

Baseando-me no programa KBruch (um joguinho educativo do KDE que serve pra somar e subtrair duas frações) resolvi fazer uma função que calculasse MMC (pra dar o resultado do KBruch bem rápido! Hehehe). A função recebe dois argumentos: o número de termos e os termos (num vetor) e ficou bem simpes (e eu até comentei). Vejam:

//Função para calcular o MMC

#include <stdio.h>

int mmc(int *num, int ntermos) {
	int i, maior=0, a, j, c;

	//Descobrindo o maior número
	for (i=0; i<ntermos; i++) {
		if (num[i]>maior) {
			maior=num[i];
		}
	}

	for (i=1; c!=1; i++) {
		c=1;
		a=maior*i;
		//Verificando se o maior número vezes o i atual é divisível por todos números do conjunto
		for (j=0; j<ntermos; j++) {
			if (a%num[j]) {
				c=0;
			}
		}
	}

	return maior*(i-1); //Retornando resultado
}

int main() {
	int n[1001], nt, i;

	//Recebe número de termos
	printf("Quantos termos? ");
	scanf("%d", &nt);

	//Recebe números
	for (i=0; i<nt; i++) {
		printf("%d: ", i+1);
		scanf("%d", &n[i]);
	}

	//Chama a função e imprime o resultado
	printf("\nResultado: %d\n", mmc(n, nt));

	return 0;
}

Depois eu fiquei pensando que eu não estou calculando MMC como as pessoas calculam, então depois vou desenvolver uma outra função que calcule o MMC como as pessoas geralmente fazem, tipo assim:

[update] Já criei esse programa agora:

//MMC do jeito que as pessoas tiram geralmente

#include <stdio.h>
int res[10000], co=0;

int mmc(int *n, int nt) {
	int i, k, dv, at;

	for (i=0; i<nt-1; i++) {
		printf("%d, ", n[i]);
	}
	printf("%d | ", n[nt-1]);

	dv=0;
	for (i=2; !dv&&at!=nt; i++) {
		dv=0;
		at=0;
		for (k=0; k<nt; k++) {
			if (!(n[k]%i)) {
				dv=1;
				n[k]/=i;
			} else if (n[k]==1) {
				at+=1;
			}
		}
		if (dv) {
			printf("%d\n", i);
			res[co++]=i--;
		}
	}

	if (at==nt) {
		return 1;
	} else {
		return i*mmc(n, nt);
	}
}

int main(void) {
	int n[1001], nt, i, resultado;

	printf("MMC - Mínimo Múltiplo Comum\n");
	printf("http://tableless.tiagomadeira.net/script/mmc-comum.c\n\n");

	printf("Este programa calcula o MMC de vários termos inteiros que você especifica.\n");
	printf("Foi criado por Tiago Madeira usando um algoritmo semelhante ao que os professores\n");
	printf("de matemática ensinam nas escolas.\n\n");

	printf("De quantos números você quer calcular o MMC? ");
	scanf("%d", &nt);
	for (i=0; i<nt; i++) {
		printf("Digite o %d. número: ", i+1);
		scanf("%d", &n[i]);
	}
	printf("\n");

	printf("Para você calcular o MMC de vários termos, basta você ir dividindo eles por primos\n");
	printf("até todos se tornarem o número 1 (um). O programa faz isto exatamente como você\n");
	printf("faria. Acompanhe o cálculo abaixo:\n\n");

	resultado=mmc(n, nt);
	printf("X\n\n", resultado);
	for (i=0; i<co-1; i++) {
		printf("%d . ", res[i]);
	}
	printf("%d = %d\n", res[co-1], resultado);

	printf("Ou seja, o menor número que é divisível por todos os números que você colocou é\n");
	printf("este. Isto tem grandes utilidades e uma delas (talvez a mais utilizada) é fazer\n");
	printf("cálculos com frações de denominadores diferentes.\n\n");

	printf("Observação: Este cálculo é a maneira com que as pessoas costumam aprender, mas\n");
	printf("desenvolvi um outro programa que (além de falar menos) tem um custo menor\n");
	printf("(calcula de forma mais rápida). Ele está disponível em\n");
	printf("http://tableless.tiagomadeira.net/script/mmc.c\n");

	return 0;
}

[/update]

Mas meu programa faz assim:

Mas com dois termos é bem simples (tem uma função para dois termos no programa do KBruch). O legal é que a minha função funciona com o número de termos que eu quiser. Vou demonstrar como ela funciona para três termos.

Acho que fica mais simples de entender no método convencional mesmo…

E por causa disso, desenvolvi um programa que calcula da forma tradicional o MMC. É uma função recursiva. Ele é bem didático e mostra todo o raciocínio e algumas observações, porém o seu custo é maior (é mais demorado) que o primeiro.

Bom, nas aulas de matemática, andei desenvolvendo uns scripts muito úteis pra não precisar ficar calculando muito. Fiz um que calcula juros compostos, mas não publiquei. O que eu publiquei foi o que você digita o rótulo e o valor de cada pedaço de um gráfico de setores e ele devolve o número de graus que cada um deve ter (é uma simples regra de três, mas mesmo assim fiz pra brincar mesmo). Veja:

//Gerador de Gráficos em Setores
#include <stdio.h>
#define NMAX 1001

int main() {
	int n, i;
	float valor[NMAX], vt;
	char rotulo[NMAX][50];

	printf("Qual o número de valores? ");
	scanf("%d", &n);

	vt=0;
	for (i=1; i<=n; i++) {
		printf("Rótulo (%2d): ", i);
		scanf("%s", rotulo[i]);
		printf("Valor  (%2d): ", i);
		scanf("%f", &valor[i]);
		vt+=valor[i];
	}

	printf("\nResultados:\n(graus que devem ser usados na confecção do gráfico)\n");
	for (i=1; i<=n; i++) {
		printf("%s: %.2f graus\n", rotulo[i], valor[i]*360/vt);
	}
}

Hmmm… Tirei um 5,8 em biologia numa prova sobre biomas (minha menor nota em três anos) :blink: e errei uma questão numa prova de física, justamente aquilo que eu tinha feito um programa, a força gravitacional. Eu esqueci de elevar a notação científica da distância ao quadrado e com isto, meu resultado na prova foi 1,27 . 10^22 ao invés de 1,27 . 10^32. Mas tudo bem…