Quiz� ALEJANDRO est� en el buen camino?

Pues no, Lo de Alejandro NO FUNCIONA !!!!!
Ya he reformado el programa de forma que el bucle exterior sea el que cambia los par�ntesis, luego un bucle intermedio que cambia los n�meros y el bucle interior que cambia los signos. Pues NO SE OBTIENE UNA LISTA ORDENADA. Por lo tanto no veo la forma de implementar la b�squeda que propone Alejandro.
Veamos un ejemplo:
El bucle exterior y el bucle medio nos entregan esta combinaci�n de par�ntesis y n�meros: (el signo $ indica que ah� va un signo a colocar por el bucle interior)
((((1 $ 2) $ 3) $ 4) $ 5) $ 6
Ahora el bucle interior nos entrega esta combinaci�n de signos:
+ * - / + que da como resultado 7
+ * - / * que da como resultado 6
Cuando debiera dar un resultado mayor si estuviera ordenado el asunto.
(el bucle interior cambia los signos en el orden: / - + * por lo que combina los signos desde / / / / / hasta * * * * * )
Otros ejemplos todav�a peores que muestran que no hay orden alguno:
+ + - + - que da como resultado 1
+ + - + * que da como resultado 42
+ + + - + que da como resultado 11
+ + + * * que da como resultado 300
+ + * + - que da como resultado 23
De momento no veo como lograr una lista ordenada. Esto est� claro que es la clave para la soluci�n del problema en tan s�lo dos segundos. Ni idea de c�mo lograrlo de momento. :-(

Jose ha intentado optimizar el bucle interno. Lo m�s l�gico a primera vista.

Enunciado del problema:

En TVE hace cosa de tres a�os emit�an un programa-concurso. Uno de los problemas m�s interesantes al que somet�an a los concursantes era la resoluci�n del problema de cifras. Era as�:

Te dan siete n�meros. Los seis primeros pueden ser de hasta dos cifras cada uno. El s�ptimo puede tener hasta tres cifras . Hay que intentar obtener el s�ptimo n�mero realizando operaciones con los seis primeros (en el programa no era necesario pero yo s� pongo la condici�n de que deben usarse todos los seis n�meros). Las operaciones permitidas son: suma, resta, multiplicaci�n y divisi�n entera (una divisi�n que da cero de resto).

Ejemplo:

Imagina que los seis n�meros son: 1,2,3,4,5,6 y el n�mero a buscar es el 901.
Podr�as entonces ir probando todas las posibles combinaciones. Probar�s primero 1+2+3+4+5+6 y luego 1+2+3+4+5-6, despues 1+2+3+4-5+6, etc. De esta forma ves que vas probando todas las combinaciones de signos con la misma combinaci�n de los seis n�meros. Cuando acabes las combinaciones de signos probar�s con otra combinaci�n de n�meros como por ejemplo: 1,2,3,4,6,5 hasta llegar a la combinaci�n 6,5,4,3,2,1 que es la �ltima.

Por tanto necesitas dos bucles: el exterior que va cambiando la combinaci�n de los n�meros a analizar y otro bucle interior que va cambiando los signos y comprueba si se ha alcanzado la soluci�n del problema.

Pero a�n se necesita un tercer bucle que ser� el m�s interno de los tres: un bucle que mueva los par�ntesis. Est� claro que no es lo mismo (5+2)*3-1+4+6 que esto otro 5+(2*3)-1+4+6

Mi programa:

He hecho un programa C++ para Windows (usando clases MFC y Visual Studio de Microsoft) que representa muy intuitivamente la parte del �rbol que se est� explorando en ese momento. Uso tres bucles: el externo cambia las cifras, luego otro cambia los signos y el m�s interior cambia los par�ntesis.

Los dos primeros bucles vienen representados por sendas barras de progresi�n y encima de cada una se muestra la combinaci�n que est� siendo analizada en ese momento.

Aqu� tienes el aspecto que presenta el programa luego de intentar encontrar el n�mero 901 con una combinaci�n de los n�meros: 1,2,3,4,5,6. Como ves este problema es irresoluble (no existe combinaci�n alguna que d� 901 como resultado) y si te fijas ver�s que mi programa ha tardado 21 minutos 14 segundos en terminar todo el "�rbol de b�squeda" (recorrer los tres bucles anidados) y presentarme la soluci�n m�s cercana.

�Quieres bajarte este programa? Pulsa en la imagen o pulsa aqu�.

Pues bien, hay un programa en la Web que termina el "�rbol de b�squeda" en dos segundos.

Mi programa tarda 21 minutos y el otro programa ��� TARDA DOS SEGUNDOS !!!

��� C�MO LO HACE ??? Supongo que tomando atajos en el "�rbol de b�squeda".
�Se te ocurre algo? Pues ��qu� esperas para escribirme?? -> [email protected]

Si alguien me escribe con alguna propuesta no tardar� nada en modificar el programa para comprobar si funciona.
Tenemos que lograr dejarlo en dos segundos como sea. Es una cuesti�n de honor: le he escrito al tipo de los dos segundos y no me ha querido contar c�mo lo ha hecho.
�Alguien desea el c�digo fuente? Es para Microsoft Visual Studio y est� en C++. Que me escriba y se lo paso, o si hay muchas peticiones lo pongo aqu�.

Vuestras contribuciones por e-mail (en azul mis respuestas):

E-mail de Alejandro:

Hola, colgao de la programaci�n ;-) Yo soy otro.

Es mi hobby preferido. Y cuando me encuentro con algo tan bestial como que alguien resuelve un problema en dos segundos cuando yo tardo 21 minutos cojo un pique... La web del tipo que lo resuelve en dos segundos es:
http://www.lleida.net/clients/chema/
y pulsando el boton Cifras y Letras vas a la p�gina donde bajarte cifras.zip y tools.zip que trae el ejecutable cifras.exe. Este programa a los 15 dias o as� ya no te permite entrar por lo que si le echas un vistazo �chaselo completo el primer dia. Nada m�s entrar, en el boton calculadora, si lo pulsas te lleva a un di�logo donde introduces seis n�meros y luego el resultado a buscar e intenta encontrar la f�rmula. Pues si le metes 1,2,3,4,5,6 y el 901 te dice en dos segundos que no hay resultado. Para saber esto tuvo que recorrer todas las combinaciones posibles. De otra forma no puede estar seguro que no se ha saltado alguna combinaci�n que da el resultado.

�Has oido hablar de las b�squedas dicot�micas en bases de datos, frente a b�squedas secuenciales?

Algo as� como el m�todo de ordenamiento del qsort.

Se trata de dividir la tabla en dos mitades, y mirar si el dato buscado est� a una parte o a otra (Por supuesto la tabla debe estar ordenada). Cuando sabes en qu� parte est� el dato, desechas el otro, y vuelves a dividir la parte que te interesa. As� sucesivamente hasta que das con el dato en cuesti�n.

Buen intento. Pero date cuenta que este es un truco (aunque creo que no vale para este caso concreto) que har�a que...
Espera un momento...
Como que no vale?
Tienes raz�n la lista est� ordenada pues 1+2+3+4+5+6 es muy bajo y 1*2*3*4*5*6 es mucho mayor.
Pues puede ser por aqu� la soluci�n. Entonces deber�a empezar a poner los signos empezando por el menos y no por el m�s como estoy haciendo. De esta forma - - - - - tiene que dar un resultado menor que + + + + +. Aunque quiz� entonces deber�a colocar la divisi�n de primera. El orden de los signos debiera ser entonces: / - + *
De esta forma 1/2/3/4/5/6 (aunque este caso concreto no est� permitido pues no se permite una division no entera) ser�a lo m�s bajo y 1*2*3*4*5*6 lo m�s alto.
Oye, pues seguir� mir�ndolo y voy a poner esto en la web. No se me hab�a ocurrido que la lista estuviera ordenada. A�n falta meter los par�ntesis y a ver si al meterlos la lista sigue ordenada que si no no valdr�a este TU m�todo.
Pues nada, a seguir mirando. Lo que vaya encontrando lo pondr� en la p�gina. Y mantendr� al tipo ese de los dos segundos informado a ver si se le ablanda el coraz�n y me cuenta el algoritmo usado que me tiene en ascuas el asunto.

Es lo primero que se me ha ocurrido en "dos segundos", pero no tengo tiempo ahora para ponerme a investigar. Estoy con un programa comercial que debo entregar el martes. Supongo que, si en vez de montar los bucles secuencialmente, consiguieras ingeniartelas para fraccionar las operaciones, por ejemplo, viendo cu�nto de cerca has estado del resultado, y aplicando cambios de caminos, se ejecutar�a m�s r�pido.
Por ejemplo, si realizas (1*2)+3+4+5+6, el resultado estar� demasiado lejos del resultado como para que sigas por ese camino; el programa deber�a intentar multiplicar por otro n�mero m�s grande. No s�, a lo mejor es una gilipollez

S�, probar una combinaci�n mucho mayor en el orden de signos: / - + * que hemos visto arriba que es el correcto (yo usaba el orden + - * / y por tanto buscaba desde +++++ hasta ///// y claro me sal�a desordenado el asunto. Con tu forma probablemente quede ordenado (falta comprobar los par�ntesis que lo miro ahora a ver...)

lo que estoy diciendo, pero a estas horas no se me ocurre nada mejor. Si en momentos de m�s tiempo y tranquilidad se me ocurre algo, te lo mando.

Seguro que ese es el camino correcto.

Creo que la �nica forma de conseguirlo es, o que tu programa ruede en un bicho a 45GHz, o dotar al programa de inteligencia.

El programa del tipo de los dos segundos lo hace en mi Pentium 166 y tarda lo dicho: dos segundos.

Chao Alejandro. Gracias.

He estado mirando la idea de Alejandro (que el �rbol si est� ordenado es mucho m�s f�cil). Creo que poniendo el orden de los signos: / - + * y luego poniendo los tres bucles as�: el exterior que mueva los par�ntesis, el siguiente mueve los n�meros y el interior los signos, y ya estar�a resuelto el asunto.
Ahora tendr�amos un �rbol de combinaciones cuyos resultados estar�an, creo, ordenados. De esta forma es f�cil recorrerla a saltos acerc�ndonos al resultado buscado. Genial, a ver si rula... Ahora a programarlo y probarlo...
�Alguien cree que hay otra soluci�n mejor? Pues nada, que lo diga que soy todo oidos.
Gracias una vez m�s Alejandro, seguro que es as�.

E-mail de Jose:

>
> Hola Bao
>
> He estado en tu p�gina y as�, de primera mano se me ocurre una cosa. Dices
>que en el bucle m�s interno tu programa mueve los par�ntesis, creo que hay
>una aproximaci�n mejor que esa.
>
> No s� si conoces la notaci�n polaca inversa, se trata de una forma
>diferente de expresar f�rmulas matem�ticas que tiene bastante utilidad en
>inform�tica. Una de las caracter�sticas m�s importantes es que no requiere
>el uso de par�ntesis.
>
> La idea es que los n�meros y las operaciones se van colocando "apiladas"
>de forma que una operaci�n afecta a los dos n�meros que tiene por debajo en
>la pila, veamos alg�n ejemplo (imag�nate una pila tumbada de forma que la
>parte inferior es la izquierda y la superior la derecha):

>Notaci�n normal         Notaci�n polaca inversa

>

>1�   3+(5*6)                  5  6  *  3  +

>2�   (3+5)*6                  3  5  +  6  *

>3�   (3*2)+(4*5)              3  2  *  4  5  *  +

> Las f�rmulas se leen as� (para la 1�):
>
>1. Se mete en la pila el 5.
>2. Se mete en la pila el 6.
>3. Se Multiplican los dos �ltimos n�meros metidos en la pila 5*6=30 y se
>mete en ella el resultado.
>4. Se mete el 3 en la pila.
>5. Se suman los dos �ltimos n�meros de la pila 30+3=33.
>
>
> Tal vez as� se puedan evitar de forma natural repeticiones que surgen
>utilizando el m�todo de los par�ntesis.
>

Much�simas gracias por tu idea Jose.
El m�todo que usa mi "bucle interior de par�ntesis" es una mezcla entre poner los par�ntesis normalmente y el m�todo notaci�n polaca del que hablas (y que por cierto es el que usa el ordenador pues si conoces assembler as� es exactamente como trabaja la CPU para los c�lculos con n�meros: metiendo en la pila los n�meros y ejecutando la operaci�n).

Voy a intentar explicarte lo que hace mi bucle de par�ntesis interno: Imagina que se llega a este bucle con los n�meros 1,2,3,4,5,6 (en este orden) suministrados por el bucle externo. Y que se llega con las operaciones en este orden: + - * + +
Entonces tenemos: 1 + 2 - 3 * 4 + 5 + 6
Y ahora hay que ir poniendo par�ntesis. Hay muchas combinaciones de par�ntesis.
La primera ser�a: (1 + 2) - 3 * 4 + 5 + 6
La �ltima ser�a quiz�, que ya no me acuerdo bien que hace mucho que lo program�:
1 + (2 - (3 * (4 + (5 + 6))))
(el programa lo hice har� unos tres a�os y no hace ni un mes que me encontr� con el del tipo este que lo resolv�a en dos segundos y me entr� el pique sano...

Bueno, pues son demasiadas combinaciones de par�ntesis y el programa ser�a muy lento por lo que decid� de aquella que se pod�an evitar ciertas combinaciones repetitivas de par�ntesis y decid� usar s�lo dos par�ntesis y luego pasar el resultado a otra funci�n que probar�a otros dos y as� en unos treinta y dos pasos tan s�lo habr�a explorado todas las posibilidades. Luego cuando el bucle que combina los n�meros moviese estos hasta adoptar la posici�n espejo de los actuales, entonces el mismo bucle de par�ntesis explorar�a los que me he dejado en esta pasada.
Un ejemplo lo aclara:
Con 1 + 2 - 3 * 4 + 5 + 6 mi programa hace dos c�lculos:
(1 + 2) - 3 * 4 + 5 + 6 = a - 3 * 4 + 5 + 6 (donde calculo "a" que es 1+2)
y
1 + (2 - 3) * 4 + 5 + 6 = 1 + a * 4 + 5 + 6 (donde vuelvo a calcular "a" tan s�lo)

Ahora paso cada una de las dos f�rmulas de arriba a otra funci�n que vuelve a calcular tan s�lo esos dos par�ntesis y luego le pasa las dos f�rmulas resultantes a otra funci�n que vuelve a hacer lo mismo hasta que la �ltima comprueba si se ha encontrado el resultado con lo que se acabar�a el programa.
O sea, ahora
a - 3 * 4 + 5 + 6 es 3 - 3 * 4 + 5 + 6 y se le pasa a una funci�n que calcula:
(3 - 3) * 4 + 5 + 6 = b * 4 + 5 + 6
y
3 - (3 * 4) + 5 + 6 = 3 - b + 5 + 6

y lo mismo con 1 + a * 4 + 5 + 6
y as� hasta acabar todo este "bucle de par�ntesis" que como ves no es un verdadero bucle del tipo

for(i=0; i< tal valor; i++)
{ ir cambiando aqu� los par�ntesis e ir mirando si da el exacto que estamos buscando
}

sino que s�lo exploro una parte de los par�ntesis posibles. La raz�n por la que se puede explorar esta peque�a parte de par�ntesis es porque luego cuando el programa calcule el inverso, (el inverso de 1 + 2 - 3 * 4 + 5 + 6 ser�a 6 + 5 + 4 * 3 - 2 + 1 ) el mismo "bucle de par�ntesis" explora los par�ntesis que me hab�an faltado por mirar en la primera pasada. O al menos a esa conclusi�n llegu� cuando hice el programa y lo di por bueno y ganaba un mont�n de velocidad que de aquella ten�a un 386 y en vez de a�os pod�a resolver el problema en unas cuantas horas... :-)

Bueno, y te respondo ahora que ya conoces un poco m�s del asunto:
Me ha escrito Alejandro (visita de nuevo members.xoom.com/bao y dale a actualizar para asegurarte de que cargas una versi�n nueva y no la de la cach� del disco duro) y creo que ha dado con la soluci�n del asunto. Creo que el truco est� en arreglar el �rbol de b�squeda de forma que quede ordenada. Esto se consigue cambiando el orden de los bucles, poniendo el de los par�ntesis como el m�s externo ( y ahora usando un for(;;) de verdad pues ya no vale el atajo que te he explicado arriba) y elegir tambien el orden correcto para cambiar los signos que en vez de + - * / que yo usaba, el correcto es / - + *
Un saludo Jose. Gracias por tu inter�s.

M�sica de fondo (Microsoft Internet Explorer 4): "Molotov Cocktail Party" de Molotov