A megoldás algoritmusa
Végigpróbáljuk az első (legbelső) zárójel lehetséges értékeit a négy alapművelet alkalmazásával, így visszavezetjük a problémát négy darab eggyel rövidebb számsorozat célérték keresésére. Pl.:
A feladat: (((5 ? 6) ? 7) ? 8) = 2
1.) 5+6=11 => ((( 11) ? 7) ? 8) = 2
2.) 5-6=-1 => ((( -1) ? 7) ? 8) = 2
3.) 5*6=30 => ((( 30) ? 7) ? 8) = 2
4.) 5/6= 0 => ((( 0) ? 7) ? 8) = 2
(megj.: egész osztás)
Ha ezt a műveletet még kétszer elvégezzük, akkor a 64 egész számot kapunk, amik közül ki kell választani a 2-höz legközelebbit, és az szám, illetve a hozzá tartozó műveletijel-sorrend lesz a megoldás.
Tehát a probléma egy olyan függvénnyel oldható meg rekurzívan, ami egy számsorozatot visszavezet négy dabrab eggyel rövidebbre, majd ezekre alkalmazza önmagát. Mindezt egészen addig, amíg minden számsorozat helyett egyetlen szám nem marad eredménynek, és ezek közül az eredmények közül kell kiválasztani a célértékhez legközelebbit.
A rekurzív függvényt pl. úgy valósíthatjuk meg, hogy paraméterként megkapja, hogy hányadik számjegyig vannak már összeolvasztva a számok, és azt, hogy mi az eredményük. (Ez az eredmény az egyel lerövidített számsorozat első eleme.) Ehhez az eredményhez aztán ő mind a négy művelettel hozzáadja a következő számjegyet, és meghívja önmagát ezen négy újabb eredménnyel, a következő számra. Amikor elfogytak a számok, akkor meg kell nézni, hogy az aktuális eredmény milyen közel van a célértékhez, és ha közelebb van az addigi legközlebbinél, akkor eltároljuk. Ha a függvényünk minden szinten eltárolta a műveleti jeleket, akkor a legjobb értékhez tartozó műveleti jelsorrendet is megkaphatjuk.
Nem szabad elfelejtkeznünk arról sem, hogy nullával nem osztunk. Ha nem tesszük fel az inputról, hogy poztitív egészekből áll, az osztások előtt ellenőriznünk kell, nem nulla-e az osztó.
A másik hasonló probléma pedig az, hogy ha túl sok nagy szám van a bemeneti számsorozatban, akkor a csupa szorzásjel esetének vizsgálata közben túlcsordulhat (és körbefodrulhat) az a változó, amiben az eredményt tároljuk. Ezért használjunk minél nagyobb egész típusokat, és túlcsordulás ellenőrzést. Pascalban és Delphiben: {$Q+}
Megoldásunk egyszerűen végignézi az összes $4^n$ lehetőséget, és egy minimumkiválasztással eldönti, melyik érték van legközelebb a célhoz.
Kicsit javíthat a hatékonyságon, ha megállunk abban az esetben, amikor pontosan "eltaláltuk" a célértéket.
Megoldások
