Euler Problem 73


Euler Problem 73:

How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Solution:

Rješenje problema svodi se na implementaciju metode za najveći zajednički djelilac, te dupla petlja koja prolazi sve integer projeve od 1-12000, s tim da je n<d.

Obzirom da je problem dosta jednostavan kao i brute force algoritam rješava problem za manje od minute, na stranici je dato efikasno objašnjenje zadatka i algortima, koji se bazira na Farey Sequances (Farray-ev niz). Moja Brute – Force implementacija:

static void Main(string[] args)
{
    long counter=0;
    double pol = 0.5;
    double trec = 1.0 / 3.0;
    for (int n = 1; n < 12000; n++)
    {
        for (int d = n + 1; d <= 12000; d++)
        {
            if (HCF(n, d) == 1)
            {
                double frac=((double)n)/((double)d);
                if (frac > trec && frac < pol)
                    counter++;

            }
        }
    }
    Console.WriteLine("Solution PE73={0}", counter);
    Console.WriteLine("Press any key to continue...");
    Console.Read();
}
static long HCF(long n, long d)
{
    while (d != 0)
    {
        long temp = n % d;
        n = d;
        d = temp;
    }
    return n;
}

About Bahrudin Hrnjica

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

Posted on 03/03/2010, in C#, 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