[ Foro de Pascal ]

Tipos enteros y reales [COMBINATORIA]

16-Apr-2014 13:59
Invitado (Marc)
6 Respuestas

Hola!

Bueno, me he atrevido a crear un pequeño programa para hallar todas las combinaciones posibles en el típico juego de lotería 6/49. Así, me entreno con los ciclos, las fórmulas y los tipos de datos de enteros y reales. Y aquí, es donde me surge el problema.

Bueno, he usado la fórmula de combinatoria:

C = m! / n! * (m! - n!)

Osea...si escojo 10 elementos (10 números) y selecciono 6 bolas me ha de dar 210 combinaciones. El programa que posteo funciona hasta que seleccionamos 20 elementos (20 números).

20 números y 6 bolas son 38760 combinaciones (sin repetición).

Pero si escogemos 21 números y 6 bolas, mi programa da: 15079 y es un error. Ya que lo correcto son 54264 combinaciones.

Y me gustaría llegar al cálculo de todas las combinaciones sobre 49 y 6 bolas. Que son:
13.983.816.

Creo que el error esta en como defino los tipos o si mi ordenador tiene capacidad para realizar la multiplicación de factoriales. Osea, 49*48*47*46*45*44...etc.

Os dejo el programa y haber donde esta el error :(

 
{ FORMULA: C (m,n) = m!/n!*(m! - n!) }
 
program formula_combinaciones;
 
var
 
    i : byte;
    fact_m, fact_aux : qword;
    fact_n : integer;
    combi : extended;
 
begin
    writeln('Introduce el numero elementos m!');
    readln(fact_m);
    writeln('Introduce cuantos elementos combinar n!');
    readln(fact_n);
 
    fact_aux := fact_m - fact_n;
    writeln('La resta factorial m! y factorial n! es ', fact_aux,'!');
    writeln();
    for i := fact_aux-1 downto 2 do
        fact_aux := fact_aux * i;
    for i := fact_m-1 downto 2 do
        fact_m := fact_m * i;
    for i := fact_n-1 downto 2 do
        fact_n := fact_n * i;
 
    writeln('FACTORIAL DE m! ',fact_m);
    writeln('FACTORIAL DE n! ',fact_n);
    writeln();
 
    {FORMULA}
    combi := fact_m / (fact_n * fact_aux);
 
    writeln('Salen ', combi:2:0  , ' combinaciones...');
end.
 



18-Apr-2014 11:51
Nacho Cabanes (+31)

Prueba a hacer un programa que te muestre sólo los factoriales de los números desde 1 hasta 30 y cuenta si funciona correctamente. Eso te dará la pista de lo que está fallando.


18-Apr-2014 12:53
Invitado (Marc)

Pues voy probando cosas (cambiando el valor de tipo) y la verdad, no me sale. Al pasar de 19 o 20 números, lo resultados no son correctos.

 
program factorial;
 
var
	fac : qword;
    i : integer;
begin
	fac := 0;
	readln(fac);
	for i := fac-1 downto 2 do
		begin
			fac := fac * i;
			writeln(fac)
		end;
end.
 


Si en la variable fac, pongo un tipo real (que parece soportan mas números) me dice que es un tipo incompatible con la variable i de iteración FOR.


20-Apr-2014 13:11
Nacho Cabanes (+31)

Ese es el problema: los factoriales crecen tan rápido que enseguida desbordas el rango de valores aceptables para un número entero (uses el tipo de dato que uses).

Por tanto, en tu ejercicio original de combinatoria, deberás replantear la forma de hacerlo:  pensar que 30! / 28! es 30 * 29, en vez de desarrollar por completo los factoriales.


20-Apr-2014 20:49
Invitado (Marc)

Pero en tu ejemplo aún debo llegar hasta 30!  y en mi código a partir de 20! de desborda la variable.

Si multiplico 30 * 29 me da 870 ¿Y que hago con ese valor?

En cambio 30! / 28! no lo puedo desarrollar con mi código. Seguro que algo se me escapa...


21-Apr-2014 12:28
Nacho Cabanes (+31)

Precisamente eso es lo que quiero que pienses.  ;-)

Las combinaciones de 30 elementos tomados de 28 en 28, o C(30,28), o "30 sobre 28", se calculan como 30! / (28! x 2!)

( Cuidado: la fórmula que tú propones está mal: te falta el paréntesis del denominador, y el último operando no es m!-n! sino (m-n)! )

Si intentas aplicar esa definición, desbordarás el rango de un entero, porque es un número aún mayor que el 20! a partir del que estás obteniendo problemas.

Pero si te das cuenta de que esa operación se puede "simplificar" y convertir en 30*29/2 verás que hay una forma alternativa de plantearlo, y de esa forma no desbordarías el rango de los números enteros. Lo que te propongo es que no apliques la definición "a ciegas", sino que pienses en algún planteamiento alternativo.


21-Apr-2014 21:44
Invitado (Marc)

Hola...

¿Así estaría correcta la fórmula?

FORMULA:

C (m,n) = m!/ (n!*(m - n)!)






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)