技术开发 频道

编程小练习:拆分自然数

 【IT168技术文档】

转载自Jeff Zhao的博客   

    今天的题目如下:

 给出sum、min、max和n四个正整数,请输出所有将sum拆分为n个正整数之和,其中每个正整数k都满足:min <= k <= max。这n个正整数之间可以重复,不过由于加法交换率的作用,1 + 2和2 + 1便算是重复的拆分了。

 例如,sum = 5,n = 3,min = 1,max = 3,这时候满足条件的拆分方式只有两种:

 1 + 1 + 3

 1 + 2 + 2

 这个练习和上次不同,我们假设所有的输入都是正整数。您无需对其进行合法性判断,只要专注于业务实现便是。您在看下面的内容之前,不如自己先简单尝试一下?老赵建议,您可以在这里阐述您的思路。至于代码,您可以在自己的博客上写一篇文章,然后再这里贴上链接,如果直接在这里贴代码的话,会使评论列表变得很长,影响阅读。点此展开

 简单枚举

 假设我们最后的结果存放在一个长度为n的int数组中。则解决这道题目最简单的方式,自然为数组的每个元素枚举min到max之间的所有值,并在得到一个枚举序列之后,判断它是否符合题目要求。如果是,则输出。代码如下:

static void PrintDivision(int sum, int n, int min, int max)

 {

 int[] array = new int[n];

 DoSimple(array, 0, min, max);

 }

 private static void DoSimple(int[] array, int n, int minInclusive, int maxInclusive)

 {

 if (n >= array.Length)

 {

 if (IsValidResult(array))

 {

 PrintResult(array);

 }

 return;

 }

 for (int i = minInclusive; i <= maxInclusive; i++)

 {

 array[n] = i;

 DoSimple(array, n + 1, minInclusive, maxInclusive);

 }

 }

  DoSimple的含义为,为array数组下标为n的位置中枚举minInvlusive到maxInclusive之间的所有值,并深入。如果array数组填充完毕,那么判断是否是一个正确的结果,并输出。在这个解法中IsValidResult方法的任务颇为繁重,它除了判断array中所有元素之和是否为sum以外,还要判断这个array所表示的拆分是否已经出现过了。例如在已经输出了1 + 1 + 3的情况下,就不能输出3 + 1 + 1。这些都必须在IsValidResult中进行判断,当然做到这点也并不困难。

 不过这个做法的问题也是很明显的,就是重复太多。如果让我们进行“人力”拆分,我们肯定不会傻呆呆地为每个空格枚举从min到max之间的所有值。我们会知道,如果已经有了1 + 2,那么在出现2的时候,我们就不会再枚举1这个值。那么在编程时,我们又该如何进行限制呢?
原文地址:http://www.cnblogs.com/jeffreyzhao/archive/2009/06/21/1507847.html

 限制范围

 “冒泡排序”人人都会(无法在5分钟内写出一个正确的冒泡排序的朋友们应该面壁了),在它的二重循环中,内存循环并不会遍历数组的所有位置,因为外层循环实际上已经对内存循环的有效范围进行了限制。这段代码可能是这样的:

for (int i = 0; i < ...)

 {

 for (int j = i + 1; j < ...)

 {

 ...

 }

 }

  如果我们可以保证最终array序列中任意相邻元素,后者不小于前者,那么枚举到最后的结果一定是唯一的——这个应该很容易理解吧。于是我们把DoSimple的代码进行一些修改:

 private static void DoBetter(int[] array, int n, int minInclusive, int maxInclusive)

 {

 if (n >= array.Length)

 {

 if (IsValidResult(array)) // 只需检查array之和是否等于sum

 {

 PrintResult(array);

 }

 return;

 }

 for (int i = minInclusive; i <= maxInclusive; i++)

 {

 array[n] = i;

 DoBetter(array, n + 1, i, maxInclusive);

 }

 }

 与DoSimple方法相比,DoBetter的修改有二。首先,进行下层递归时minInclusive不再保持不变,而是把当前位置的值传入,这样便保证了下层递归所枚举的值一定大于等于当前值。其次,由于我们保证了每个枚举出的序列是唯一的,那么最后判断array是否为一个正确结果的IsValidResult方法,只需要将array数组的元素之和与sum进行比较即可。

 避免无效步骤

 DoBetter还是有一些明显的性能问题。例如,在枚举出多个max的情况下,其值已经大于sum了,那么接下来的所有步骤都是浪费。如果我们要避免这种浪费,就需要确保走的每一步都是迈向最终结果的。如果要做到这一点,有些朋友可能会选择在合适的时候“剪枝”,也就是发现死路之后及早回头。不过对于现在这题,我们可以使用另外的策略,也就是把每一步都控制在有效的范围内,避免走进一个“无解”的道路上。首先我们还是先列出代码吧:

 static void PrintDivision(int sum, int n, int min, int max)

 {

 if (min * n > sum) return;

 if (max * n < sum) return;

 int[] array = new int[n];

 DoBest(array, sum, n, min, max);

 }

 private static void DoBest(int[] array, int sum, int n, int minInclusive, int maxInclusive)

 {

 int index = array.Length - n;

 if (n == 1)

 {

 array[index] = sum;

 PrintResult(array);

 return;

 }

 int itemMinInclusive = Math.Max(sum - maxInclusive * (n - 1), minInclusive);

 int itemMaxInclusive = sum / n;

 for (int i = itemMinInclusive; i <= itemMaxInclusive; i++)

 {

 array[index] = i;

 DoBest(array, sum - i, n - 1, i, maxInclusive);

 }

 }

 首先,如果出现两种情况之一,那么肯定无法得出任何拆分结果:

min * n > sum

 max * n < sum

  其次,我们的DoBest方法的“含义”也有所变化。DoBest的含义是,将sum拆分成n个正整数(请注意,这里的n已经不是元素下标了),其中每个整数k都保证minInclusive <= k <= maxInclusive。于是在DoBest方法中,我们如果发现n为1,则意味着最后一个数值能取sum,于是输出结果。否则,我们已经对当前元素的值进行遍历。值得注意的是,我们并非直接遍历minInclusive到maxInclusive之间的值,因为可能我们取了其中最大或最小的几个值之后,我们拆分遍失败了(先想想,为什么?)。

 于是,我们在每层递归中,将会计算出当前位置真正可以摆放的值。这个值必须让后续拆分可以继续进行,因此它必须小于sum / n(因为后续n - 1个值都要大于等于当前值),还必须超过sum - maxInclusive * (n - 1)(因为太小的话,即使后面所有数字都取maxInclusive,它们之和还是到不了sum)。我们以此确保了每一步都是正确拆分的步骤之一,避免产生任何无效的步骤。

 递归?

 其实这道题目老赵在CSDN学生大本营中也贴出过。在那里有朋友提出这样的看法:

 递归不是传说中的最耗费资源的算法吗??怎么还用递归!

 例如有人说,计算斐波那契数列时,递归的性能非常差。但是事实上,递归本身只是一种特殊的方法调用方式,往往不是性能的关键。例如递归计算斐波那契数列性能低下,是因为重复计算的问题,我们可以使用Memoization来避免重复计算。当然,递归的确是有开销的,反复操作调用堆栈上的数据,其性能自然不如所谓“递推”。不过性能“低下”是相对的,在《Beautiful Code(中文名“代码之美”)》的第一章中就提到了一段利用递归的正则表达式匹配代码,其性能与grep相差无几,于是证明了“递归并不会会性能有太多影响”。InfoQ中文站推出过这本书的中译精选版,值得一看。

 使用递归的好处在于程序会显得非常清晰(clean code),咱都知道“make clean code fast”远比“make fast code clean”容易,使用递归将您的思路整理出来,是快速解决问题,快速优化问题的有效途径。如果递归真成了您的性能瓶颈之一,那么您可以设法将递归进行优化。例如将其优化为尾递归,或者自己编写不用递归的代码来解决问题。

 您是否可以尝试不用递归来解决这个问题呢?

原文地址:http://www.cnblogs.com/jeffreyzhao/archive/2009/06/21/1507847.html

0
相关文章