Matematické Fórum

Ahoj, řekl bych, že při použití hrubé síly bude pro [mathjax]n[/mathjax] cifer na vstupu zapotřebí [mathjax]3^{n-1}[/mathjax] kroků výpočtu (pro větší počet cifer neřešitelné).
Když nám bude stačit první správné řešení, asi skončíme dřív. Pokud budeme chtít všechna řešení, musíme pokračovat do hořkého konce.
Když úloha nemá řešení, asi budeme muset spočítat taky všechno.

Další zkracování výpočtů bude asi záviset na zadané hodnotě výsledku [mathjax]N[/mathjax].

Např.:
1. Protože známe nejmenší a největší možnou hodnotu výsledku,úloha nemá řešení, když je [mathjax]N[/mathjax] mimo tyto meze. (Které to jsou?)

2.Protože známe [mathjax]N[/mathjax], můžeme každý krok výpočtu zabrzdit po dosažení [mathjax]N[/mathjax] - zůstává stejný počet kroků

3. Když je [mathjax]N[/mathjax] čtyřciferné, nebudeme sčítat větší než čtyřciferné skupiny- snižuje se počet kroků

atd.

Nevím nevím, jestli se to dá nějakou fintou zásadně zjednodušit...

Jen pozor na to násobení 0 - to je jediný případ, kdy se mezivýpočet sníží a tak může některé heuristiky nabourat.