• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

skin

[Resolvido] Combinatórias - Necessito explicação

9 mensagens neste tópico

Boas,

bem para tentar resolver um problema de programação, necessito de saber combinatórias ( ou combinações ).

Até aqui consegui chegar. Agora tenho de arranjar um algoritmo para me fazer a combinatória (combinação) que necessito, alguém me pode explicar como se faz isto à mão? Tipo se fosse fazer no papel sem máquina de calcular. Já andei a ler alguns artigos pela grande rede mas não consegui entender :\.

Isto salvo erro dá-se em estatistica aplicada na faculdade...

Desde já agradeço as respostas  ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas,

aqui vai um algoritmo recursivo que gera combinações, de longe o mais usado (pelo menos em concursos de programação):

void go_comb(int depth, int init, int final, int len)
{
int i;
if(depth==len)
{
	for(i=0; i<depth; i++)
		printf("%d", comb[i]);
	printf("\n");
	return;
}
for(i=(depth!=0 ? comb[depth-1]+1 : init); i<=final; i++)
{
	comb[depth]=i;
	go_comb(depth+1, init, final, len);
}
}

Chamas a função assim (por exemplo):

go_comb(0, 1, 5, 3);

para produzir um output do género:

123

124

125

134

135

145

234

235

245

345

Ou seja, todas as combinações com os algarismos de 1 a 5 de comprimento 3.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

pcaldeira, eu quero é entender como fazer não quero já feito ;).

Além disso não é bem isso que pretendia, por exemplo diz 5 bolas quantas combinações são possíveis com a distribuição de bolas por 500 copos.

Betovsky vou ver. Não sei se serve mas uma explicação matemática da coisa dava era de grande utilidade :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas queres o número de combinações possíveis ou a listagem das combinações?

Se for o primeiro caso é apenas aplicar a fórmula.

Se for o segundo é como o pcaldeira disse, basicamente vai ser o produto cartesiano da lista de opções.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É o primeiro caso que quero.

Eu vi a fórmula:

d0f8192d823750dc427f41c978d49c15.png

No entanto não consegui ainda entender como a desenvolver, como fazer esta fórmula só com o papel e lapiz.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A fórmula do factorial percebes, certo?

Considera então n=5 e r=3.

Como só queres 3 elementos (e admitindo, por enquanto, que a ordem conta), ficas com 5*4*3 hipóteses (5 para a primeira posição, 5-1 para a segunda, e 5-2 para a terceira), ou seja, 5*4*3*2*1/(2*1)=5!/(5-3)!.

Mas as repetições também não te interessam. E quantas repetições tens? Com 3 valores diferentes, consegues criar 3! sequências diferentes, num entanto só queres contar uma. Ou seja, 1/3! dos conjuntos obtidos não te interessam.

Resumindo, ficas com (5!/(5-3)!)/3!.

Generalizando o raciocínio, chegas à fórmula que apresentaste.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isto salvo erro dá-se em estatistica aplicada na faculdade...

Não, dá-se no 12º ano.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Obrigado pela explicação Rui Carlos :D.

pedrosorio, então parece que vou dar isto para o ano ;).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora