Euler Problem 104:
Na prvi pogled zadatak vrlo prost. Mathematica bi trebala da ga riješi za pa sekundi. Medjutim…
Prvi Brute force pokušaj i nije bio toliko loš.
For[i=45,True,i++,lst=IntegerDigits[Fibonacci[i]]; If[Sort[lst[[1;;9]]]=={1,2,3,4,5,6,7,8,9},If[Sort[Take[lst,-9]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]] ];i
Print[i] koji je stavljen ispisiva pandigitalne brojeve prvih 9 cifara Fibonaccievog broja. Ovim se htjelo vidjeti kako se često takvi brojevi pojavljuju, i drugo kako brzo algoritam radi.
Ubrzo se vidjelo da kod neće završiti brzo.
Druga optimizacija bila je da se izračunava ostatak djeljenja Fibonaccievog niza sa 10^9, a onda da se provjeri da li je prvi dio cifara pandigitalan. Odmah se vidjelo da je algoritam dosta brži ali i da neće završiti za 60 sekundi.
For[i=45,True,i++, If[Sort[IntegerDigits[Mod[Fibonacci[i],10^9]]]=={1,2,3,4,5,6,7,8,9}, If[Sort[IntegerDigits[Fibonacci[i]][[1;;9]]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]]];
U implementaciji najsporiji dio je funkcija Fibonacci[], koja svaki put mora ispočetka da izračunava Fobonaccijev broj. Sada je potrebno ovaj dio optimizirati:
f1=1;f2=1;For[i=3,True,i++, f=f1+f2; If[Sort[IntegerDigits[Mod[f,10^9]]]=={1,2,3,4,5,6,7,8,9}, If[Sort[IntegerDigits[f][[1;;9]]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]]; f1=f2; f2=f ];i
Kod se izvršava za 20 sec što je prihvatljiv rezultat. Približan rezultat dobijemo i sa C# implementacijom:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics; namespace EulerProblem104 { class Program { static void Main(string[] args) { BigInteger div=BigInteger.Pow(10,9); long n = 1; foreach (var x in FibonacciNiz()) { if (IsPanDigital(x % div)) { string ss = x.ToString(); if (ss.Length > 8) { var digits = ss.Substring(0, 9); if (IsPanDigital(BigInteger.Parse(digits))) break; } } n++; } Console.WriteLine(n); Console.WriteLine("Press any key to continue..."); Console.Read(); } static bool IsPanDigital(BigInteger numb) { var v = numb.ToString(); if (v.Length < 9) return false; var ss=v.OrderBy(x => x).ToArray(); for (int i = 0; i < ss.Count(); i++) if (ss[i].ToString() != (i + 1).ToString()) return false; return true; } static IEnumerable<BigInteger> FibonacciNiz() { BigInteger a = 1; BigInteger b = 1; BigInteger c = 0; yield return a; yield return b; while (true) { yield return c = a + b; a = b; b = c; } } } }