递归算法一例

chenzyyysl · 发表于 2013-2-16 16:07

本帖最后由 chenzyyysl 于 2013-2-16 16:09 编辑

原题见http://club.excelhome.net/forum.php?mod=viewthread&tid=981243&page=1#pid6713854
考虑到编程的方便，把原题的表述限定为：求一组正整数中，其和为一特定值的所有组合

分析：1：对于任一组正整数，有最小值、最大值、总和这三个参数
      2：当特定的目标值小于最小值或大于总和时，不可能产生所需要的组合；
      3：当特定的目标值等于总和时，则只有全部数据这一组合能符合要求；
      4：当特定的目标值在最小值、最大值之间时有可能找到一个数正好等于目标值
      5：当特定的目标值在最小值、总和之间时，从原数组中取出任一数，则问题可以转化为“求剩余数组，其和为‘特定值-该取出的数’的所有组合”，这个就正好符合递归算法的要求，而前面的2项又正好是退出条件；
程序见附件，SHEET1,A列为从小到大排列的一组正整数，C1为目标值，结果在SHEET2（原题的结果我的机器上跑了4分钟，6万多组合，测试时最好用少量的数组）

asdf.zip (22.84 KB, 下载次数: 258)

lxw6 · 发表于 2013-2-16 16:46

这个思路很不错，赞一个！
我把中间结果记录到数组，速度能提升32%，减少到162秒。见附件。当收藏该帖了。

chenzyyysl · 发表于 2013-2-16 17:16

不错，是快了不少，我平时不爱用全局变量，没想到这样处理。

shaowu459 · 发表于 2013-2-16 23:57

帮顶一下，应该很多人用的到

yangxhhb · 发表于 2013-4-7 21:35

惭愧，太复杂，没看懂，不过还是感谢分享！

香川群子 · 发表于 2014-8-26 13:53

本帖最后由香川群子于 2014-8-26 14:05 编辑

思路算是不错的。
经确认，对于重复值的处理结果为：
前面的数值都不会重复、但组合中最后一个数（最大数）可被重复计算。

呵呵。有趣的结果。

即，既不是完全不重复、也不是完全重复……

		自动登录	找回密码
密码			免费注册

[分享] 递归算法一例

评分

评分