设m,n均为自然数,m可以表示为一些不超过n的自然数之和,试编写函数f(m,n)计算这种表达方式的数目.

1
2
3
4
5
6
input: f(5,3)
output: 5

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

根据题意数据结构用基本数据类型就可以.算法明显使用分治递归最简单.

它只要求数目,不要求列出表达式.找到数目计算方法就行了.

我还是想错了,更方便的方法是使用递归.理解题意也有问题.如果把它当做一个找规律题来做也是可以的,编程实现的运行会非常快,只有O(1)而递归是O($$a^n$$)

分析：
确定递归的终止条件。

第一个终止条件
if (m==1) return 1;这里是说如果m等于1,则函数的返回值为1,显然1只能分解为1,也即表示方式只有一种.

第二个终止条件
if (n==1) return 1;这里是说如果n等于1,则函数的返回值为1,显然无论m多大,n为1时只能表示为m个1之和,也即表示方式只有一种.

当m>n时，f(m,n) 可以递归地分解为两种情况：
当最大加数包含n时，即f(m-n, n)
当最大加数不包含n时，即f(m, n-1)
比如f(6,4)，分成两类讨论：如果最大的加数为3，则按照定义共有f(6,3)种表示方法；而剩下的表示方法中必然有一个最大的加数4，由于总和为6，因此可知其余的加数之和为(6-4)2，而要使小于等于4的自然数之和等于2，按照函数定义共有f(2,4)种可能性。因此f(6,4)=f(6,3)+f(2,4)。

当m<n时如果所有的加数都为自然数的话，则最大的加数是不会超过和的，因此在m小于n的情况下加数也必然小于m。

即

1
2
3
4
5
m=1,f(m,n)=1
n=1,f(m,n)=1
m<n,return f(m,m)
m=n,return 1+f(m,m-1)
m>n,return f(m,n-1)+f(m-n,n)

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f(int m, int n)
{
	if(m==1)
        return 1;
	else if(n==1)
        return 1;
	else if(m<n) 
		return f(m,m);
	else if (m==n)
		return 1+f(m,n-1);
	else //(m>n)这里注意不能使用else if(m>n)
	//要避免所有条件不成立时.程序最后会执行此语句
		return f(m,n-1)+f(m-n,n);
}

这里有个疑问,自然数包含0.如果n为0,那么f(5,0)是否应该等于0.我的程序得到的结果为1.所以改成正整数就可以了.