Parçalanış Fonksiyonu p(n) Hesaplama

Nasıl hesaplanır?

p(n), n sayısını sıra gözetmeksizin pozitif tam sayıların toplamı olarak yazmanın yollarını sayar. Araç dinamik programlamayla bir tablo kurar: p[0] = 1 ve diğer tüm girişler 0 ile başlar, sonra 1’den n’ye kadar her parça büyüklüğü k için j = k’dan n’ye p[j] += p[j − k] güncellemesi yapılır. Son turdan sonra p[n] cevaptır. n, 0 ile 299 arasında bir tam sayı olmalıdır; negatif sayı, ondalık sayı ve 299’dan büyük değerler sonuç vermez, çünkü 300’den itibaren sayı kullanılan kayan noktalı sayılara tam olarak sığmaz. p(0) tanım gereği 1’dir ve sonuç binlik ayraçlarla gösterilir.

Sık yapılan hatalar

• Sıralamaları farklı parçalanış saymak. 3+1+1, 1+3+1 ve 1+1+3 tek bir parçalanıştır. Her sırayı saymak kompozisyonları verir; bunlar 2ⁿ⁻¹ gibi p(n)’den çok daha hızlı büyür.
• n’nin kendisinin de bir parçalanış olduğunu unutmak. p(4) = 5’tir, 4 değil; çünkü tek parçalı 4, 3+1, 2+2, 2+1+1 ve 1+1+1+1 ile birlikte sayılır.
• 299’un üstünde bir değer girip yaklaşık sonuç beklemek. Araç yalnızca kesin değer verir; 300 ve üstünde hiçbir şey döndürmez.
• Ondalık ya da negatif sayı girmek. Yalnızca 0 ve üstü tam sayılar geçerlidir.
• p(n)’yi farklı parçalara ya da yalnızca tek sayılara ayrılan parçalanış sayısı sanmak. Bu araç, tekrarlanan parçalar üzerinde kısıtlama olmaksızın tüm parçalanışları sayar.