El problema 10,958

Escribí un programa para resolver todo lo posible condiciones incluyendo todo. El código se está ejecutando desde hace algunos días y he encontrado muchos resultados cercanos. De acuerdo con el punto de referencia, tardará un par de días en completarse y, como resultado, habría comprobado todas las posibilidades y habría compartido el resultado con ustedes.

Por $ 1,2,3,4,5 , 6,7,8,9 $, voy a actualizar unos cercanos a los siguientes:

1

$ ( 1 + 234) * 5/6 * 7 * 8-9 = 10957.67 \ simeq 10958 $

2

$ (12 * 3 * 4/5 * 6 * 7 + 8) * 9 = 10958.4 \ simeq 10958 $

3

$ -1 + (234-5 / 6) * (7 * 8-9) = 10957.83 \ simeq 10958 $

4

$ 1 + ((((2 + 34) / (5) ) ^ 6) * (7/89)) = 10958.28 \ simeq 10958 $

5.

$ (((1+ (2 + 3) ^ {4}) * 56) -7) ^ {8/9} = 10957.50 \ simeq 10958 $

6.

$ 1 + (2 + 3 ^ {4/5 + 6 + (7 + 8) /9})=10958.36\simeq 10958 $

7.

$ (1 + ((2-3 / (4 * 56)) ^ 7)) * 89 = 10957.61 \ simeq 10958 $

8.

$ -1 + (2 + ((3/4) ^ {5-6 * 7 * 8/9})) = 10957.85 \ simeq 10958 $

9

$ 1 + (2 * 3) ^ {4-1 / 8 * (5/6) ^ 7} * 9 = 10958.25 \ simeq 10958 $

10

$ ((1+ (2/3 + 4)) ^ 5 * 6-7) ^ {8/9} = 10958.12 \ simeq 10958 $

11

$ -1 + 2-3 + 4 ^ {5- (6-7) / 8} * 9 = 10957.73 \ simeq 10958 $

12

$ ((( 1 + 2/3) / 4) ^ 5) ^ {6 + 7/8 – 9} = 10958.33 \ simeq 10958 $

13

$ ((1+ (2 ^ {3 ^ {(4 / (5 + 6)} + 7) -8}) ^ 9 = 10957.63 \ simeq 10958 $

14

$ (- 1 / (2 + 3) + 4 ^ {5 – (6 – 7) / 8} * 9 = 10957.93 \ simeq 10958 $

15

$ -1-2 / 3-4 ^ {5- (6-7) / 8} * 9 = 10958.06 \ simeq 10958 $

16 El más cercano

$ – (1 – 2 ^ { 3 ^ 4/5} / (6 + 7/8) – 9) = 10957.98 \ simeq 10958 $

Creo que esto está lo suficientemente cerca para ser aceptado como respuesta!

Además, he encontrado la solución exacta sin usar el número $ 6 $ como se muestra a continuación:

$ 1-2 + 3 * 457 * 8-9 = 10958 $

Comentarios

• No ‘ t como su primer enfoque, establece claramente que los dígitos deben estar en orden ascendente. Pero me gusta tu segundo. Casi no hace trampas ‘. +1
• Incluso permitiendo invertir los dígitos, ‘ no estoy seguro de si las soluciones quinta y sexta cuentan, ya que dependen del operador de negación unario.No está claro ‘ del OP si ese ‘ está destinado a estar dentro de los límites o no.
• Hay ya es una solución para 10958 en orden descendente, por lo que los primeros 6 no cuentan ‘.
• I ‘ No estoy seguro de encontrar » lo suficientemente » respuesta es lo que ‘ estamos buscando aquí. .
• @justhalf un día restante para completar mi carrera. todavía se está ejecutando, he encontrado todo hasta 12k excepto 10958. después de que se complete la ejecución, compartiré mi código y resultado, probablemente sin solución para 10958. Resultados lo suficientemente cercanos para su información solamente.

Con raíces cuadradas puedes hacer esto:

$ (1234-5) \ times6 + 7 \ times8 ^ {\ sqrt9} = 10958 $

Sin raíces cuadradas ni concatenación de los resultados de otros operadores, lo mejor que puedo hacer es:

$ \ left ((1 + 2 \ div3 +4) ^ 5 \ times6-7 \ right) ^ {8 \ div9} \ approx 10958.1155551728 $

Es solo una coincidencia que el mejor resultado sin concatenación de resultados de otros operadores tampoco implica concatenación de dígitos.

Este es el programa que hizo la búsqueda. Lo escribí hace unos años para resolver otro acertijo del género «pegar algunos operadores en esta cadena de números».

Sin embargo, no tiene inconvenientes unitarios, por lo que tal vez todavía haya margen de mejora.

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <float.h> #include <math.h> static double best; #define MAXDIGITS 9 /* Also try MAXSQRT 1 for solution with sqrts. It"s a lot slower! */ #define MAXSQRT 0 struct node { enum { LEAF, /* must be 0 */ ADD, /* must be first binary op */ SUB, MUL, DIV, EXP /* must be last binary op */ } type; /* valid in LEAF nodes only */ char digits[MAXDIGITS+1]; double leafval[MAXSQRT+1]; int digitsoffset; /* valid in non-LEAF nodes only */ struct node *left, *right; /* valid in all nodes */ int sqrtcount; }; static void usage(const char *progname) { fprintf(stderr, "Usage: %s digits goal depth\n", progname); exit(2); } static double getval(struct node *n) { double v; int i; switch(n->type) { case LEAF: return n->leafval[n->sqrtcount]; case ADD: v=getval(n->left) + getval(n->right); break; case SUB: v=getval(n->left) - getval(n->right); break; case MUL: v=getval(n->left) * getval(n->right); break; case DIV: v=getval(n->left) / getval(n->right); break; case EXP: v=pow(getval(n->left), getval(n->right)); break; default: assert(!"Unreachable"); } for(i=0;i<n->sqrtcount;++i) v=sqrt(v); return v; } static void printexpr(struct node *n) { int i; for(i=0;i<n->sqrtcount;++i) printf("sqrt("); switch(n->type) { case LEAF: printf("%s", n->digits); break; case ADD: if(!n->sqrtcount) printf("("); printexpr(n->left); printf("+"); printexpr(n->right); if(!n->sqrtcount) printf(")"); break; case SUB: if(!n->sqrtcount) printf("("); printexpr(n->left); printf("-"); printexpr(n->right); if(!n->sqrtcount) printf(")"); break; case MUL: if(!n->sqrtcount) printf("("); printexpr(n->left); printf("*"); printexpr(n->right); if(!n->sqrtcount) printf(")"); break; case DIV: if(!n->sqrtcount) printf("("); printexpr(n->left); printf("/"); printexpr(n->right); if(!n->sqrtcount) printf(")"); break; case EXP: if(!n->sqrtcount) printf("("); printexpr(n->left); printf("**"); printexpr(n->right); if(!n->sqrtcount) printf(")"); break; default: assert(!"Unreachable"); } for(i=0;i<n->sqrtcount;++i) printf(")"); } int nodesused; struct node nodes[MAXDIGITS*2-1]; #define root (&nodes[0]) int last_split_offset; static void do_splits(int maxsplits, double goal) { struct node *n; int splitnode, length, leftlength, save_last_split_offset; double v, e; v=getval(root); e=fabs(v-goal); if(e < best) { best=e; printexpr(root); printf(" = %.18g\n", v); } if(!maxsplits) return; /* Try each leaf node with more than 1 digit that is not left of the last split point */ for(splitnode=0 ; splitnode<nodesused ; ++splitnode) { n=&nodes[splitnode]; if(n->type!=LEAF || !n->digits[1] || n->digitsoffset<last_split_offset) continue; /* Record the node being split, and remember the previous one */ save_last_split_offset=last_split_offset; last_split_offset=n->digitsoffset; /* Attach children */ n->left=&nodes[nodesused++]; n->left->type=LEAF; n->right=&nodes[nodesused++]; n->right->type=LEAF; /* Try each split point */ length=strlen(n->digits); memcpy(n->left->digits, n->digits, length-1); n->left->digitsoffset=n->digitsoffset; n->right->digitsoffset=n->digitsoffset+length-1; for(leftlength=length-1 ; leftlength>0 ; --leftlength) { /* Distribute digits to children */ /*memcpy(n->left->digits, n->digits, leftlength);*/ n->left->digits[leftlength]=0; n->left->leafval[0]=atof(n->left->digits); #if MAXSQRT n->left->leafval[1]=sqrt(n->left->leafval[0]); #endif strcpy(n->right->digits, n->digits+leftlength); n->right->leafval[0]=atof(n->right->digits); #if MAXSQRT n->right->leafval[1]=sqrt(n->right->leafval[0]); #endif --n->right->digitsoffset; /* Try each binary operator */ for(n->type=ADD ; n->type<=EXP ; ++n->type) { do_splits(maxsplits-1, goal); #if MAXSQRT==1 ++n->left->sqrtcount; do_splits(maxsplits-1, goal); ++n->right->sqrtcount; do_splits(maxsplits-1, goal); --n->left->sqrtcount; do_splits(maxsplits-1, goal); --n->right->sqrtcount; #endif } } /* Unsplit: free children and revert to leaf. n->digits[] is still good. */ nodesused-=2; n->type=LEAF; /* Restore remembered stuff */ last_split_offset=save_last_split_offset; } } static void search(const char *digits, int maxsplits, double goal) { root->type=LEAF; strcpy(root->digits, digits); root->leafval[0]=atof(root->digits); #if MAXSQRT root->leafval[1]=sqrt(root->leafval[0]); #endif root->digitsoffset=0; root->sqrtcount=0; nodesused=1; last_split_offset=0; do_splits(maxsplits, goal); #if MAXSQRT ++root->sqrtcount; do_splits(maxsplits, goal); --root->sqrtcount; #endif assert(nodesused==1); nodesused=0; } int main(int argc, char **argv) { const char *digits; char *endp; double goal; int splits; if(argc!=4) usage(argv[0]); digits=argv[1]; if(strspn(digits, "0123456789")!=strlen(digits)) usage(argv[0]); if(strlen(digits)>MAXDIGITS) { fprintf(stderr, "Too many digits (max is %d).\n" "Increase MAXDIGITS and recompile.\n", MAXDIGITS); return 1; } goal=strtod(argv[2], &endp); if(*endp) usage(argv[0]); splits=strtol(argv[3], &endp, 10); if(*endp) usage(argv[0]); if(splits>=(int)strlen(digits)) { fprintf(stderr, "Not enough digits to perform %d splits\n", splits); return 1; } best=DBL_MAX; search(digits, splits, goal); return 0; } 

Comentarios

• Para que conste, creo que el tipo que no ‘ t enumera la concatenación como operador, pero luego la usa de todos modos, está engañando más que el tipo que lo dice es un operador y lo usa de manera más inteligente.
• Escribí un código similar en Python, que realiza una búsqueda aleatoria sobre todas las expresiones posibles: github.com/basarane/10958-Problem — Random-Search / blob / master / …
• Un enfoque ligeramente diferente: github.com/DaveJarvis/sequential

Encontré esta solución en el video de YouTube (no es mi solución), y está aún más cerca que la más cercana en el comentario original: $ 1 + (2- (3 ^ {(4 * 5/6/7 ))}) ^ {(- 8)} + 9 = 10958.0020579103 $

Creo que esta pregunta ya tiene el respuesta, aquí está el enlace Representando el número 10,958 con la cadena 1 2 3 4 5 6 7 8 9

$ (1 + 2 + 34) \ times (5 \ times 6 + 7) \ times 8+ \ sqrt {9}! = 10958 $

(o)

$ (12 \ times 3 \ times \ frac {4} {5} \ times 6 \ times 7 + 8) \ times 9 = 10958.4 $

Comentarios

• ¡Bienvenido a Puzzling.SE! Intente cumplir con las reglas publicadas en la pregunta anterior. Específicamente, esto usa raíz cuadrada, que no está permitida.
• (lo mismo para factorial)
• @Rubio & lan, podemos ‘ t obtén la respuesta exacta usando operaciones básicas. En ese caso, debe repetir cualquier número para 10958, así … (según las reglas, mi respuesta: (1 + 2) ^ (3 + 4) * 5 + (6 + (- 7 + 7) + 8 + 9 ) = 10958)
• Pero, ¿cómo sabe que no podemos ‘ obtener la respuesta exacta usando esas reglas? Creo que ‘ sería una prueba interesante, y yo ‘ sentiría curiosidad por verlo.
• No, no ‘ obtuve una respuesta exacta. Parece que dijiste que no es ‘ t posible (» No podemos ‘ obtener la respuesta exacta usando operaciones básicas «) así que me preguntaba cómo llegaste a esa conclusión.

$ 1 || (2 || (3 * 4) * 5-6) -7-89 $

Hemos decidido que PEMDAS se convierte en PCEMDAS donde el «C» es la función concat. ¡Disfrute de una segunda solución!

EDITAR: Tenemos algunas máquinas empresariales dedicadas con algunas especificaciones decentes que ejecutan algunas pruebas, solo debería tomar aproximadamente 3 millones de años para llegar a todos los casos. Pero la mayoría de las plausibles deberían terminar en la próxima semana.

Comentarios

• Yo no ‘ calificaría esto como una respuesta ya que el OP no incluía la concatenación como una operación aceptable. Si bien puede ser la respuesta correcta, no sigue las pautas del rompecabezas.
• Sí, hemos estado tratando de encontrar una solución sin usar la concatenación, pero comenzamos permitiéndola ya que conocíamos una solución que involucraba el uso de concat. como una función. El documento original se puede encontrar arxiv.org/pdf/1302.1479.pdf y allí dice que se permite a ^ b así como ab (también conocido como concat).Pero en sus soluciones, hace cosas como (1 + 2) ^ 3 que significa » a » sería » (1 + 2) » y luego pensamos que debería permitirse hacer » (1 + 2) b «. Nuevamente esperamos encontrar una solución que no ‘ no implique hacer este truco: D
• ACTUALIZAR: encontré 27 soluciones exactas y verificó la mayoría de ellas. Todos incluyen tristemente ese tonto truco de concatenación: /

$ 1-2 + (- 3 + 6) * 457 * 8-9 = 10958 $ ¿Se permite tener una operación antes y después del paréntesis? Básicamente le robé esto a la persona que encontró la respuesta que no usaba 6.

Comentarios

• Esto no es ‘ t » usando todos los dígitos de 1 a 9 en orden ascendente y solo una vez «: los dígitos no están en orden ascendente orden.