这是某人给我出的一道算法题。经过考虑，给出了解法。最快的谈不上（算法无止境、人外有人），没有用递归。
还是以题目的例子说明，数字12，范围3-6。给出了5种组合。将这5种组合改写一下
3+3+3+3=3*4+4*0+5*0+6*0 记作：(4,0,0,0) 3+3+6=3*2+4*0+5*0+6*1 记作：(2,0,0,1) 3+4+5=3*1+4*1+5*1+6*0 记作：(1,1,1,0) 4+4+4=3*0+4*3+5*0+6*0 记作：(0,0,3,0) 6+6=3*0+4*0+5*0+6*2 记作：(0,0,0,2)
可以看出，本题就变成求各个数字的系数组合。求解这样的题目一般用递归（本题要求不能用递归）或者递推。
在“遍历组合算法的模块化”中，介绍了解这类题的模块化代码。如下所示：
Public Sub Traversal() Dim P() As Integer, K As Integer, IsGroup As Boolean
InitData() 注：初始化数组代码块
K = P.GetUpperBound(0)
Do If IsMatch() Then 注：判别是否满足条件的代码块 OutputAnswer() 注：输出解的代码块 End If
IsGroup = False
Do Delta(K) 注：P(K)自增加值的代码块 Do If Overflow(K) Then 注：判断P(K)是否越界的代码块 K = K - 1 Exit Do Else If K < P.GetUpperBound(0) Then K = K + 1 SetP(K) 注：依据条件设置P(K)值的代码块 Else IsGroup = True Exit Do End If
End If Loop Loop Until (K < 0 Or IsGroup = True)
Loop Until K < 0
SomeEndCode() 注：求解结束的代码块
End Sub
上面的代码相当于伪代码。还要根据本题的实际情况，进行改写。
首先，函数有输入参数：A——给定的数字；N——范围的下限；M——范围的上限
函数有返回值，以字符串数组返回每一组解
1、初始化数组的代码：
Dim i As Integer, j As Integer Dim tS() As String = {}, T As Integer = -1 Dim S As Integer
For i = 0 To M - N - 1 P(i) = 0 Next P(M - N) = Int(A / M) S = P(M - N) * M
最先想到的数组初始化的代码是所有的系数都是0，但是没有必要，最后的一个系数是和前面的系数相关的。
2、判别是否满足条件的代码块： 这个简单，S=A
3、输出解的代码块：
ReDim Preserve tS(T + 1) T += 1 tS(T) = "" For i = 0 To M - N If P(i) > 0 Then For j = 1 To P(i) tS(T) &= (i + N).ToString & "+" Next End If Next tS(T) = tS(T).Substring(0, tS(T).Length - 1) 4、P(K)自增加值的代码块： P(K) += 1
S += K + N
5、判断P(K)是否越界的代码块 这个也很简单，S>A
6、依据条件设置P(K)值的代码块 这个分两种情况，若P(K)不是最后一个系数，设置为0；是最后一个系数，设置为最大可能的组合。
If K < P.GetUpperBound(0) Then P(K) = 0 Else P(K) = IIf(S > A, 0, Int((S - A) / M)) S += P(K) * M End If
7、求解结束的代码块
把前面的解返回出去。
Return tS
至此，代码改写完毕。完整的代码如下：
Public Function Traversal(ByVal A As Integer, ByVal N As Integer, ByVal M As Integer) As String() Dim K As Integer, IsGroup As Boolean Dim P(M - N) As Integer
Dim i As Integer, j As Integer Dim tS() As String = {}, T As Integer = -1 Dim S As Integer
For i = 0 To M - N - 1 P(i) = 0 Next P(M - N) = Int(A / M) S = P(M - N) * M
K = P.GetUpperBound(0)
Do
If S = A Then
ReDim Preserve tS(T + 1) T += 1 tS(T) = "" For i = 0 To M - N If P(i) > 0 Then For j = 1 To P(i) tS(T) &= (i + N).ToString & "+" Next End If Next tS(T) = tS(T).Substring(0, tS(T).Length - 1) End If
IsGroup = False
Do P(K) += 1 S += K + N Do If S > A Then S -= (K + N) * P(K) K = K - 1
Exit Do Else If K < P.GetUpperBound(0) Then K = K + 1
If K < P.GetUpperBound(0) Then P(K) = 0 Else P(K) = IIf(S > A, 0, Int((S - A) / M)) S += P(K) * M End If Else IsGroup = True Exit Do End If
End If Loop Loop Until (K < 0 Or IsGroup = True)
Loop Until K < 0
Return tS
End Function
最新评论