寻求算法

zhixin1007 2003-10-23 01:10:01

从1到m一共m个自然数中任取n个（2n<=m）
并且这n个数中任意两个不相连，（例如3，4就算相连。）
共有多少种取法。

要求不能使用递归算法，循环嵌套不能超过两层。
多谢了

...全文

53 17 打赏收藏转发到动态举报

写回复

用AI写文章

17 条回复

切换为时间正序

请发表友善的回复…

发表回复

zhixin1007 2003-11-02

打赏
举报

northwolves(野性的呼唤) 对了。。下面是我从老师那里拿来的SOLUTION
总结了一下

另外：基于计算机的运行方式，能不用递归千万别用，递归只是给程序员省事，给机器加负担了

SOLUTION
从 1~m 这m个连续自然数中选出n个，不出现连续的取法有多少种。（例如1，4，5，8即算出现连续）
要求给出算法。

这是一个计算机里的问题，最直接的办法就是利用计算机强大的计算与存储功能 —— 枚举
呵呵，很笨的方法。
稍微有点头脑的人就不会枚举了，例如我（很不谦虚的说）
我是这么想的，假设不出现连续取法函数为f(m,n)，显然的m>=2n-1时才有f(m,n)>0,且初始条件f(m,1)=m。
现在将取出的n个数按照升序排列。
当第一个数为1时，有f(m-2,n-1)种取法，也就是相当于在3~m这m-2个数中取出n-1个不连续的取法个数
当第一个数为2时，有f(m-3,n-1)种
……
所以f(m,n)=f(m-2,n-1)+f(m-3,n-1)…… +f(2n-3,n-1)
已然构造出了递归算法，于是f(m,n)可求。
当然，这个算法的时间复杂度绝对是对不起观众的，而且应用了看着漂亮但让计算机活受罪的递归算法（计算机每调用一个函数都要生成相应的函数空间，所以递归调用会生成一大串函数空间，吞噬内存降低机器速度与效率）。这时有个人指出我们可以用f[m][n]矩阵来代替f(m,n)这个麻烦的函数，方法是先把f[][1]都赋上值（初始条件），然后利用上面的式子来求f[][2]直到求出f[m][n]，这应该算是递归的改良方法，如果说递归是把一个大箱子拖着走，那这种方法则是把这要命的箱子推着走（这比喻不甚恰当，推和拖在物理上做的功一样，但在这里确实省了一大片的存储空间），也就是递推算法。
说来说去，上面的方法都是不明智的，下面看看我们一个平时古里古怪老说匪夷所思的话的年轻老师给出的解决方法，这个老师，呵呵，长的很有个性，耳朵尖尖的，象……加菲猫
我们现在从1~m中取出了n个不连续的数为a1,a2~an（升序排列）,现在我们补充a0=0,a(n+1)=m
然后令xi=ai-a(i-1) i=1~(n+1)
于是得到一个方程 x1+x2+x3+……x(n+1)=a(n+1)-a0=m
又因为a1~an互不连续，所以x1>=1,x2~xn>=2.x(n+1)>=0
然后我们再令y1=x1,yi=xi-1 (i=2~n) ,y(n+1)=x(n+1)+1
所以有方程 y1+y2+……+y(n+1)=m-n+2 其中的yi>=1 呵呵，典型的丢番图方程。
而我们现在感兴趣就是这个方程有多少组正整数解。
这么想吧，我们在1~m-n+1这系列连续数中任取n个不相等的，为b1~bn然后补充b0=0,b(n+1)=m-n+2
然后得到的yi=bi-b(i-1)就是上面方程的一组解，不是吗？所以，上面那个方程的正整数解有C(m-n+1,n)种。当然，这也是取法的种数。学过C语言的人都看出来了，计算C(m-n+1,n)只需要一个单循环，哈哈哈哈哈，解得不错吧？！

northwolves 2003-11-01

打赏
举报

前边我的帖子结果计算错误。但结果c(m-n+1,n)应该没错，干么不用递归？
Private Sub Command1_Click()
MsgBox getcount(8, 3)
End Sub
Function comb(ByVal m As Integer, ByVal n As Integer) As Long
If n > m Then Exit Function
If m = 1 And n = 0 Then comb = 1
If m = 1 And n = 1 Then comb = 1
If m > 1 Then comb = comb(m - 1, n - 1) + comb(m - 1, n)
End Function
Function getcount(ByVal m As Integer, ByVal n As Integer) As Long
If n > m / 2 Then Exit Function
getcount = comb(m - n + 1, n)
End Function
如果要列出所有取法我觉得还是递归好些。

taosihai1only 2003-11-01

打赏
举报

递归好些

佛的光辉 2003-10-31

打赏
举报

Option Explicit

Public Function GetCount(M As Long, n As Long) As Long
Dim lM1 As Long, lM2 As Long
Dim i1 As Long, i2 As Long, i3 As Long
Dim Count As Long, Count1 As Long, Count2 As Long, Count3 As Long
On Error GoTo ErrHandle
If (M <= 0) Or (n <= 0) Or (n * 2) > M Then
MsgBox "错误的参数"
GoTo ErrHandle
End If
lM1 = M \ 2
lM2 = M - lM1
Count = fact(lM2) / (fact(lM2 - n) * fact(n))
For i1 = 1 To n
Count1 = fact(lM1) / (fact(lM1 - i1) * fact(i1))
Count3 = 0
For i2 = i1 + 1 To (2 * i1) Mod (lM2 + 1)
Count2 = fact(lM2 - i2) / (fact((lM2 - i2) - (n - i1)) * fact(n - i1))
Count3 = Count3 + Count2
Next i2
Count = Count + Count1 * Count3
Next i1
GetCount = Count
Exit Function
ErrHandle:
GetCount = 0
End Function

Function fact(ByVal x As Long) As Long '求阶乘
fact = 1
Dim i As Long
For i = 1 To x
fact = fact * i
Next
End Function
Private Sub Command1_Click()
MsgBox GetCount(15, 7)
End Sub

chenyu5188 2003-10-31

打赏
举报

UP楼上的。

northwolves 2003-10-31

打赏
举报

应该不难, 大家看看对否？
在[，1，2，3，4，5，。。。，m，] 的m+1个逗号位置中取出n个两逗号之间的数，按照要求，显然只能从其中m+1-n个位置中取，故共有c(m-n+1,n)种，即（m-n+1)!*(m+2-2n)!/n!

Function fact(ByVal x As Long) As Long '求阶乘
fact = 1
Dim i As Long
For i = 1 To x
fact = fact * i
Next
End Function
Function comb(ByVal m As Integer, ByVal n As Integer) As Long '求组合
comb = fact(m - n + 1) * fact(m + 2 - 2 * n) / fact(n)
End Function

Private Sub Command1_Click() '计算15个数中选7个的方法
Const m = 15
Const n = 7
MsgBox comb(m, n)
End Sub

佛的光辉 2003-10-31