整數(shù)數(shù)的劃分問(wèn)題：就是把一個(gè)整數(shù)n劃分成一系列整數(shù)的和。當(dāng)n=6時(shí)：
6；
5+1，
4+1+1，4+2；
3+1+1+1，3+2+1，3+3；
2+1+1+1+1，2+2+1+1,2+2+2;
1+1+1+1+1+1+1;
觀察上面的列表，可以得出觀察結(jié)論：對(duì)于每一行的第一個(gè)數(shù)字，總比上一行的數(shù)字小，且這一行都小于上一行，也就是基于更小的劃分。所以我們可以想到遞歸，但是怎么樣設(shè)計(jì)這個(gè)遞歸呢？就從“每一行是一個(gè)新的劃分，縮小問(wèn)題的規(guī)模。得出Q(n,m)是對(duì)n的不大于m的劃分。然后我們?cè)谟懻撨@個(gè)Q(n,m)函數(shù)問(wèn)題！
1.m>n時(shí)：
對(duì)于n，對(duì)它進(jìn)行m劃分，那么相當(dāng)于對(duì)它進(jìn)行n劃分。也就是Q(n,m)=Q(n,n);
2.m=n時(shí)：
對(duì)于這種劃分可以分成一個(gè)更小的規(guī)模，分成不大于n-1的劃分和1，這個(gè)1就是對(duì)n的劃分，就是n。所以Q(n,m)=(n,n-1)+1;
3.n>m時(shí)：
劃分成兩個(gè)字部分，首先對(duì)它進(jìn)行不大于m-1的劃分，也就是Q(n,m-1),然后對(duì)它進(jìn)行m的劃分，但總的成為n-m啦（想一下為什么？惡哈哈），為：Q(n-m,m).所以總的個(gè)數(shù)為：Q(n,m)=Q(n,m-1)+Q(n-m,m);
情況討論完了，現(xiàn)在該設(shè)計(jì)遞歸出口了：
當(dāng)n=1||m=1時(shí)：顯然是1中劃分。
接下來(lái)我們?cè)搶?xiě)代碼了，如下：

 1/**//*
 2  Name: 整數(shù)的劃分
 3  Copyright: Copyleft
 4  Author:
 5  Date: 21-09-08 19:48
 6  Description:
 7*/
 8int main()
 9{
10    int n,m;
11    scanf("%d",&n);
12    m=divinteger(n,n);
13    printf("%d\n",m);
14    system("PAUSE");
15    return 0;
16}
17
18int divinteger(int n,int m)
19{
20    if(n<1||m<1)
21    {
22        printf("Error!\n");
23        exit(1);
24    }
25    if(n==1||m==1)
26    {
27        return 1;
28    }
29    else if(m>n)
30    {
31        return divinteger(n,n);
32    }
33    else if(n==m)
34    {
35        return divinteger(n,m-1)+1;
36    }
37    else
38    {
39        return divinteger(n,m-1)+divinteger(n-m,m);
40    }
41}
42
43
44
45
46
47
48
49