Çö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.
