algorithm
पूर्णांक विभाजन एल्गोरिथम

पूर्णांक विभाजन एल्गोरिथ्म की बुनियादी जानकारी

पूर्णांक का विभाजन इसे सकारात्मक पूर्णांक के योग के रूप में लिखने का एक तरीका है। उदाहरण के लिए, संख्या 5 के विभाजन हैं:

• 5
• 4 + 1
• 3 + 2
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

ध्यान दें कि सारांश के क्रम को बदलने से एक अलग विभाजन नहीं होगा।

विभाजन फ़ंक्शन स्वाभाविक रूप से पुनरावर्ती है क्योंकि बड़ी संख्या के परिणाम में छोटी संख्या के परिणाम घटक के रूप में दिखाई देते हैं। बता दें कि p (n, m) केवल सकारात्मक पूर्णांक का उपयोग करने वाले n के विभाजन की संख्या है जो m से कम या बराबर है। यह देखा जा सकता है कि p> (n) = p (n, n) , और p (n, m) = p (n, n) = p (n) के लिए m > n

पूर्णांक विभाजन एल्गोरिथ्म का उदाहरण:

सहायक स्थान: O(n^2)
समय जटिलता: O(n(logn))

सी # में अंतराल विभाजन एल्गोरिथ्म का कार्यान्वयन

 public class IntegerPartition
{
    public static int[,] Result = new int[100,100];

    private static int Partition(int targetNumber, int largestNumber)
    {
        for (int i = 1; i <= targetNumber; i++)
        {
            for (int j = 1; j <= largestNumber; j++)
            {
                if (i - j < 0)
                {
                    Result[i, j] = Result[i, j - 1];
                    continue;
                }
                Result[i, j] = Result[i, j - 1] + Result[i - j, j];
            }
        }
        return Result[targetNumber, largestNumber];
    }

    public static int Main(int number, int target)
    {
        int i;
        for (i = 0; i <= number; i++)
        {
            Result[i, 0] = 0;
        }
        for (i = 1; i <= target; i++)
        {
            Result[0, i] = 1;
        }
        return Partition(number, target);
    }
}