Euler Problem 99


Euler Problem 99:

Umjesto kompariranja datih brojeva po stepenima, brojeve je dovoljno provjeriti po logaritmima, jer je log funkcija rastuća. To pak znači ako je potrebno provjeriti koji broj je veći:

632382^{518061}>519432^{525806}

dovoljno je logaritmirati nejednakost pa imamo:

518061Log(632382)>525806Log(519432)

Na osnovu izloženog implementiran je sljedeći kod koji rješava problem:

namespace Problem99
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader reader = null;
            reader = System.IO.File.OpenText("base_exp.txt");
            string buffer = reader.ReadToEnd();

            var resultLine = buffer.Split(new char[] { '\r', '\n' },
                                 StringSplitOptions.RemoveEmptyEntries)
                             .Aggregate(
                             new {maxNumber=0.0,lineFromGreatesNumber=1, currentLine=0},
                             (prevLine, stringLine)=>
                             {
                               //Frmiranje broja iz string linije
                               int baseNumber =int.Parse(stringLine.Split(',')[0]);
                               int exponent = int.Parse(stringLine.Split(',')[1]);
                              //Umjesto stepenovanja usporedjujemo brojeve po lagaritmima
                             //jer je log funkcija rastuća za posmatrani interval
                             double result= exponent*Math.Log10(baseNumber);

                             //Komparacija sa prethodnim največim brojem
                             if (result > prevLine.maxNumber)
                                return new { maxNumber = result,
                               lineFromGreatesNumber = prevLine.currentLine + 1,
                              currentLine = prevLine.currentLine + 1 };
                            else
                               return new { maxNumber = prevLine.maxNumber,
                               lineFromGreatesNumber = prevLine.lineFromGreatesNumber,
                              currentLine = prevLine.currentLine + 1 };
                             }
                             ).lineFromGreatesNumber;
            Console.WriteLine(resultLine);
            Console.WriteLine("Press any key to continue...");
            reader.Close();
            Console.Read();
        }
    }
}

About Bahrudin Hrnjica

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

Posted on 07/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