递归-整数划分代码,代码库,德仔网

代码语言

代码分类

【】递归-整数划分

作者:memristor / 发布于2014/9/10/ 601


	将正整数n表示成一系列正整数之和：n=n1+n2+&hellip;+nk，其中n1&ge;n2&ge;&hellip;&ge;nk&ge;1，k&ge;1。
	正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数
	将n中最大加数是m的划分个数记作f(n,m)。可以建立f(n,m)的如下递归关系
	（1）当 n = 1 时，不论m的值为多少（m > 0 )，只有一种划分即 { 1 };
	(2) 当 m = 1 时，不论n的值为多少，只有一种划分即 n 个 1，{ 1, 1, 1, ..., 1 };
	(3) 当 n = m 时，根据划分中是否包含 n，可以分为两种情况：
	 (a). 划分中包含n的情况，只有一个即 { n }；
	 (b). 划分中不包含n的情况，这时划分中最大的数字也一定比 n 小，即 n 的所有 ( n - 1 ) 划分。
	 因此 f(n, n) = 1 + f(n, n-1);
	(4) 当 n < m 时，由于划分中不可能出现负数，因此就相当于 f(n, n);
	(5) 但 n > m 时，根据划分中是否包含最大值 m，可以分为两种情况：
	 (a). 划分中包含 m 的情况，即 { m, { x1, x2, ..., xi } }, 其中 { x1, x2, ..., xi } 的和为 n - m，可能再次出现 m，因此是（n - m）的 m 划分，因此这种划分个数为 f(n-m, m);
	 (b). 划分中不包含 m 的情况，则划分中所有值都比 m 小，即 n 的 ( m - 1 ) 划分，个数为 f(n, m - 1);
	 因此 f(n, m) = f(n - m, m) + f(n, m - 1);

	unsigned long GetPartitionCount(int n, int max)
	{
	 if (n == 1 || max == 1)
	 return 1;
	 else if (n < max)
	 return GetPartitionCount(n, n);
	 else if (n == max)
	 return 1 + GetPartitionCount(n, max-1);
	 else
	 return GetPartitionCount(n,max-1) + GetPartitionCount(n-max, max);
	}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　整数划分　

同语言下

可能有用的

memristor贡献的其它代码(1)

.递归-整数划分