Arquivo da tag: gcd

Desafios Lógicos e Sites

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

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.

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.

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

Função para MMC e Gerador de Gráficos em Setores

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

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:

MMC como as pessoas fazem

  • 4, 5 | 2
  • 2, 5 | 2
  • 1, 5 | 5
  • 1, 1 | /
  • 2 . 2 . 5 = 20

[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:

MMC pelo meu programa

  • 4, 5 – qual o maior? 5.
  • 5*2 é múltiplo de 4? Não.
  • 5*3 é múltiplo de 4? Não.
  • 5*4 é múltiplo de 4? Sim.
  • MMC encontrado: 5*4=20.

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.

MMC com três termos no meu programa

  • 4, 5, 6 – qual é o maior? 6.
  • 6*2 é múltiplo de 4? Sim. Segue. É múltiplo de 5? Não. Para.
  • 6*3 é múltiplo de 4? Não. Para tudo.
  • 6*4 é múltiplo de 4? Sim. Segue. É múltiplo de 5? Não. Para.
  • 6*10 é múltiplo de 4? Sim. Segue. É múltiplo de 5? Sim.
  • MMC encontrado: 6*10=60.

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

Método convencional – MMC de três termos

  • 4, 5, 6 | 2
  • 2, 5, 3 | 2
  • 1, 5, 3 | 3
  • 1, 5, 1 | 5
  • 1, 1, 1 | /
  • 2 . 2 . 3 . 5 = 60

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…