Problém 10 958 (Čeština)

Napsal jsem program, který vyřeší všechny možné podmínky včetně všeho. Kód běží už několik dní a našel jsem spoustu blízkých výsledků. Podle benchmarku to bude trvat pár dní a ve výsledku bych zkontroloval všechny možnosti a podělil se o výsledek s vámi.

Za 1,2,3,4,5 $ , 6,7,8,9 $, chystám se aktualizovat blízké následující:

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 Nejbližší

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

Domnívám se, že je to dost blízko na to, přijato jako odpověď!

Navíc jsem našel přesné řešení bez použití čísla $ 6 $, jak je uvedeno níže:

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

Komentáře

• Nemám ‚ Jako váš první přístup, jasně uvádí, že číslice musí být vzestupně. Ale líbí se mi tvoje druhá. ‚ téměř nepodvádí. +1
• I když dovolujeme obracet číslice, nejsem si ‚ jistý, zda se 5. a 6. řešení počítají, protože se spoléhají na unární operátor negace.‘ Z OP není jasné, zda to ‚ mělo být v mezích nebo ne.
• Tam je již řešením pro 10958 v sestupném pořadí, takže prvních 6 se nepočítá ‚ t.
• I ‚ nejsem si jistý, zda “ dostatečně blízko “ odpověď je to, co ‚ hledáme zde .
• @justhalf zbývá den na dokončení mého běhu. stále běží, našel jsem vše do 12k kromě 10958. po dokončení běhu budu sdílet svůj kód a výsledek, pravděpodobně neříkám žádné řešení pro 10958. Zavřete dost výsledků pouze pro ur informace.

S druhou odmocninou to můžete udělat:

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

Bez odmocniny nebo zřetězení výsledků jiných operátorů je nejlepší, co můžu udělat:

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

Je jen náhoda, že nejlepší výsledek bez zřetězení výsledků jiných operátorů také nezahrnuje žádné zřetězení čísel.

Toto je program, který provedl vyhledávání. Napsal jsem ho před několika lety, abych vyřešil další hádanku v žánru „držet některé operátory v tomto řetězci čísel“.

Nedělá to však unární mínus, takže možná stále existuje prostor pro zlepšení.

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

Komentáře

• Pro záznam si myslím, že ten, kdo ‚ t neuvádí zřetězení jako operátor, ale přesto ho stejně použije, podvádí víc než ten, kdo to říká je operátor a používá ho chytřeji.
• Podobný kód jsem napsal v pythonu, který provádí náhodné vyhledávání ve všech možných výrazech: github.com/basarane/10958-Problem — Random-Search / blob / master / …
• Trochu odlišný přístup: github.com/DaveJarvis/sequential

Našel jsem toto řešení u videa na YouTube (ne moje řešení) a je ještě blíže než nejbližší v původním komentáři: $ 1 + (2- (3 ^ {(4 * 5/6/7) ))}) ^ {(- 8)} + 9 = 10958.0020579103 $

Věřím, že tato otázka již má odpověď, tady je odkaz Vykreslení čísla 10 958 pomocí řetězce 1 2 3 4 5 6 7 8 9

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

(nebo)

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

Komentáře

• Vítejte v Puzzling.SE! Pokuste se dodržovat pravidla uvedená ve výše uvedené otázce. Konkrétně se používá druhá odmocnina, což není povoleno.
• (stejné pro faktoriál)
• @Rubio & lan, můžeme ‚ t získáte přesnou odpověď pomocí základních operací. V takovém případě musíte zopakovat libovolné číslo pro 10958, jako je toto .. (na základě pravidel moje odpověď: (1 + 2) ^ (3 + 4) * 5 + (6 + (- 7 + 7) + 8 + 9 ) = 10958)
• Jak ale víte, že pomocí těchto pravidel ‚ nedostaneme přesnou odpověď? Myslím, že to je ‚ d zajímavý důkaz a já ‚ bych byl zvědavý, jak to uvidím.
• Ne, ‚ jsem nedostal přesnou odpověď. Zní to, jako byste říkali, že to není ‚ možné (“ ‚ nemůžeme získat přesnou odpověď pomocí základních operací „), takže mě zajímalo, jak jste k tomuto závěru dospěli.

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

Rozhodli jsme se, že se PEMDAS stane PCEMDAS, kde „C“ je funkce concat. Užijte si druhé řešení!

EDIT: Máme několik dedikačních podnikových strojů s některými slušnými specifikacemi, které procházejí některými testy. Trvání všech případů by mělo trvat jen zhruba 3 miliony let. Většina pravděpodobných by však měla skončit příští týden.

Komentáře

• Nechci to ‚ kvalifikovat jako odpověď, protože OP nezahrnuje zřetězení jako přijatelná operace. I když to může být správná odpověď, nedodržuje pokyny pro skládání.
• Ano, snažili jsme se najít řešení bez použití zřetězení, ale začali jsme ho povolit, protože jsme věděli o jednom řešení, které zahrnovalo použití concat jako funkce. Původní dokument najdete arxiv.org/pdf/1302.1479.pdf a tam říká, že a ^ b je povoleno stejně jako ab (aka concat).Ale ve svých řešeních dělá věci jako (1 + 2) ^ 3, což znamená “ a “ by bylo “ (1 + 2) “ a poté jsme si mysleli, že by mělo být umožněno “ (1 + 2) b „. Znovu doufáme, že najdeme řešení, které nezahrnuje provádění tohoto triku: D
• UPDATE: nalezeno 27 přesných řešení a většinu z nich zkontrolováno. Všechny smutně zahrnují tento trik hloupého zřetězení: /

$ 1-2 + (- 3 + 6) * 457 * 8-9 = 10958 $ Je povoleno provádět operaci před a za závorkou? V podstatě jsem to ukradl osobě, která našla odpověď, která nepoužila 6.

Komentáře

• Toto není ‚ t “ použití všech 1-9 číslic ve vzestupném pořadí a pouze jednou “ – číslice nejsou vzestupné objednat.