整數劃分

整數劃分是將正整數n表示為多個不小於1的整數之和的組合形式，不同順序的加數被視為同一划分，例如5=3+1+1與5=1+3+1屬於同一划分。其在計算機科學中常用於遞歸算法的典型問題。

該算法的核心是遞推關係：當n=1或劃分最大數為1時，劃分數為1；當n等於劃分最大數m時，劃分數為1加上n的(m-1)劃分；若n則等價於n的n劃分；其他情況遞歸計算包含與不包含最大值m的劃分數之和。通過約束劃分元素有序性避免重複計算，保證結果唯一性。

該算法思想源於組合數學中的整數分拆遞歸建模，遞推關係體現了動態規劃的重疊子問題特性。在編程實現中，常用遞歸或記憶化搜尋最佳化效率，C語言、Java等均可實現核心邏輯。

基本介紹

• 中文名：整數劃分
• 所屬學科：數學、遞歸
• 所屬行業：教育

概念

所謂整數劃分，是指把一個正整數n寫成為

其中， 為正整數，並且 ； 為n的一個劃分。

如果 中的最大值不超過m，即 ，則稱它屬於n的一個m劃分。

求劃分個數

算法分析

這裡我們記的劃分的個數為 。

例如，當時，有個劃分，即 ， ， ， ， 。

注意： 和 被認為是同一個劃分。

根據和的關係，考慮一下幾種情況：

（一）當 時，無論的值為多少 ，只有一種劃分，即 。

（二）當 時，無論的值為多少，只有一種劃分個，即 。

（三）當 時，根據劃分中是否包含，可以分為以下兩種情況：

（1）劃分中包含的情況，只有一個，即 。

（2）劃分中不包含的情況，這時劃分中最大的數字也一定比小，即的所有 劃分。

因此 。

（四）當 時，由於劃分中不可能出現負數，因此就相當於 。

（五）當 時，根據劃分中是否包含最大值m，可以分為以下兩種情況：

（1）劃分中包含的情況，即 ，其中 的和為，因此這種情況下為 。

（2）劃分中不包含的情況，則劃分中所有值都比小，即的劃分，個數為 。

因此 。

綜上所述：

那么對於正整數，它的劃分數為。

JAVA實現

class Solution{
    /**
* 正整數n，最大加數不大於m的劃分數
* @params {int}n 待劃分數
* @params {int}m 劃分序列中的最大數
* @returns {int} 返回本次劃分數
* /
    public static int q(int n,int m){
   //若正整數或最大加數小於1，則返回0
   if(n<1||m<1) return 0;
   //若正整數或最大加數等於1，則劃分個數為1（n個1相加）
   if(n==1||m==1) return 1;
   //若最大加數實際上不能大於正整數n，若大於則劃分個數等於最大加數為n的劃分個數
   if(n<m) return q(n,n);
   //若正整數等於最大加數，則劃分個數等於
   if (n==m) return 1+q(n,n-1);
   //若正整數大於最大加數 返回如下劃分結果
   return q(n,m-1)+q(n-m,m);
    } 
	public static void main(String[] args){
    	Solution solution = new Solution();
   // 測試
   solution.q(4,4) //返回結果為 5
    }
}

C語言實現

#include<stdio.h>
void main()
{
    int equation(int n,int m);
    int n,m;
    printf("Please input 'n'(0<n<100):");
    scanf("%d",&n);
    printf("Please input 'm'(0<m<=n):");
    scanf("%d",&m);
    printf("quantity:%d\n",equation(n,m));
}
int equation(int n,int m)
{
    if(n==1||m==1)
        return (1);
    else if(n<m)
        return equation(n,n);
    else if(n==m)
        return 1+equation(n,n-1);
    else
        return equation(n-m,m)+equation(n,m-1);
}

求具體劃分集合

劃分分析

把一個正整數n分成 ，若使 ，可求出一種劃分，再使x遞減，令x是劃分好的數，按此方法繼續對y繼續進行分解，以此類推，直到 （不包含 ）為止，這樣就求出了所有劃分。

在分解時應保證分解數x有序，即上一次的x要大於等於這一次的x，以避免求出元素相同但位置不同的結果。

例：當 時，部分過程如圖1所示：

圖1 當n=6時的部分過程

C語言實現 劃分合集