|
这个问题，是论坛的一位朋友提出来的。最早由狼版给出了答案。问题如下：
求一个分数，分子5位数（第1位不是0），分母也是5位数（第1位不是0），分子和分母这10个数正好由0到9这10个数字组成（不缺也不重复）。我想要最接近π值的那个分数。 递归是个很让人头疼的过程。头疼的过程在于总结出递归过程中的相似流程，其他的交给计算机去工作就行了。因此，递归一旦开始，我们就不知道它要执行多少步会得到结果了。但我们要确信的一点是，计算机有不达目的誓不罢休的精神，只要不找到我们设定的解，也就是那个递归结束的条件，它就会永远执行下去的。 递归可以解决很多有重复性流程的难题。比如，在这个例子中。让谁一下子说出这个解都是不可能的，我们只有交给计算机去穷举遍历来完成这个工作。 假设我们现在已经在递归的某一层中了。那么这一层要干什么事情呢？ 首先，我们要看分子分母是否被赋值了，如果没有赋值，就是要想办法给分子分母赋值，分子分母各赋一位，共有72种组合。这个过程，我们用循环来赋值。赋值完成后，就要调用递归，进入下一层了。 再次，我们要看分子分母多少位了。如果没有到5位，我们就要继续给分子与分母赋值。分子分母再各赋一位。当然，数字是不能重复的。除出在前面用过的2位数字，现在还有8个数字可以用。要赋完全部的分子分母，即0－9这十位数全部用上，一共组合会有（9×8×8×7×6×5×4×3×2×1）种。赋值完成，调用递归。 三者，如果分子分母已经够了五位了，那么就要对这个分数的值进行检验了。检验这个值与其他的“前辈”们（是指比它还早到达这个检验点的递归过程）相比，谁最小，如果它够小，那么它就要排到前面去了。后来者就要跟它相比了。 如此，我们的递归过程就好像完成了。 好，下面我们开始写程序吧。 我们先要定义几个公用变量。它们的作用是分别记录到递归执行到当前为止，最接近π的分数的分子与分母，记录与π的差。 Dim lngFM As Long'保存分母 Dim lngFZ As Long'保存分子 Const PI = 3.1415926535 Dim dbl As Double'分数与PI的差值 然后就是下面的递归程序了。 Sub fs(ByRef FM As String, ByRef FZ As String) Dim i, j As Long If Len(FM) = 0 Then For i = 1 To 9 For j = 1 To 9 If i <> j Then Call fs(CStr(i), CStr(j)) End If Next j Next i ElseIf Len(FM) < 5 Then For i = 0 To 9 If InStr(FM & FZ, i) = 0 Then For j = 0 To 9 If InStr(FM & FZ & i, j) = 0 Then Call fs(FM & i, FZ & j) End If Next j End If Next i Else If Abs((FZ / FM) - PI) < dbl Then lngFM = FM lngFZ = FZ dbl = Abs((FZ / FM) - PI) End If End If End Sub 明白了我前面用语言叙述的部分，这段小小的程序是一点也不难理解的。它只是对前面的语言的程序化罢了。 好了，我们需要另外写一个程序来调用这个递归。 Sub cnft() dbl = 3.1415926535 Call fs("", "") Debug.Print lngFZ Debug.Print lngFM Debug.Print dbl End Sub 剩下的工作，就是坐下来，等着看这个程序什么时候运行完成。它运行的有点慢。为了知道它到底运行了多少次递归过程，我们可以在递归的一开始就放入一个变量，每运行一次加1,以记录递归的次数。我们就用KKK来标记吧。在我的附件里已经加入了这个变量了。好，运行一下，看它执行了多少次操作。好家伙，等了好久呀，一共执行了4479625次递归，怪不得这么慢呢。 有什么办法让它快起来呢？我早就说过，递归有一种不达目的誓不罢休的精神，所有的递归，最后都走到尽头与那个最小值的前辈进行比较，甚至于，那些一看就知道不可能达标的家伙也在不知羞耻地前进着。比如9876/1234，它很显然不如9876/2134更加接近π，其实从第一位分数赋值完毕，即9/1后，我们就可以判它的死刑了。如何让这些家伙知难而退呢？这就要用到出口了。 递归可以有多个出口。这个太方便了，也为我们减少递归的次数提供了可能。 我们知道对于一个分数x/y来说，无论在它的分子与分母后面添加多少位数值，它数值的变动区域在( (x-1)/(y+1),(x+1)/(y-1))。因此，我们完全可以对每一次赋值完成后的数值先进行一次检验，看它数值的变动范围是否包括π。不包括的就直接PASS掉吧。这就是一个出口条件，因此，我们在每次递归的前面加上下列语句 If ((FZ - 1) / (FM + 1)) > PI Then Exit Sub If FM = 1 Then If ((FZ + 1) / (FM)) < PI Then Exit Sub Else If ((FZ + 1) / (FM - 1)) < PI Then Exit Sub End If 相信，这次的运行速度会令你比较满意吧。一共调用递归8755次。 我们的解也得到了。分子是85910,分母是27346。 我们还可以设置人工的出口，这个出口是根据我们的意愿来的，当然，出口的随意设置有可能取不到正确的解。我们试着设一个人工的出口，这个出口的设置，是建立在我们得到的这个解上。解的值为3.14159292,因此我们要求在任何一个递归层次上，分数的值一定要大于等于3,但它要小于等于4。将这个条件设一下，替换上面的出口语句。 If FZ / FM < 3 Then Exit Sub If FZ / FM > 4 Then Exit Sub 再运行一下，递归进行了126123次。当然速度也是可以让人满意的。大家可以在我的附件表格里试着更改数据的上限与下限试试，看看在什么样的情况可以看到正确的值，什么样的情况下仅得到相对满意的值。 通过上面一大堆的讨论，可见，出口的设置是非常重要的。真正的递归高手，我相信对于出口的设置也是非常精心的。 附件里的程序做了相应的修改，也加入了一个窗体的递归过程提示，但打开它以后，速度会慢得好多好多。默认关闭，不建议打开。 祝大家用递归用得快乐。
atcTEjUR.rar
(14.47 KB, 下载次数: 227)
| 
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2007-8-25 01:09
楼主