Problem 76 - Counting Summations

Çözerken zevk aldığım problemlerden biri de problem 76 oldu. Gerek dinamik programlamayla soruyu ufak parçalara ayırıp çözülebildiği gibi, formülleyerek de çözüme gitmek mümkün. Formülü bulmak bana daha eğlenceli geldi açıkçası, her ne kadar dinamik programlamaya göre zahmetli de olsa bu bir bulmaca.

Soru

5'i şu şekilde, 6 farklı ifadeyle yazmak mümkün
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1

Peki 100 sayısını bu şekilde yazmak istersek kaç farklı ifade ortaya çıkar? (En az iki pozitif sayının toplamı şeklinde olmalı)


Çözüm

Formülleme

Sayımız n ise, p(n) fonksiyonu bize n sayısının kaç farklı pozitif toplam şeklinde yazılabileceğini versin.

Bu durumda araştırma yaptığınızda görüyorsunuz ki, p(n) değerleri esasında "Beşgensel Sayı Teoremi" - "Pentagonal Number Theorem" ile örtüşüyor, fakat değerler bir eksik. Sebebi ise sanıyorum bu teoremde, işleme n+0'ın da katılıyormuş gibi farz edilmesi. Dolayısıyla hesaptan 1 çıkaracağız.

Pentagonal Number Theorem hakkında buradan daha fazla bilgi edinebilirsiniz.
http://en.wikipedia.org/wiki/Pentagonal_number_theorem

Genellediğimizde şu sonuçlarla karşılaşıyoruz

p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ...

Formülsel ifade edecek olursak

k = 1, -1, 2, -2, 3, -3...
gk = 1, 2, 5, 7, 12


p(0) = 1
p(1) = 1
p(2) = 2
p(3) = 3
p(4) = 5
p(5) = 7
p(6) = 11
p(7) = 15
p(8) = 22
p(9) = 30
p(10) = 42
p(11) = 56
p(12) = 77

p(5) = p(4) + p(3) - p(0)
7 = 5 + 3 - 1

p(6) = p(5) + p(4) - p(1)
11 = 7 + 5 - 1

p(7) = p(6) + p(5) - p(2) - p(0)
15 = 11 + 7 - 2 - 1

p(8) = p(7) + p(6) - p(3) - p(1)
22 = 15 + 11 - 3 - 1

p(9) = p(8) + p(7) - p(4) - p(2)
30 = 22 + 15 - 5 - 2

p(10) = p(9) + p(8) - p(5) - p(3)
42 = 30 + 22 - 7 - 3

p(11) = p(10) + p(9) - p(6) - p(4)
56 = 42 + 30 - 11 - 5

p(12) = p(11) + p(10) - p(7) - p(5) + p(0)
77 = 56 + 42 - 15 - 7 + 1


Kodlama

int hedef = 100; int sayici = 0; int _k = 1;
int[] k = new int[hedef+1];
int[] gk = new int[hedef+1];
int[] p = new int[hedef+1];

// hedef'e kadar olan gk'lar için k'ları belirliyoruz
// gk = k(3k-1)/2 for k = 1, -1, 2, -2, 3...

while (sayici < hedef)
{
   if (sayici % 2 == 0) // 1, 2, 3, ...
   {
      k[sayici] = _k;
   }
   else // -1, -2, -3, ...
   {
      k[sayici] = (-1) * _k;
      _k++; // Negatif değer verildikten sonra k +1 artıyor
   }
   // Sonuç k[] = {1, 1, 2, -2, 3, ...}

   sayici++;
}

// k'lardan yola çıkıp gk'ları belirliyoruz

for (int q = 0; q < hedef; q++)
{
   // gk = k(3k-1)/2 ---> Beşgensel sayılar
   gk[q] = (k[q]) * (3 * k[q] - 1) / 2;
}

// Şimdi p(n)'leri belirleyebiliriz, eldeki gk değerlerini kullanacağız
// p(n) = S [(-1)^(k-1) . p(n-gk)] --> S for Sigma

int c = 0;
p[0] = 1; p[1] = 1; p[2] = 2; p[3] = 3; p[4] = 5;

for (int n = 5; n <= hedef; n++)
{
   c = 0;
   while (n - gk[c] >= 0)
   {
      p[n] += (Int32)(Math.Pow((-1), (k[c] - 1)) * p[(n - gk[c])]);
      c++;
   }
}

p[n] dizisi, 100'e kadar olan sonuçları 1'er fazla olacak şekilde barındırmaktadır.(Soruda istenilene göre 1 fazla, teoreme göre doğru)

Dinamik Programlama

Esas problemi, ufak alt problemlere ayırarak çözümü daha kolay hale getirmek mümkün. Bunun için dinamik programlamaya göz atmakta fayda var. Çözüm çok daha kısa görünecektir.
int[] ifadeler = new int[hedef + 1];
int hedef = 100;
ifadeler[0] = 1;

for (int i = 1; i <= 99; i++)
{
   for (int j = i; j <= hedef; j++)
   {
      ifadeler[j] += ifadeler[j - i];
   }
}

Sonuç : 190569291 bulunur.