ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 Excel转在线管理系统,怎么做看这里 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 高效办公必会的Office实战技巧 免费下载Excel行业应用视频
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 1821|回复: 13

[求助] 求助关于彭版剪枝代码的思路解释

[复制链接]

TA的精华主题

TA的得分主题

发表于 2013-10-18 10:10 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:递归
对于递归,目前我可以写出那个什么数列:
Function f(n)
  If n <= 1 Then
     f = n
  Else
     f = f(n - 1) + f(n - 2)
  End If
End Function
但是,看到彭版的递归代码却怎么也看不懂了:
Sub peng()
ReDim arr(1 To 65536, 1 To 1)
Call xi("", 3, 2, 0, jj, arr)
Range(Cells(1, 1), Cells(jj, 1)) = arr
End Sub
Sub xi(a, x, y, z, jj, arr)
If z > y Then Exit Sub
If Len(a) - z > x Then Exit Sub
If Len(a) = x + y Then
jj = jj + 1
arr(jj, 1) = a
End If
Call xi(a & "o", x, y, z, jj, arr)
Call xi(a & "1", x, y, z + 1, jj, arr)
End Sub
求各位达人帮助详细解释一下这代码的思想方法。
注:是求详细的思想方法,不是解释成如“jj=jj+1就是变量jj累加1”这样的翻译。
要是再能将此思想方法转为非递归形式(如果可以转的话)那就更好了。谢谢各位达人!
为了学习哈{:soso_e183:}

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-10-20 12:54 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2013-10-20 13:08 | 显示全部楼层
你这个递归代码有什么作用?

生成5选2的二进制组合?
Combin(5,2)=10


TA的精华主题

TA的得分主题

 楼主| 发表于 2013-10-20 13:24 | 显示全部楼层
本帖最后由 m_n_j001 于 2013-10-20 13:26 编辑

首先感谢美女达人的关注与回复!
此代码完成的功能是:随意给出x个"o"、y个"1",递归得到这x+y个字符的全排列。不是得到有多少种,而是把每种排列列出来
全排列的程序很多,大体上我也可写出一两段。
但是,彭版的这段代码中的“剪枝”是怎么回事,看了很久始终不得其要领,故在此开贴求助,望各位达人赐教。

TA的精华主题

TA的得分主题

发表于 2013-10-20 14:21 | 显示全部楼层
凑合看看
  1. Sub peng()
  2.     ReDim arr(1 To 65536, 1 To 1)
  3.     Call xi("", 3, 2, 0, jj, arr)
  4.     Range(Cells(1, 1), Cells(jj, 1)) = arr
  5. End Sub
  6. Sub xi(a, x, y, z, jj, arr) 'z记录a中1的个数,逐位组合
  7.     If z > y Then Exit Sub '超过y个1退出
  8.     If Len(a) - z > x Then Exit Sub '超过x个o退出
  9.     If Len(a) = x + y Then '合成字串长度=x+y
  10.         jj = jj + 1
  11.         arr(jj, 1) = a
  12.     End If
  13.     Call xi(a & "o", x, y, z, jj, arr) '当前位组合一个o,而后下一位
  14.     Call xi(a & "1", x, y, z + 1, jj, arr) '当前位组合一个1,而后下一位
  15. End Sub
复制代码

TA的精华主题

TA的得分主题

发表于 2013-10-20 18:47 | 显示全部楼层
本帖最后由 香川群子 于 2013-10-20 18:59 编辑

呵呵,那这就是一个简单的递归组合算法。

看我的代码,是否理解起来更容易一些?

  1. Dim jg(), m, n, k '定义公共变量以便在递归过程中传递数据

  2. Sub kagawa()
  3.    
  4.     n = 2 'y    → 需要得到组合结果="1"的个数
  5.     m = 5 'x+y  → 字符总长度("o"和"1"的总个数)
  6.    
  7.     k = WorksheetFunction.Combin(m, n) '计算得到组合结果总数k
  8.     ReDim jg(1 To k, 1 To 1) '定义存储k个结果的数组jg
  9.    
  10.     k = 0 '记录结果的k值初始化=0
  11.     s = String(m, "o") '结果字符串s初始化 (从="ooooo"开始)
  12.     Call dgZH(s, 0, 0) '调用递归组合过程
  13.    
  14.     [a1].Resize(k) = jg '输出结果到工作表
  15. End Sub


  16. Sub dgZH(s, i, t) '递归组合过程
  17.    '参数s=组合状态结果字符串,i为组合抽取位置,t为组合抽取个数


  18.     If t = n Then    '当组合抽取个数=n时可结束递归
  19.         k = k + 1    '结果数k+1
  20.         jg(k, 1) = s '结果字符串s写入结果数组jg
  21.         Exit Sub     '结束本次递归
  22.     End If
  23.    
  24.     For j = i + 1 To m - n + t + 1 '遍历循环进行组合
  25.         Mid(s, j, 1) = "1"         '当前位置j写入结果"1"
  26.         Call dgZH(s, j, t + 1)     '当前递归状态进入下一步递归
  27.         Mid(s, j, 1) = "o"         '递归退回时把该位置"1"复位为"o"
  28.     Next
  29. End Sub
复制代码

TA的精华主题

TA的得分主题

发表于 2013-10-20 18:56 | 显示全部楼层
去掉注释,加入变量定义后的代码如下:
  1. Dim jg$(), m&, n&, k&
  2. Sub kagawa1()
  3.     Dim s$
  4.     n = 2: m = 5: k = WorksheetFunction.Combin(m, n)
  5.     ReDim jg$(1 To k, 1 To 1)
  6.     k = 0: Call dgZH(String(m, "o"), 0, 0)
  7.     [a1].CurrentRegion = "": [a1].Resize(k) = jg
  8. End Sub
  9. Sub dgZH(s$, i&, t&)
  10.     Dim j&
  11.     If t = n Then k = k + 1: jg(k, 1) = s: Exit Sub
  12.     For j = i + 1 To m - n + t + 1
  13.         Mid(s, j, 1) = "1": Call dgZH(s, j, t + 1): Mid(s, j, 1) = "o"
  14.     Next
  15. End Sub
复制代码

TA的精华主题

TA的得分主题

发表于 2013-10-20 19:06 | 显示全部楼层
如果像彭版那样,不使用公用变量,而是直接在递归中传递变量的话,代码如下:
  1. Sub kagawa2()
  2.     n = 2: m = 5: k = WorksheetFunction.Combin(m, n): ReDim jg(k)
  3.     Call dgZH(String(m, "o"), 0, 0, m, n, 0, jg)
  4.     [a1].CurrentRegion = "": [a1].Resize(k) = Application.Transpose(jg)
  5. End Sub
  6. Sub dgZH(s, i, t, m, n, k, jg)
  7.     If t = n Then jg(k) = s: k = k + 1: Exit Sub
  8.     For j = i + 1 To m - n + t + 1
  9.         Mid(s, j, 1) = "1": Call dgZH(s, j, t + 1, m, n, k, jg): Mid(s, j, 1) = "o"
  10.     Next
  11. End Sub
复制代码
不过,一般说定义使用公用变量会比较好。递归内存占用少一些。

TA的精华主题

TA的得分主题

发表于 2013-10-20 19:17 | 显示全部楼层
我的递归思路是:

1. 从j位置开始循环 (j=i+1=0+1=1,即从位置1开始)
2. 写入"1"
3. 进入下一层递归 (j位置传递下去),即又从步骤1开始

在下一层递归是这样子:
2-1. 从j位置开始循环 (j=1+1=2,即从位置2开始)
2-2. 写入"1"
2-3. 进入下一层递归 (j位置传递下去),即又从步骤1开始

……
这样位置从1开始一直到递归到最后一个位置结束。
过程中如果统计t的个数已经达到 t=n 即等于抽取个数n时,即可终止本次递归 (楼主把这叫做剪枝?呵呵……)

然后退出递归时,回到下一语句时顺便把j位置写入的"1"复位为"o"即可。


…………
就是这么简单。


彭版的递归组合代码,退出条件和进入递归的条件都不止一个,相对我的代码来说比较复杂了。

但彭版的递归代码没有使用For循环,因此是充分利用了递归的特性。


…………
但是从算法理解度和实际计算效率来说,还是我的循环递归组合代码更好一些。


TA的精华主题

TA的得分主题

发表于 2013-10-20 19:27 | 显示全部楼层
我的代码,递归过程调用=15次 (n=2,m=3时)
而彭版递归过程调用了=84次
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关闭

最新热点上一条 /1 下一条

关注官方微信,高效办公专列,每天发车

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2019-8-25 18:02 , Processed in 0.089003 second(s), 12 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表