划分一：对于一个正整数n的分划就是把n写成一系列正整数之和的表达式。例如，对于正整数n=6，它可以分划为：

6  

5+1  

4+2,  4+1+1  

3+3,  3+2+1,  3+1+1+1  

2+2+2,  2+2+1+1,  2+1+1+1+1  

1+1+1+1+1+1

       根据例子发现“包括第一行以后的数据不超过6，包括第二行的数据不超过5，……，第六行的数据不超过1”。

          因此，定义一个函数Q(n,m)，表示整数n的“任何被加数都不超过m”的分划的数目，n的所有分划的数目P(n)  =Q(n,n)。

   模型建立：

    一般地Q(n.m)有以下递归关系：

  1)Q(n,n)=1+Q(n,n-1)     （m=n）

    Q(n,n-1)表示n的所有其他分划，即最大被加数m<=n-1的划分。

 2)Q(n,m)=Q(n,m-1)+Q(n-m,m)    (m<n)

   Q(n,m-1)表示被加数中不包含m的分划的数目；

Q(n-m,m)表示被加数中包含(注意不是小于)m的分划的数目。

  递归的停止条件：

   1)Q(n,1)=1，表示当最大的被加数是1时，该整数n只有一种分划，即n个1相加；

    2)Q(1,m)=1，表示整数n=1只有一个分划，不管最大被加数的上限m是多大。

算法如下：

int

 Q(

int

 n,

int

 m)

{

   

if

(n

==

1

||

m

==

1

) 

return

 

1

;

   

else

 

if

(n

<

m) 

return

 Q(n,n);

   

else

 

if

(n

==

m) 

return

 

1

+

Q(n,n

-

1

);

   

else

 

return

 Q(n,m

-

1

)

+

Q(n

-

m,m);

}

 划分二：把一个正整数m分成n个正整数的和，有多少种分法？

例：把5分成3个正正数的和，有两种分法：

1 1 3

1 2 2

 算法如下：

1 

int

 f(

int

 m,

int

 n)

2 

{

3 

    

if

(m

<

n) 

return

 

0

;

4 

    

else

 

if

(n

==

1

||

n

==

m) 

return

 

1

;

5 

    

else

 

return

 f(m

-

1

,n

-

1

)

+

f(m

-

n,n);

6 

}