Euler Problem 104


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

}

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 18/03/2010, in Project Euler and tagged . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s