ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

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

[分享]最接近π值的5位分数的一种递归算法

[复制链接]

TA的精华主题

TA的得分主题

发表于 2007-8-25 01:09 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:递归

这个问题,是论坛的一位朋友提出来的。最早由狼版给出了答案。问题如下:
求一个分数,分子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, 下载次数: 193)

TA的精华主题

TA的得分主题

发表于 2007-8-25 07:30 | 显示全部楼层

分析得很好,学习.

主要是难以找到很好的出口来提高效率

TA的精华主题

TA的得分主题

发表于 2007-8-25 07:46 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2007-8-25 08:52 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2007-8-25 11:44 | 显示全部楼层

Sub peng()
    Pi = 3.141592654
    ReDim arr(1 To 3)
    arr(1) = 10
    For i = 31415 To 100000
        If Abs(i / Fix(i / Pi) - Pi) < arr(1) Then
            arr(1) = Abs(i / Fix(i / Pi) - Pi)
            arr(2) = i
            arr(3) = Fix(i / Pi)
        End If
    Next i
    MsgBox (arr(2) & "/" & arr(3) & " =" & arr(2) / arr(3))
End Sub

怎么和我算的结果不一样呢31595/10057 =3.14159292035398

TA的精华主题

TA的得分主题

发表于 2007-8-25 12:46 | 显示全部楼层
QUOTE:
以下是引用彭希仁在2007-8-25 11:44:40的发言:

Sub peng()
    Pi = 3.141592654
    ReDim arr(1 To 3)
    arr(1) = 10
    For i = 31415 To 100000
        If Abs(i / Fix(i / Pi) - Pi) < arr(1) Then
            arr(1) = Abs(i / Fix(i / Pi) - Pi)
            arr(2) = i
            arr(3) = Fix(i / Pi)
        End If
    Next i
    MsgBox (arr(2) & "/" & arr(3) & " =" & arr(2) / arr(3))
End Sub

怎么和我算的结果不一样呢31595/10057 =3.14159292035398

彭兄思路不错,修改如下:

Sub peng()
Dim pi As Single, diff As Single, i As Long, j As Long, temp As Long, s() As Byte, n As Byte, result As String, tt As Single
tt = Timer
pi = 4 * Atn(1)
diff = 1
    For i = 31425 To 98765
    ReDim s(9)
    For j = 1 To 5
    s(Mid(i, j, 1)) = 1
    Next
    If WorksheetFunction.Sum(s) = 5 Then
         temp = Fix(i / pi)
         For j = 1 To 5
           s(Mid(temp, j, 1)) = 1
         Next
        If WorksheetFunction.Sum(s) = 10 Then
            If Abs(i / temp - pi) < diff Then
              diff = Abs(i / temp - pi)
             result = i & "/" & temp
            End If
        End If
   End If
Next
MsgBox result, vbInformation, "总计用时" & Timer - tt & "秒!"
End Sub

TA的精华主题

TA的得分主题

发表于 2007-8-25 14:17 | 显示全部楼层

求一个分数,分子5位数(第1位不是0),分母也是5位数(第1位不是0),分子和分母这10个数正好由0到9这10个数字组成(不缺也不重复)。我想要最接近π值的那个分数。

 

不好意思,看错题目了。闭门思过去

[em04][em04]

TA的精华主题

TA的得分主题

发表于 2007-8-25 14:36 | 显示全部楼层

Public pi
Public x
Public y
Public z
Public k As Long
Public st
Sub peng()
    t = Timer
    pi = 3.141592654
    x = 10
    st = 0
    Call caii("", 0)
    MsgBox (y & "/" & z & "=" & y / z & "递归" & st & "次,耗时" & Timer - t & "秒")
End Sub
Sub caii(a, i)
    st = st + 1
    m = 0
    If i = 1 Then m = 3
    For j = m To 9
        If Not (a Like "*" & j & "*") Then
            If i + 1 = 5 Then
                k = a & j
                If k > 31415 Then
                    If Abs(k / Fix(k / pi) - pi) < x Then
                        h = k & Fix(k / pi)
                        For n = 0 To 9
                            If Not (h Like "*" & n & "*") Then Exit For
                        Next n
                        If n = 10 Then
                            x = Abs(k / Fix(k / pi) - pi)
                            y = k
                            z = Fix(k / pi)
                        End If
                    End If
                End If
            Else
                Call caii(a & j, i + 1)
            End If
        End If
    Next j
End Sub

[此贴子已经被作者于2007-8-25 15:21:27编辑过]

TA的精华主题

TA的得分主题

 楼主| 发表于 2007-8-25 17:17 | 显示全部楼层

彭大侠的思路非常不错。先知分子,后求分母。

但是,我这里有一点疑惑,觉得彭大侠的程序,是为3.1415927量身定作的。

比如这个时候我们不求逼近3.1415926535的分数了,按照我们程序的设计,我们可以求最逼近于任何数值的符合条件的5位分数。好了,现在我们抛开π的束缚,我们来另外假定一个数字,我们求逼近于3.142,3,1416,3.14159的分数,彭大侠的结果就与我的解法解出来的结果不同了。当我们将分数设为3.1415927甚至更多位后,彭大侠的结果才与我的一致起来。3.142后的数值均有差异,彭大侠的程序并不能正确求出最逼近于这些情况的分数。

话罗索了太多,就是感觉彭大侠的这种解法很奇特,总觉得有种说不出来的感觉。我感觉问题应该出在取整上。即fix这个语句。仅仅是感觉,不知道对不对。

TA的精华主题

TA的得分主题

发表于 2007-8-25 19:03 | 显示全部楼层
QUOTE:
以下是引用yier_fang在2007-8-25 17:17:09的发言:

彭大侠的思路非常不错。先知分子,后求分母。

但是,我这里有一点疑惑,觉得彭大侠的程序,是为3.1415927量身定作的。

比如这个时候我们不求逼近3.1415926535的分数了,按照我们程序的设计,我们可以求最逼近于任何数值的符合条件的5位分数。好了,现在我们抛开π的束缚,我们来另外假定一个数字,我们求逼近于3.142,3,1416,3.14159的分数,彭大侠的结果就与我的解法解出来的结果不同了。当我们将分数设为3.1415927甚至更多位后,彭大侠的结果才与我的一致起来。3.142后的数值均有差异,彭大侠的程序并不能正确求出最逼近于这些情况的分数。

话罗索了太多,就是感觉彭大侠的这种解法很奇特,总觉得有种说不出来的感觉。我感觉问题应该出在取整上。即fix这个语句。仅仅是感觉,不知道对不对。

FIX总是往下取整的,即使1.99也要取1,改成ROUND就可以了.

您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关注官方微信,每天学会一个新技能

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

GMT+8, 2019-9-18 20:04 , Processed in 0.092299 second(s), 17 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

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

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

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