Project Euler i C#


Od 2001 godine pokrenuta je stranica nazvana Project Euler, koja objavljuje zadatke iz matematile koji se rješavaju sa kompjuterskim programima. Do danas je objavljeno 267 zadataka uglavnom iz teorije brojeva koji se rješavaju pogodnim algoritmima. Zadaci koji su postavljeni tiču se teorije brojeva, kombinatorike i vjerojatnosti, a fora je u tome da se nađu pogodni algoritmi koji rješavaju problem. Nekoliko blog stranica rješavaju ove zadatke preko LINQ u C# jer rješenje ovih zadataka čini posebnim, radi same elegancije LINQ upita. Naravno ovim postom nije mi namjera da rješavam sve zadatke postavljene na stranici, ali kroz nekoliko rješenja zadataka može se pokazati prava elegancija i “umjetnost” programiranja sa LINQ i programskog jezika C#.

Problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
Ako prikažemo sve prirodne brojeve manje od 10, koji su multiplikatori brojeva 3 ili 5, dobićemo 3,5,6 i 9. Suma ovih multiplikatora iznosi 23. Pronaći sumu svih multiplikatora 3 ili 5 koji su manji od 1000.

Rješenje:

Pogodnim korištenjem LINQ upita rješenje se dobija u samo jednoj liniji koda:


var rjesenjeP1 = Enumerable.Range(1, 999).Aggregate(0, (parSum, i) => ((i % 3 == 0) || (i % 5 == 0)) ? parSum + i : parSum);

Objašnjenje: Range metoda Enumerable klase daje nam sve prirodne brojeve od 1 do 999, nad kojim vršimo upit prekooperatora Aggregate, koji nam omogućava manipulaciju nad svakim prirodnim brojem u datom intervalu. Ako je neki broj djeljiv sa 3 ili 5 dodaj ga parcijalnoj sumi parSum, čija je početna vrijednost 0, definisana prvim argumentom operatora Aggregate.

Problem 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Svaki član Fibonaccijevog niza dobijen je zbirom prethodna dva. Krenuvši sa 1 i 2, prvih 10 članova niza su:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Potrebno je pronaći sumu svih parnih članova niza manjih od 4 000 000.

Rješenje: Za rješenje ovog problema potreno je implemenirati metodu za vraćanje članova Fibonaccijevog reda.

static IEnumerable<long> FibonacciNiz()
 {
  //Prva dva clana, odnosno prethodna dva
  long a = 1;
  long b = 2;
  //i-ti clan
  long c = 0;
  yield return a;
  yield return b;

 while (true)
  {
   yield return c = a + b;
   //nakon proracuna i-tog clana
   // prethodna dva clana postaju
   a = b;
   b = c;
  }
 }

Nakon što imamo metodu za vraćanje članova Fibonaccievog niza, sada se suma može izračunati kao:

var rjesenjeP2 = FibonacciNiz().TakeWhile(x => x <= 4000000).Sum(x => x % 2 == 0 ? x : 0);

Objašnjenje: Neprestano uzimamo članove Fibonaccievog niza, dok god su članovi manji od 4 miliona. Za to vrijeme pravimo sumu članova koji su parni brojevi odnosno koji su djeljivi sa 2.

Problem 3:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
Prosti faktori broja 13195 su 5,7,13 i29. Pronaći najveći prosti faktor broja 600851475143.

Rješenje: Metoda za rastavljanje na proste faktore implementirana je u blog postu o yield naredbi, koju ćemo iskoristiti za rješavanje ovog problema. Međutim, potrebno je metodu prilagoditi ovom problem u smislu 64-bitnog integera, pa u metodi gdje se koristio int,potrebno je staviti long. Implementacija je prikazana u narednom tekstu:

//Rastavljanje broja n na proste faktore n=n1*n2*n3*...nn
public static IEnumerable<string> Foktoriziraj(string izraz, longn)
{
  //Ako je 1 vrati izraz
  if (n == 1)
    yield return izraz;
  else
  {
    //Prolazimo sve brojeve manje od n
    for (long i = 2; i <= n; i++)
     {
       //Ako je n djeljiv sa i
       if ((n % i) == 0)
        {
          long q = n / i;
          //Zapišimo u izraz broj i
          if (!izraz.EndsWith("= "))
             izraz += " * ";
          izraz += i.ToString();
          //Nad djeljiteljem q ponovimo isti postupak rekurzivno
          foreach (string podizraz in Foktoriziraj(izraz, q))
            yield return podizraz;
            yield break;
        }
     }
  }
}

Kada ovu metodu pozovemo na sljedeći način:

Console.WriteLine(Foktoriziraj(600851475143.ToString() + " = ", 600851475143).SingleOrDefault());

Dobićemo rezultat kao na slici.

Objašnjenje metode  se može pronaći na blog postu o yield komandi.

U nekom od sljedećih postova biće prikazana rješenja drugih interesantnih problema.

About Bahrudin Hrnjica

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

Posted on 17/12/2009, in .NET, C#, Programiranje 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