Le problème 10 958

Jai écrit un programme pour résoudre tout ce qui est possible conditions comprenant tout. Le code fonctionne depuis quelques jours maintenant et jai trouvé beaucoup de résultats proches. Selon le benchmark, cela prendra quelques jours et jaurais donc vérifié toutes les possibilités et partager le résultat avec vous.

Pour 1,2,3,4,5 $ , 6,7,8,9 $, je vais mettre à jour les plus proches ci-dessous:

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 Le plus proche

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

Je pense que cest assez proche pour être accepté comme réponse!

De plus, jai trouvé une solution exacte sans utiliser le nombre $ 6 $ comme ci-dessous:

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

Commentaires

• Je ne ‘ t comme votre première approche, il indique clairement que les chiffres doivent être dans lordre croissant. Mais jaime bien votre deuxième. Il ‘ ne triche presque pas. +1
• Même en tenant compte de linversion des chiffres, je ‘ ne sais pas si les 5ème et 6ème solutions comptent car elles reposent sur lopérateur de négation unaire.Il ‘ nest pas clair du PO si ce ‘ est censé être dans les limites ou non.
• Là est déjà une solution pour 10958 par ordre décroissant, donc les 6 premiers don ‘ t count.
• I ‘ Je ne suis pas sûr de trouver  » assez près  » La réponse est ce que nous ‘ recherchons ici .
• @Il reste une demi-journée pour terminer ma course. il est toujours en cours dexécution, jai tout trouvé jusquà 12k sauf 10958. Une fois la course terminée, je partagerai mon code et mon résultat, ne disant probablement aucune solution pour 10958. Fermer suffisamment de résultats pour vos informations uniquement.

Avec des racines carrées, vous pouvez faire ceci:

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

Sans racines carrées ni concaténation des résultats dautres opérateurs, le mieux que je puisse faire est:

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

Cest juste une coïncidence que le meilleur résultat sans concaténation des résultats dautres opérateurs nimplique pas non plus de concaténation de chiffres.

Cest le programme qui a fait la recherche. Je lai écrit il y a quelques années pour résoudre un autre casse-tête du genre « coller quelques opérateurs dans cette chaîne de nombres ».

Cela ne fait pas de moins unaire, alors peut-être quil y a encore place à amélioration.

#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; } 

Commentaires

• Pour mémoire, je pense que le gars qui ne ‘ t liste la concaténation comme opérateur, mais qui lutilise quand même, triche plus que celui qui le dit est un opérateur et lutilise plus intelligemment.
• Jai écrit un code similaire en python, qui effectue une recherche aléatoire sur toutes les expressions possibles: github.com/basarane/10958-Problem — Random-Search / blob / master / …
• Une approche légèrement différente: github.com/DaveJarvis/sequential

Jai trouvé cette solution sur la vidéo YouTube (pas ma solution), et elle est encore plus proche que la plus proche dans le commentaire original: $ 1 + (2- (3 ^ {(4 * 5/6/7 ))}) ^ {(- 8)} + 9 = 10958.0020579103 $

Je crois que cette question a déjà le réponse, voici le lien Rendu du nombre 10,958 avec la chaîne 1 2 3 4 5 6 7 8 9

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

(ou)

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

Commentaires

• Bienvenue sur Puzzling.SE! Veuillez essayer de respecter les règles affichées dans la question ci-dessus. Plus précisément, cela utilise la racine carrée, ce qui nest pas autorisé.
• (idem pour factorielle)
• @Rubio & lan, nous pouvons ‘ t obtenir la réponse exacte en utilisant des opérations de base. Dans ce cas, vous devez répéter nimporte quel nombre pour 10958, comme ceci .. (basé sur les règles ma réponse: (1 + 2) ^ (3 + 4) * 5 + (6 + (- 7 + 7) + 8 + 9 ) = 10958)
• Mais comment savez-vous que nous ne pouvons ‘ obtenir la réponse exacte en utilisant ces règles? Cela ‘ serait une preuve intéressante, je pense, et je ‘ serais curieux de le voir.
• Non, je nai ‘ pas obtenu de réponse exacte. On dirait que vous avez dit que ce n’est pas ‘ t possible ( » Nous ne pouvons ‘ obtenir la réponse exacte en utilisant les opérations de base « ) donc je me demandais comment vous en êtes arrivé à cette conclusion.

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

Nous avons décidé que PEMDAS devient PCEMDAS où le « C » est la fonction concat. Profitez dune deuxième solution!

EDIT: Nous avons des machines dentreprise dédicaces avec des spécifications décentes exécutant des tests, cela ne devrait prendre quenviron 3 millions dannées pour répondre à tous les cas. Mais la majorité des plausibles devraient se terminer la semaine prochaine.

Commentaires

• Je ‘ t qualifierais cela comme une réponse car le PO nincluait pas la concaténation comme une opération acceptable. Bien que ce soit peut-être la bonne réponse, elle ne suit pas les directives du puzzle.
• Oui, nous avons essayé de trouver une solution sans utiliser la concaténation, mais nous avons commencé par lautoriser car nous connaissions une solution impliquant lutilisation de concat en tant que fonction. Le papier original peut être trouvé arxiv.org/pdf/1302.1479.pdf et là il dit que a ^ b est autorisé aussi bien que ab (aka concat).Mais dans ses solutions, il fait des choses comme (1 + 2) ^ 3 signifiant  » a  » serait  » (1 + 2)  » et après cela nous avons pensé quil devrait être permis de faire  » (1 + 2) b « . Encore une fois, nous espérons trouver une solution qui nimplique pas ‘ de faire cette astuce: D
• UPDATE: a trouvé 27 solutions exactes, et vérifié la plupart dentre elles. Tous incluent malheureusement cette astuce de concaténation stupide: /

1-2 $ + (- 3 + 6) * 457 * 8-9 = 10958 $ Est-il permis davoir une opération avant et après le crochet? Jai essentiellement volé ceci à la personne qui a trouvé la réponse qui na pas utilisé 6.

Commentaires

• Ceci nest pas ‘ t  » en utilisant les 1 à 9 chiffres dans lordre croissant et une seule fois  » – les chiffres ne sont pas en ordre croissant commande.