函数f(m,n)算法设计

题目：

设m，n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。

例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。

以下是该函数的程序段，请将未完成的部分填入，使之完整。

int f(int m, int n)
{
    if(m == 1)   return ___;
    if(n == 1)   return ___;
    if(m < n)   return f(m,m);
    if(m == n)     return 1 + ___;
	return f(m,n-1) + f(m-n,___);
}

解析：

我们先对已给出代码进行分析：

int f(int m, int n)   //定义f(m,n)函数,返回值表示方式的数目,返回值类型为整数.
{
    if(m == 1)   return ___;   //当m=1时，显然1只能分解为1+0,即表示方式只有一种，返回值应为1
    if(n == 1)   return ___;   //当m=1时，显然无论m多大,n为1时只能表示为m个1之和,即表示方式只有一种，返回值应为1
    if(m < n)   return f(m,m);   //见下方说明1
    if(m == n)     return 1 + ___;   //见下方说明2
	return f(m,n-1) + f(m-n,___);   //见下方说明3
}

• 说明1：

  当m<n时，这里需要注意不应该是返回错误，而是将返回值转化为f(m,m)。这hi因为如果所有的加数都为自然数的话，则最大的加数n是不会超过和m的，因此将m小于n的情况转化为m=n的情况，此处使用函数的递归调用。

  如f(2,3)=f(2,2)。

• 说明2：

  当m=n时，则返回值为1+f(m,n-1)，因为f(m,n)只比f(m,n-1)多了一个n+0的表示方法。

  如f(3,3)=1+f(3,2)

• 说明3：

  当其他情况，即当m>n时，f(m,n) 可以递归地分解为两种情况：

  1. 当最大加数不包含n时，即f(m, n-1)。即最大加数为(n-1)时的表示方式数量。

  2. 当最大加数包含n时，即f(m-n, n)。因加数中至少有一个n，因此表示方式数量相当于剩下的数字m-n可表示为不大于n的自然数之和，按照函数的定义，表示方式的数量为f(m-n,n)。

     如题干中的f(5,3),在去除第一种情况不包含 3 即 f(5,3-1)=f(5,2)（2+2+1，2+1+1+1，1+1+1+1+1）后，其余表示方式数量为 f(5-3,3)=f(2,3)（3+2，3+1+1）=f(2,2)（2+0，1+1）

     再如f(6,2)，在去除第一种情况不包含 2 即 f(6,2-1)=f(6,1)=1（1+1+1+1+1+1）后，其余表示方式数量为 f(6-2,2)=f(4,2)

答案：

故答案为：

int f(int m, int n)
{
    if(m == 1)   return 1;
    if(n == 1)   return 1;
    if(m < n)   return f(m,m);
    if(m == n)     return 1 + f(m,n-1);
	return f(m,n-1) + f(m-n,n);
}