Wednesday 29 April 2009

PROJECT EULER #76

Link to Project Euler problem 76

It is possible to write five as a sum in exactly six different ways:


4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Here we go...yet more virgin territory for me, but isn't that the point?
Partitions....the clue is to store values somewhere, so we do it in a 2-D grid.


using System;

namespace ProjectEuler
{
class Program
{
static void Main()
{
//Problem 76
DateTime start = DateTime.Now;
int n = 100;
int[,] a = new int[n + 1, n + 1];
for (int i = 0; i < n + 1; i++)
{
a[i, 0] = 0;
a[0, i] = 1;
}
for (int i = 1; i < n + 1; i++)
{
a[i, 1] = 1;
for (int j = 2; j < n + 1; j++)
{
int k = i - j;
if (k < 0)
a[i, j] = a[i, j - 1];
else
a[i, j] = a[i, j - 1] + a[k, j];
}
}
Console.WriteLine(a[n, n - 1]);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
}
}

No comments: