Problema 10.958

Am scris un program pentru a rezolva tot posibilul condiții inclusiv totul. Codul rulează de câteva zile și am găsit o mulțime de rezultate apropiate. Potrivit valorii de referință, va dura câteva zile și, prin urmare, aș fi verificat fiecare posibilitate și aș împărtăși rezultatul cu voi.

Pentru 1,2,3,4,5 USD , 6,7,8,9 $, voi actualiza cele apropiate la cele de mai jos:

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 Cel mai apropiat

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

Cred că acest lucru este suficient de aproape pentru a fi acceptat ca răspuns!

Mai mult decât atât, am găsit o soluție exactă fără a utiliza numărul $ 6 $ ca mai jos:

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

Comentarii

• Nu ‘ nu îți place prima abordare, afirmă clar că cifrele trebuie să fie în ordine crescătoare. Dar îmi place al doilea. ‘ aproape că nu înșală. +1
• Chiar și permițând inversarea cifrelor, nu știu dacă soluțiile 5 și 6 contează pe măsură ce se bazează pe operatorul de negare unitar.’ nu este clar din PO dacă ‘ este destinat să fie sau nu în limitele legale.
• este deja o soluție pentru 10958 în ordine descrescătoare, deci primele 6 nu contează ‘.
• I ‘ Nu sunt sigur că găsim ” suficient de aproape ” răspunsul este ceea ce căutăm aici ‘ .
• A rămas doar o jumătate de zi pentru a-mi finaliza alergarea. este încă în desfășurare, am găsit totul până la 12k, cu excepția 10958. După finalizarea rulării, voi împărtăși codul și rezultatul, probabil că nu voi spune nicio soluție pentru 10958. Închideți suficient rezultate numai pentru informațiile dvs. ur.

Cu rădăcini pătrate puteți face acest lucru:

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

Fără rădăcini pătrate sau concatenarea rezultatelor altor operatori, cel mai bun lucru pe care îl pot face este:

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

Este doar o coincidență faptul că cel mai bun rezultat fără concatenarea rezultatelor altor operatori nu implică nici o concatenare de cifre.

Acesta este programul care a făcut căutarea. L-am scris acum câțiva ani pentru a rezolva un alt puzzle din genul „lipiți niște operatori în acest șir de numere”.

Totuși, nu face unus minus, deci poate că mai este loc de îmbunătățire.

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

Comentarii

• Pentru înregistrare, cred că tipul care nu ‘ listează concatenarea ca operator, dar îl folosește oricum, înșală mai mult decât tipul care o spune este un operator și îl folosește mai inteligent.
• Am scris un cod similar în python, care efectuează căutări aleatorii peste toate expresiile posibile: github.com/basarane/10958-Problem — Random-Search / blob / master / …
• O abordare ușor diferită: github.com/DaveJarvis/sequential

Am găsit această soluție pe videoclipul YouTube (nu soluția mea) și este chiar mai aproape decât cea mai apropiată din comentariul original: $ 1 + (2- (3 ^ {(4 * 5/6/7 ))}) ^ {(- 8)} + 9 = 10958.0020579103 $

Cred că această întrebare are deja răspuns, aici este linkul Redarea numărului 10.958 cu șirul 1 2 3 4 5 6 7 8 9

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

(sau)

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

Comentarii

• Bine ați venit la Puzzling.SE! Vă rugăm să încercați să respectați regulile postate în întrebarea de mai sus. Mai exact, acesta folosește rădăcină pătrată, care nu este permisă.
• (același lucru pentru factorial)
• @Rubio & lan, Putem ‘ t obțineți răspunsul exact utilizând operațiuni de bază. În acest caz, trebuie să repetați orice număr pentru 10958, așa .. (pe baza regulilor răspunsul meu: (1 + 2) ^ (3 + 4) * 5 + (6 + (- 7 + 7) + 8 + 9 ) = 10958)
• Dar de unde știi că putem ‘ să obținem răspunsul exact folosind aceste reguli? Cred că ‘ ar fi o dovadă interesantă, și ‘ aș fi curios să o văd.
• Nu, nu am primit ‘ un răspuns exact. Se pare că ai spus că nu este ‘ t posibil (” Putem ‘ nu obține răspunsul exact utilizând operațiuni de bază „), așa că mă întrebam cum ați ajuns la acea concluzie.

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

Am decis că PEMDAS devine PCEMDAS unde „C” este funcția concat. Bucurați-vă de o a doua soluție!

EDIT: Avem câteva mașini dedicate întreprinderii, cu unele specificații decente care rulează unele teste, ar trebui să dureze aproximativ 3 milioane de ani pentru a atinge toate cazurile. Dar majoritatea celor plauzibile ar trebui să termine în săptămâna următoare.

Comentarii

• Nu aș califica acest lucru drept un răspuns, deoarece PO nu a inclus concatenarea ca o operațiune acceptabilă. Deși poate fi răspunsul corect, nu respectă instrucțiunile puzzle-ului.
• Da, am încercat să găsim o soluție fără a utiliza concatenarea, dar am început permițându-l, deoarece știam o soluție care presupunea utilizarea concat. ca o funcție. Lucrarea originală poate fi găsită arxiv.org/pdf/1302.1479.pdf și acolo spune că a ^ b este permis, precum și ab (aka concat).Dar în soluțiile sale face lucruri precum (1 + 2) ^ 3, adică ” a ” ar fi ” (1 + 2) ” și după aceea am considerat că ar trebui să li se permită să facă ” (1 + 2) b „. Din nou, sperăm să găsim o soluție care nu ‘ nu implică realizarea acestui truc: D
• UPDATE: a găsit 27 de soluții exacte și le-am verificat pe cele mai multe. Toate includ acel truc prost de concatenare din păcate: /

$ 1-2 + (- 3 + 6) * 457 * 8-9 = 10958 $ Este permisă o operație înainte și după paranteză? Practic, am furat acest lucru de la persoana care a găsit răspunsul care nu „a folosit 6.

Comentarii

• Acesta nu este ‘ t ” folosind toate 1-9 cifre în ordine crescătoare și o singură dată ” – cifrele nu sunt în ordine crescătoare ordinea.