[Programación] Re: [Programación] =?iso-8859-1 ?q?Re:=20[Programaci=F3n]=20Re: =20[Programaci=F3n]=20=3D=3Fis? = =?iso-8859-1?q?o-8859-1=3Fq=3F Re:=3D20[Programaci=3DF3n]=3D20 Fwd:=3D20Re:?= =?iso-8859-1?q?= 3D20[Programaci=3DF3n]=3D20R=3F =3D=20=3D=3Fiso-8859-1=3Fq?= =?i

[Rafael Bidegain]

On Tue, 15 Mar 2005 14:09:35 -0300 (ART), Horacio Castellini
<horacio9573@yahoo.com.ar> wrote:
> > > yo no lo pensé asi, sino lo pensé como la solución
> > a
> > > la biblioteca de babel (que es un cuento de
> > Borges),
> > > en lugar de agrupar en palabras de 5 números
> > pienso en
> > > una palabra de 20 números de las cuales tomo 4
> > cadenas
> > > de 5 números. Es decir mi cadena original es
> > >
> > > 1 2 3 ... 18 19 20. Las posibles cadenas
> > diferentes
> > > que se pueden formar con esta son 20!-1. En las
> > cuales
> > > se incluye las permutaciones cíclicas. Entonces
> > > entablo una relación biunívoca entre las cadenas y
> > los
> > > cartones de la siguiente forma...
> > >
> > > 1 2 3 4 5 .... 18 19 20 <------> 1 2 3 4 5
> > >                                  6 7 8 9 10
> > >                                  ........
> > >
> > > En lugar de preocuparme por los cartones que es
> > más
> > > dificil de abordar me preocupo por las cadenas que
> > es
> > > más simple de abordar teóricamente....
> > >
> > > No sé si fuí claro...
> > sip.
> > pero observa lo siguiente:
> 
> Aunque no lo creas... he consultado el problema con un
> experto en análisis combinatorio y grafos de la LM
> (licenciatura en matemáticas) y me ratifico que el
> razonamiento anterior era correcto, es decir hay 20!
> (son las permutaciones de 20) cartones...  yo también
> dudaba de la cantidad... pero no... el razonamiento
> anterior esta bien...
> 
> > si tomo el grupo [1,2,3,4,5] para generar los tres
> > grupos restantes
> > debo utilizar
> > [6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
> > al grupo [1,2,3,4,5] no lo puedo volver a utilizar,
> > tampoco a los otros tres
> > para el segundo paso debo/podria/deberia usar el
> > grupo [1,2,3,4,6] y
> > para generar los tres restantes debo utilizar
> > [5,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
> >
> > creo que no hay dificultades en generar el primer
> > grupo de 5 y si
> > muchas en generar los tres restantantes ya antes de
> > utilizarlos debo
> > controlar si no forman parte de otra solucion.
> 
> Esto es, como vos palteás el algoritmo... pero una
> cosa es el algoritmo y otra es la cantidad de cartones
> posibles que hay.... No soy un experto en análisis de
> complejidad de algoritmo salvo para casos muy
> conocidos y que se reducen al tipo n**p y n*log(n). Te
> recomiendo que hagas un análisi de la complejidad...
> porque en este tipo de problema es lo primero que uno
> debe enfocarse, pues no estamos hablando de 10ms de
> tiempo de micro sino de varias horas y hasta días...
> si tenés contacto con la gente de la UBA hay gente que
> se dedica a esto exclusivamante...
> 
> Debo reconocer que por fin alguien que plantea algo
> como la gente y que va más alla de la impresora fiscal
> o aprender c/c++.
> >
> > saludos
horacio

te estoy muy agradecido por la atencion que le dedicas al tema y por
haber molestado al experto en la materia (claro que te creo!)

quiza mi planteo fue confuso, te aseguro que el universo de cartones
es de 15504 ya que no importa el orden y no puede haber repeticiones.
o sea c(20,5)
en un mail anterior (respuesta a Pablito) le decia que
si vos tomas 1 carton hay (en el universo de 15504) solo 1001 cartones posibles.
despues de seleccionar 2 cartones solo hay 126 cartones que se pueden
seleccionar.
y despues de seleccionar 3 cartones solo hay 1 carton que completa la solucion.

como llegue a esto??
probando...
pego el programa que utilice, 
para llegar a 1001 la constante TOPE debe estar definida como 6
para llegar a 126 la constante TOPE debe estar definida como 11
para llegar a 1 la constante TOPE debe estar definida como 16

creo que el programa es facil de entender
tomo como base para calcular el carton formado por los numeros [1,2,3,4,5]
genero todos los cartones y por cada carton pregunto si en el nuevo
carton generado hay numeros menores que la constante y los voy
contando

saludos
#include <stdio.h>
#define TOPE 6

int main(void){
int a, b, c, d, e;
int canti;
int senial;

canti=0;
for (a=1; a<17; a++)
for (b=a+1; b<18; b++)
for (c=b+1; c<19; c++)
for (d=c+1; d<20; d++){
        senial=1;
        if (a<TOPE) senial = 0;
        if (b<TOPE) senial = 0;
        if (c<TOPE) senial = 0;
        if (d<TOPE) senial = 0;
        if (e<TOPE) senial = 0;
        if (senial)
                canti++;
}

printf("hay %d cartones que se pueden combinar con el
carton[1,2,3,4,5]\n",canti);




return 0;
}




-- 
/* Rafael Bidegain
Linux Registered User # 204304
CaFeLUG Grupo de Usuarios de Software Libre de Capital Federal
http://www.cafelug.org.ar */