Tema destacado: Entra al canal IRC oficial de #elhacker.net
 Autor
|
Tema: Programa que sepa los signos que hay que poner en una igualdad (Leído 1,023 veces)
|
javirk
 Desconectado
Mensajes: 73
|
Hola, pues me gustaría hacer un programa que al que tú le dijeras 3 números y lo que tienen que dar las cuentas entre ellos y que te diera los signos, del tipo:
Números:
7
2
1
Resultado:
8
Y que el programa te dijera: 7+2-1=8
O algo parecido. Había pensando en poner Ifs con todas las condicionales, pero son muchas y no me parece lo más adecuado, ¿se os ocurre alguna otra forma?
El programa lo estoy haciendo en C++, por eso lo pongo aquí.
Un saludo y gracias
|
|
|
|
|
En línea
|
|
|
|
javirk
Desconectado
Mensajes: 73
|
Ok, he encontrado que se puede hacer con "backtracking", pero no sé cómo funciona eso, y eso que he leído bastante al respecto...
|
|
|
|
|
En línea
|
|
|
|
eleon
Desconectado
Mensajes: 56
|
Podrías explicarte mejor por favor, ¿estás diciendo que el usuario introduce los operandos y las operaciones que quieres que haga con ellos (como una calculadora)?.
No está permitido hacer los ejercicios, sin embargo si te explicas bien se te puede orientar acerca de por dónde tirar.
|
|
|
|
|
En línea
|
|
|
|
raul338
Desconectado
Mensajes: 2.371
La sonrisa es la mejor forma de afrontar las cosas
|
Bactracking ya es avanzado de por si, se podria decir que es una inteligencia aplicada  Lo que si puedes hacer es el tipico "fuerza bruta", o sea, con un for ir cambiando todo tipo, sumar, restar y asi 1º Vuelta Suma 1º Suma 2º Suma 3º Es correcto? No? Entonces cambio el primero por una resta 2º Vuelta Suma 1º Resta 2º Suma 3º y asi con todas las operaciones, claro, tarda mas exponecialmente segun los numeros que haya, pero seria la forma mas "simple" de hacerlo |
|
|
|
|
En línea
|
|
|
|
javirk
Desconectado
Mensajes: 73
|
Podrías explicarte mejor por favor, ¿estás diciendo que el usuario introduce los operandos y las operaciones que quieres que haga con ellos (como una calculadora)?.
No está permitido hacer los ejercicios, sin embargo si te explicas bien se te puede orientar acerca de por dónde tirar.
El usuario sólo introduce los números, el programa da los signos. @raul338 No entiendo cómo podría hacer eso con un for... Muchas gracias por la ayuda!
|
|
|
|
|
En línea
|
|
|
|
|
ghastlyX
|
Si la cantidad de números puede ser arbitraria, tienes que hacer un backtracking. Si la cantidad de números es fija, puedes simular el backtracking a base de bucles. En todo caso, si tienes n números, la complejidad resultante es O(2n).
Puedes también hacer una dinámica, si los números y el resultado están acotados será mucho más eficiente.
|
|
|
|
|
En línea
|
|
|
|
Xandrete
Desconectado
Mensajes: 195
|
¿División también? ¿Producto también?
En realidad, el ejercicio tiene un poco más de "cosa" si admites la división como posible operador, porque has de tener cuidado con no dividir nada entre 0.
Hay otro detalle: el de la jerarquía de las operaciones. Tanto si admites el producto como la división, has de tener en consideración que cualquiera de estas dos operaciones tiene prioridad frente a la suma y la resta.
Si no estabas considerando ni el producto ni la multiplicación, no hay ningún problema.
Coincido con las personas que han comentado que para este caso viene un poco grande el backtracking (no vale la pena aplicarlo para decidir tan solo dos operadores). Para este caso, bastaría con dos bucles for anidados. Inténtalo, es bastante fácil. Si aún así no te sale, arroja algo de código y así te ayudamos un poco más.
|
|
|
|
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 604
Cuando me afeito, recuerdo porque me dejo barba.
|
¡Buenas! Esto me suena al cifras y letras que hubo en tiempos en el foro libre en tiempos. El programa no es dificil utilizando al goritmos recursivos (si, hice trampas... XD) Aqui te dejo el codigo que hice, si no entiendes algo avisa. En este caso he utilizado un vector estatico con MAX_CIFRAS elementos. txtresultado tambien tiene fijado el numero de caracteres (el codigo lo hice un poco al vuelo). Si quieres que tu programa funciones bien tendras que corregir esos detalles utilizando memoria dinamica, ya que pueden se fuente de errores. Tendras que darle una dimension "grande" a txtresultado si quieres asegurarte de que no te pasas del final del bloque... /*
* si se puede resolver devuelve 1, sino 0
*
* guarda en txtresultado las operaciones que se van realizando para llegar al resultado
*/
int resolver(int *cifras,int ncifras,int resultado,char *txtresultado)
{
int i,j,operador1,operador2;
/* si el numero de datos restantes es <= 1, no se pueden realizar operaciones */
if(ncifras <= 1)
return 0; /* devolvemos falso */
/* emparejamos los numeros de 2 en 2 */
for(i=0 ; i < ncifras ; i++)
{
for(j=0 ; j < ncifras ; j++)
{
operador1 = cifras[i];
operador2 = cifras[j];
if(i!=j) /* un numero no puede operar consigo mismo */
{
if(i < j) /*suma y producto son conmutativas y se realizan solo con i<j */
{
/*
* operamos y guardamos la operacion en la cadena que contiene el texto con
* el resultado
*/
operacion(cifras,i,j,'+',txtresultado);
/* si tras la operacion hemos hallada el resultado */
if(cifras[i] == resultado)
return 1; /* devolvemos verdadero */
/* en este punto, no se ha hallado ninguna solucion
* por lo tanto, buscamos un resultado, con los datos restantes
*/
if(resolver(cifras,ncifras-1,resultado,txtresultado + strlen(txtresultado)))
return 1; /* si lo solucionamos, devolvemos verdadero */
/* si no lo solucionamos, resauramos los valores de los parametros */
restaurar(cifras,i,j,operador1,operador2,txtresultado);
/* y pasamos a la siguiente operacion */
operacion(cifras,i,j,'*',txtresultado);
if(cifras[i] == resultado)
return 1;
if(resolver(cifras,ncifras-1,resultado,txtresultado + strlen(txtresultado)))
return 1;
restaurar(cifras,i,j,operador1,operador2,txtresultado);
}
//resta y division no conmutativas, asi que las realizamos con todos los pares
operacion(cifras,i,j,'-',txtresultado);
if(i < j)
{
if(cifras[i] == resultado)
return 1;
}
else
if(cifras[j] == resultado)
return 1;
if(resolver(cifras,ncifras-1,resultado,txtresultado + strlen(txtresultado)))
return 1;
restaurar(cifras,i,j,operador1,operador2,txtresultado);
operacion(cifras,i,j,'/',txtresultado);
if(i < j)
{
if(cifras[i] == resultado)
return 1;
}
else
if(cifras[j] == resultado)
return 1;
if(resolver(cifras,ncifras-1,resultado,txtresultado + strlen(txtresultado)))
return 1;
restaurar(cifras,i,j,operador1,operador2,txtresultado);
}
}
}
return 0;
}
void restaurar(int *cifras,int i,int j,int operador1,int operador2, char *txtresultado)
{
/* movemos los datos a partir del indice mayor una posicion a la derecha */
if(i < j)
memmove(cifras + j + 1, cifras + j, sizeof(int) * (MAX_NUMEROS - j - 1));
else
memmove(cifras + i + 1, cifras + i, sizeof(int) * (MAX_NUMEROS - i - 1));
/* restauramos los valores originales que habia en el vector */
cifras[i] = operador1;
cifras[j] = operador2;
/* y eliminamos la informacion de la operacion de la cadena con la solucion */
*txtresultado = '\0';
return;
}
void operacion(int *cifras,int i,int j,char op,char *txtresultado)
{
/* guardamos en min{i,j} el bresultado de la operacion */
switch(op)
{
case '+':
sprintf(txtresultado,"%d + %d = %d\n",cifras[i],cifras[j],cifras[i]+cifras[j]);
cifras[i] += cifras[j];
break;
case '*':
sprintf(txtresultado,"%d * %d = %d\n",cifras[i],cifras[j],cifras[i]*cifras[j]);
cifras[i] *= cifras[j];
break;
case '-':
sprintf(txtresultado,"%d - %d = %d\n",cifras[i],cifras[j],cifras[i]-cifras[j]);
if(i < j)
cifras[i] -= cifras[j];
else
cifras[j] -= cifras[i];
break;
case '/':
if(cifras[j])
if(!(cifras[i] % cifras[j]))
{
sprintf(txtresultado,"%d / %d = %d\n",cifras[i],cifras[j],cifras[i]/cifras[j]);
if(i < j)
cifras[i] /= cifras[j];
else
cifras[j] /= cifras[i];
}
break;
}
/* y ahora desplazamos todos los valores a la derecha de max{i,j} una posicion a la izquierda */
if(i < j)
memmove(cifras + j,cifras + j + 1, sizeof(int) * (MAX_NUMEROS - j - 1));
else
memmove(cifras + i,cifras + i + 1, sizeof(int) * (MAX_NUMEROS - i - 1));
return;
}
Si encontrais errores o cambiais algo el codigo me gustaria poder echarle un ojo. ¡Saludos! |
|
|
|
« Última modificación: 4 Febrero 2012, 22:42 por do-while »
|
En línea
|
¡¡¡Feliz año nuevo!!!
|
|
|
|
ghastlyX
|
Antes no había leído que eran tres números. Ignora pues la parte de mi mensaje anterior donde hacía referencia a la solución para una cantidad arbitraria de números. Ya que tu problema es más sencillo, te dejo un código que he picado ahora para el caso general, suponiendo que los operadores son + o -, por si te interesa el tema para mirarlo. #include <iostream>
#include <vector>
using namespace std;
void imprime(vector<int>& v, int x) {
for (int i = 0; i < v.size(); ++i) {
if ((x >> i)&1) cout << "+";
else cout << "-";
cout << v[i];
}
cout << endl;
}
int main() {
//Cantidad de numeros, resultado
int n, m;
cin >> n >> m;
//Lectura de los numeros
vector<int> v(n);
for (int i = 0; i < n; ++i) cin >> v[i];
//Solucion
for (int i = 0; i < (1 << n); ++i) {
int res = 0;
for (int j = 0; j < n; ++j) {
if ((i >> j)&1) res += v[j];
else res -= v[j];
}
if (res == m) imprime(v, i);
}
} Es equivalente a una solución por backtracking, sólo que lo he hecho iterativo mediante máscaras de bits puesto que es mucho más corto y simple el código. |
|
|
|
|
En línea
|
|
|
|
Xandrete
Desconectado
Mensajes: 195
|
Bueno, ya que hay gente que ha puesto su código, me voy a animar yo también... Como ghastlyX ya lo hizo con bucles for anidados, voy a plantear una propuesta distinta. #include <iostream>
using namespace std;
int main() {
char comb[][2] = {{'-','-'},{'-','+'},{'+','-'},{'+','+'}};
int a,b,c,result;
cin >> a >> b >> c >> result;
for (int i = 0; i < 4; ++i) {
int res;
if (comb[i][0] == '-') res = a - b;
else res = a + b;
if (comb[i][1] == '-') res -= c;
else res += c;
if (res == result) cout << a << comb[i][0] << b << comb[i][1]
<< c << "=" << result << endl;
}
} Saludos |
|
|
|
|
En línea
|
|
|
|
javirk
Desconectado
Mensajes: 73
|
Hola, muchas gracias por vuestras respuestas, de verdad.
do-while, creo que tu solución se me queda algo grande, no sé ni por dónde empezar, pero muchas gracias, lo tendré que mirar más en detalle.
ghastlyX, aún no sé nada de vectores, pero parece que los entiendo más o menos al ver tu solución, muchas gracias.
Xandrete, creo que tu solución es la que más me interesa, posiblemente por ser la más corta, pero no me funciona cuando la compilo, es decir, que no me sale nada, y meto 4 números y sale del programa; lo mismo me pasa con la de ghastlyX, pero este no sale, simplemente no hace nada. ¿Por qué puede ser eso?
Bueno, a lo que iba, Xandrete, lo que no entiendo del tuyo es eso del "comb[][2]", ¿por qué dos corchetes?
Un saludo y gracias a todos.
|
|
|
|
|
En línea
|
|
|
|
Xandrete
Desconectado
Mensajes: 195
|
Hola, muchas gracias por vuestras respuestas, de verdad.
do-while, creo que tu solución se me queda algo grande, no sé ni por dónde empezar, pero muchas gracias, lo tendré que mirar más en detalle.
ghastlyX, aún no sé nada de vectores, pero parece que los entiendo más o menos al ver tu solución, muchas gracias.
Xandrete, creo que tu solución es la que más me interesa, posiblemente por ser la más corta, pero no me funciona cuando la compilo, es decir, que no me sale nada, y meto 4 números y sale del programa; lo mismo me pasa con la de ghastlyX, pero este no sale, simplemente no hace nada. ¿Por qué puede ser eso?
Bueno, a lo que iba, Xandrete, lo que no entiendo del tuyo es eso del "comb[][2]", ¿por qué dos corchetes?
Un saludo y gracias a todos.
¿Quizás sea porque no existe ninguna combinación de operadores que haga que se cumpla la igualdad? No he tenido ningún problema con el código que te he propuesto. Yo lo he compilado con las opciones -Wall, -Werror y -Wextra para asegurarme de que no había ni error ni warnings de ninguna clase (siempre compilo así) y lo he probado con la entrada que das como ejemplo y con otras. Con 7 2 1 8 la salida es: 7+2-1=8 Con 0 0 0 0 la salida es: 0-0-0=0 0+0-0=0 0-0+0=0 0+0+0=0 Con 1 1 1 1 la salida es 1+1-1=1 1-1+1=1 Y con 0 0 0 1 no se imprime nada (como ha de ser). ¿Por qué dos corchetes? Porque es un array de arrays de caracteres. O sea, una matriz o estructura de datos bidimensional. Se suelen declarar así, con un par de corchetes. Mírate bien el tema de los arrays. Otra manera. Con if's, tal y como habías pensado tú al principio: #include <iostream>
using namespace std;
int main() {
int a,b,c,result;
cin >> a >> b >> c >> result;
if (a-b-c == result)
cout << a << "-" << b << "-" << c << "=" << result << endl;
if (a-b+c == result)
cout << a << "-" << b << "+" << c << "=" << result << endl;
if (a+b-c == result)
cout << a << "+" << b << "-" << c << "=" << result << endl;
if (a+b+c == result)
cout << a << "+" << b << "+" << c << "=" << result << endl;
} Este último código si que es claro a más no poder. De todas formas, no nos has sacado de dudas aún acerca del número de signos que consideras. ¿Están la multiplicación y la división también incluidos? Todos estamos asumiendo que sólo te interesan sumas y restas. Saludos
|
|
|
|
|
En línea
|
|
|
|
|
ghastlyX
|
Si no te hace nada mi programa y no termina es porque no le pasarás correctamente la entrada. Si te fijas en lo que he dicho o en el código, verás que mi programa no trabaja con tres números, sino con los que tú quieras, lo he hecho para el caso general . El formato de la entrada es primero la cantidad de números que usarás (en tu caso sería 3), a continuación el resultado que buscas y luego los números que se deban usar (tantos como hayas indicado). Por ejemplo, para tu ejemplo sería: 3 8
7 2 1 Y la salida que produce es +7+2-1 Otro caso por ejemplo sería 5 8
7 2 1 1 1 Y su salida es +7+2+1-1-1
+7+2-1+1-1
+7+2-1-1+1 |
|
|
|
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 604
Cuando me afeito, recuerdo porque me dejo barba.
|
¡Buenas!
No se si el problema esta bien planteado. ¿Los numero hay que utilizarlos en el orden en el que se introducen, o se pueden reordenar?
Lo digo porque si se pueden reordenar, en principipo tendras 4 formas de poner los simbolos de suma y resta en los dos huecos que tienes, y 6 (3!) formas de reorganizar los tres numeros para buscar el resultado, en total 24 casos (que luego se quedan en menos, ya que la suma es conmutativa). Si estas en este ultimo caso, introducir todas las condiciones a mano es largo y bastante propenso a cometer errores...
¡Saludos!
Editado:
Si lo miras con mas detenimiento, solo tienes que variar los coeficientes de los elementos. +/-a, +/-b y +/-c y luego sumarlos, asi queda mas claro, ya que solo tendras que comprobar 8 casos y te olvidas de reordenar los elementos:
a+b+c
a+b-c
a-b+c
-a+b+c
a-b-c
-a+b-c
-a-b+c
-a-b-c
|
|
|
|
« Última modificación: 6 Febrero 2012, 01:53 por do-while »
|
En línea
|
¡¡¡Feliz año nuevo!!!
|
|
|
Xandrete
Desconectado
Mensajes: 195
|
¿Reordenar? Bueno, javirk no nos había planteado esa posibilidad.
Si fuera posible, lo que haría simplemente sería considerar un signo más (un - o + antes de la a) y me ahorraría reordenar, que es justo lo que propone do-while. En ese caso habría 23= 8 casos, tal y como nos sugiere. De todas formas, yo apuesto por la Navaja de Ockham y creo que el problema es la versión más sencilla de la que hemos planteado por aquí: sólo dos operadores (suma y resta) y sin posibilidad de reordenación. Y si no es así, que javirk nos dé el enunciado completo de su problema. No tiene sentido que especulemos mientras él no nos dice ni mu xD (javirk, no te mosquees, lo digo sin intención de ofender, a lo mejor no has podido responder aún por alguna razón >.<)
¡Saludos!
|
|
|
|
|
En línea
|
|
|
|
|
 |
