设为首页收藏本站Access中国

Office中国论坛/Access中国论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

返回列表 发新帖
查看: 29476|回复: 68
打印 上一主题 下一主题

[模块/函数] 【新手进阶】之七:递归算法

[复制链接]
跳转到指定楼层
1#
发表于 2012-3-10 11:43:50 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
       在谈递归算法之前,不得不提的是斐波纳契(Fibonacci)数列。生于十二世纪的斐波纳契(Leonardo Fibonacci)曾提到这样一个问题:有一对兔子,如果每个月生一对小兔子,而刚生下来的兔子两个月后同样每个月生一对小兔子,那么,一对兔子一年内总共能生下几对兔子?
      1……第一个月
      1……第二个月
      2……第三个月,产下第一只兔子(仔兔的第一个月)。
      3……第四个月,产下第二只兔子(仔兔的第二个月)。
      5……第五个月,产下第三只兔子,仔兔产下第一只兔子(仔兔的第三个月)。
      ……………………………………………………………………
     于是得到这样一个数列:1,1,2,3,5,8,13,21……这在数学上解法很多,通项公式是:an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n},并由此引出了黄金比例等等。当我们把通项公式写成程序则得到以下函数:
  1. Function GetF(N As Long)
  2. GetF = (Sqr(5) / 5) * (((1 + Sqr(5)) / 2) ^ N - ((1 - Sqr(5)) / 2) ^ N)
  3. End Function
复制代码
我们需要获取具体值(例如a5)时,就可以直接调用了:
  1. Sub Test()
  2. Debug.Print GetF(5)
  3. End Sub
复制代码
显然,数学不太好的盆友们,一时间未必能推导出通项公式,可如果恰好需要去完成这项任务,该怎么办呢?我们只能使用反推法:从数列中可以看得出来,后一项是前面两项之和。先得到最后一项,再得到倒数第二和倒数第三项,然后再继续往前推,直至得到第一项和第二项。于是整个结果就出来了。
这就是程序上最常用的递归思想。现在我们开始写函数:
  1. Function Fibonacci(N As Long)
  2. If N = 1 Or N = 2 Then Fibonacci = 1
  3. If N >= 3 Then Fibonacci = Fibonacci(N - 1) + Fibonacci(N - 2)
  4. End Function
复制代码
这显然比用通项公式解答起来简单多了。以N=4时为例,运行过程大体如下:
      Fibonacci(4)→Fibonacci(3)+Fibonacci(2)→Fibonacci(2)+Fibonacci(1)+Fibonacci(2)→1+1+1=3
      记得前些日子ycxchen提及,在Access中这些是如何应用的。其实这个算法在Access里也是可以用得上的,常见于树控件中。Kangking同志曾在《程序界面兼工具栏、树、状态栏、页标签及进度条等控件的应用》里就用过它来展开子节点,有兴趣的版友可以去看看。
       这里给一个比较简单的作业,用递归思想写一个阶乘的函数。

游客,如果您要查看本帖隐藏内容请回复

【新手入门】之一:If分支语句
【新手入门】之二:分支语句总结
【新手入门】之三:循环语句For
【新手入门】之四:循环语句Do和死循环
【新手入门】之五:公共变量与传址过程、传值过程
【新手入门】之六:“悲欢离合总无情”——浅谈Split和Join
【新手入门】之七:嵌套与并列——再谈If流程问题
【新手入门】之八:“连就连”——浅谈“&”和“+”连接符的区别

【新手入门】之九:从百钱百鸡谈起——浅谈“规划求解”兼答lingjiang问
【新手入门】之十:书到用时方恨少——自定义菜单(Access 2003)的制作
【新手入门】之十一:浅谈ADO之序言
【新手入门】之十二:浅谈ADO之Connection
【新手入门】之十三:浅谈ADO之Conmmand(上)
【新手入门】之十四:浅谈ADO之Command(下)
【新手入门】之十五:浅谈ADO之Recordset(上)
【新手入门】之十六:浅谈ADO之Recordset(下)
【新手入门】之十七:浅谈列表框的使用
【新手入门】之十八:双击列表框修改数据
【新手入门】之十九:从“书与女友恕不外借”谈起——浅谈“Bookmark”的使用
【新手入门】之二十:“书与书签”——bookmark属性答疑
【新手入门】之二十一:记录集的“凌迟”——逐条导出记录集

【新手进阶】之一:基础算法(一)
【新手进阶】之二:基础算法(二)
【新手进阶】之三:基础算法(三)
【新手进阶】之四:基础算法(四)
【新手进阶】之五:排序搜索(一)
【新手进阶】之六:排序搜索(二)
【新手进阶】之七:递归算法
【新手进阶】之八:冒泡排序
【新手进阶】之九:浅谈不绑定数据源操作记录
【新手进阶】之十:工作日的计算
【新手进阶】之十一:“庖丁解牛”和“纪昌学射”——浅谈表格式文本数据的导入
【新手进阶】之十二:从四脚腾空的奔马谈起——原来界面可以这样设计
【新手进阶】之十三:Outlook风格导航界面
【新手进阶】之十四:仓库管理系统

本帖被以下淘专辑推荐:

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏3 分享分享 分享淘帖1 订阅订阅
2#
发表于 2012-3-10 12:05:12 | 只看该作者
第一个学习!
3#
发表于 2012-3-10 12:10:54 | 只看该作者
学习
4#
发表于 2012-3-10 13:34:33 | 只看该作者
有兴趣,看看。
5#
发表于 2012-3-10 13:41:55 | 只看该作者
学习学习学习


6#
发表于 2012-3-10 13:53:42 | 只看该作者
那个数列还真没听说过.挺复杂的.其实在生活中类递归的例子真有,如常说的:从前有座山,山上有做庙,庙里有个老和尚在给小和尚讲故事,讲的什么故事呢?从前有座山,山上有做庙,庙里有个老和尚在给小和尚讲故事,......
记得偶上小学时,班里有个同学特有才,那时偶根本不知道这叫有才.他写了篇作文,讲述的是他与父亲搬砖,"搬了一块又一块,搬了一块又一块,搬了一块又一块,.......",直到达到老师要求的字数后才停止了调用.当时这篇作文被老师当众批评了.我学编程后才知道那同学使用的是递归

点评

为什么不是简单的循环语句呢?  发表于 2012-3-11 11:30
7#
发表于 2012-3-10 16:21:36 | 只看该作者
学习了,谢谢。
8#
发表于 2012-3-10 16:41:18 | 只看该作者
学习!
9#
发表于 2012-3-11 12:48:19 | 只看该作者
本帖最后由 风中漫步 于 2012-3-11 13:48 编辑

roych  为什么不是简单的循环语句呢?

递归的特点是自己调用自己.

斑竹讲到这我也就跟进了,这用循环也可解决的.可能我理解的会有偏差,还请斑竹批评指正了.
这个我对低归的理解,请大家批评:

Function by(zs As String) As Long
  If Len(zs) > 100 Then   Exit Function
  Text1 = zs
  zs = zs + "搬了一块又一块,"
  Call by(zs)
End Function
10#
发表于 2012-3-11 20:25:00 | 只看该作者
厉害,旁征博引,说的很清楚,谢谢!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|站长邮箱|小黑屋|手机版|Office中国/Access中国 ( 粤ICP备10043721号-1 )  

GMT+8, 2024-11-15 01:33 , Processed in 0.101937 second(s), 36 queries .

Powered by Discuz! X3.3

© 2001-2017 Comsenz Inc.

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