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

m_n_j001 · 发表于 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:}

m_n_j001 · 发表于 2013-10-20 12:54

真难{:soso_e117:}

香川群子 · 发表于 2013-10-20 13:08

你这个递归代码有什么作用？

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

m_n_j001 · 发表于 2013-10-20 13:24

本帖最后由 m_n_j001 于 2013-10-20 13:26 编辑

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

yangyangzhifeng · 发表于 2013-10-20 14:21

凑合看看

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) 'z记录a中1的个数，逐位组合
If z > y Then Exit Sub '超过y个1退出
If Len(a) - z > x Then Exit Sub '超过x个o退出
If Len(a) = x + y Then '合成字串长度=x+y
jj = jj + 1
arr(jj, 1) = a
End If
Call xi(a & "o", x, y, z, jj, arr) '当前位组合一个o，而后下一位
Call xi(a & "1", x, y, z + 1, jj, arr) '当前位组合一个1，而后下一位
End Sub

复制代码

香川群子 · 发表于 2013-10-20 18:47

本帖最后由香川群子于 2013-10-20 18:59 编辑

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

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

Dim jg(), m, n, k '定义公共变量以便在递归过程中传递数据
Sub kagawa()
n = 2 'y → 需要得到组合结果="1"的个数
m = 5 'x+y → 字符总长度("o"和"1"的总个数)
k = WorksheetFunction.Combin(m, n) '计算得到组合结果总数k
ReDim jg(1 To k, 1 To 1) '定义存储k个结果的数组jg
k = 0 '记录结果的k值初始化=0
s = String(m, "o") '结果字符串s初始化 (从="ooooo"开始)
Call dgZH(s, 0, 0) '调用递归组合过程
[a1].Resize(k) = jg '输出结果到工作表
End Sub
Sub dgZH(s, i, t) '递归组合过程
'参数s=组合状态结果字符串,i为组合抽取位置,t为组合抽取个数
If t = n Then '当组合抽取个数=n时可结束递归
k = k + 1 '结果数k+1
jg(k, 1) = s '结果字符串s写入结果数组jg
Exit Sub '结束本次递归
End If
For j = i + 1 To m - n + t + 1 '遍历循环进行组合
Mid(s, j, 1) = "1" '当前位置j写入结果"1"
Call dgZH(s, j, t + 1) '当前递归状态进入下一步递归
Mid(s, j, 1) = "o" '递归退回时把该位置"1"复位为"o"
Next
End Sub

复制代码

香川群子 · 发表于 2013-10-20 18:56

去掉注释，加入变量定义后的代码如下：

Dim jg$(), m&, n&, k&
Sub kagawa1()
Dim s$
n = 2: m = 5: k = WorksheetFunction.Combin(m, n)
ReDim jg$(1 To k, 1 To 1)
k = 0: Call dgZH(String(m, "o"), 0, 0)
[a1].CurrentRegion = "": [a1].Resize(k) = jg
End Sub
Sub dgZH(s$, i&, t&)
Dim j&
If t = n Then k = k + 1: jg(k, 1) = s: Exit Sub
For j = i + 1 To m - n + t + 1
Mid(s, j, 1) = "1": Call dgZH(s, j, t + 1): Mid(s, j, 1) = "o"
Next
End Sub

复制代码

香川群子 · 发表于 2013-10-20 19:06

如果像彭版那样，不使用公用变量，而是直接在递归中传递变量的话，代码如下：

Sub kagawa2()
n = 2: m = 5: k = WorksheetFunction.Combin(m, n): ReDim jg(k)
Call dgZH(String(m, "o"), 0, 0, m, n, 0, jg)
[a1].CurrentRegion = "": [a1].Resize(k) = Application.Transpose(jg)
End Sub
Sub dgZH(s, i, t, m, n, k, jg)
If t = n Then jg(k) = s: k = k + 1: Exit Sub
For j = i + 1 To m - n + t + 1
Mid(s, j, 1) = "1": Call dgZH(s, j, t + 1, m, n, k, jg): Mid(s, j, 1) = "o"
Next
End Sub

复制代码

不过，一般说定义使用公用变量会比较好。递归内存占用少一些。

香川群子 · 发表于 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循环，因此是充分利用了递归的特性。

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

香川群子 · 发表于 2013-10-20 19:27

我的代码，递归过程调用=15次（n=2,m=3时）
而彭版递归过程调用了=84次

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

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