Euler problem 76


Euler Problem 76: Particioniranje broja.

Particioniranje broja detaljno je objašnjeno na ovom linku, pa stoga je vrlo jednostavno implementirati rješenje.

Ne ulazeći dublje u optimizaciju ovog koda implementacija traje malo duže, mada se vrijeme izvršavanja lako može skratiti.

static long PartitionFn(long k, long n)
{
    if (k > n)
        return 0;
    else if (k == n)
        return 1;
    else
        return PartitionFn(k + 1, n) + PartitionFn(k, n - k);
}
static void Main(string[] args)
{
    Console.WriteLine(PartitionFn(1,100) - 1);
    Console.Read();
}

Mada Mathematica ima posebnu funkciju za ovo:

PartitionsP[100] - 1

Na ovom linku (numerikana.com) se mogu naći bezbroj algoritama vezanih za teoriju brojeva.

Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s