搜索
当前位置: 678彩票官网 > 递归块编码 >

求公式的递归函数

gecimao 发表于 2019-04-18 14:21 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  函数值,例如阶乘函数和Fibonacci函数;第二类问题具有递归特征,目的可能是求

  出满足某种条件的操作序列,例如Hanoi塔和八皇后问题。第一类问题的程序设计是

  简单的、机械的,而第二类问题则不然,由于涉及面广,没有统一的规则可循,所以

  编程过程往往比较复杂,而且编得的程序也不大好理解。究其原因在于,第一类问题

  已经有了现成的函数公式,第二类则没有。如果我们对于第二类问题也能写出它的递

  归公式,那么编码过程会大大简化,而且还可以改善程序的可读性。本文将借助两个

  考虑编程语言和实现环境。通常算法可以用自然语言、流程图、NS图等工具来表示,

  3. 由于公式是算法的最精确最简洁的描述形式,有了递归公式,编码工作就变得异常

  所谓递归程序设计的公式化方法,首先要把问题表示成数学意义下的递归函数,那么

  关键是确定函数值的意义,尽管问题本身未必需要计算什么函数值。函数值的选取可

  Hanoi塔问题要求显示为把若干个盘子从一柱搬到另一柱要采取的动作,我们可以

  把动作的个数取为函数值。于是得到有四个自变量的递归函数h(d,f,t,u),其意义

  是以u柱(using)为缓冲把d个盘子(disks)从f柱(from)搬到t柱(to)。容易得

  其实际意义非常明显:搬动一个盘子只需一个动作;而把f柱上的d个盘子从f柱搬到t柱,

  需要先把上面的d-1个盘子从f柱搬到u柱,再把最下面的一个盘子从f柱搬到t柱,最后

  有了递归公式,编程就变得极为简单。程序的结构是一个多分支结构,恰好同递归

  公式一一对应,编程几乎变成了机械的翻译。在下面的程序中,递归函数与递归公式的

  八皇后问题[2]是一个更有代表性更复杂的递归例题,要求在8×8的国际象棋棋盘上摆

  放8个皇后,使她们不致互相攻击。我们采取的算法仍然是从棋盘第一行开始每行放一

  个皇后,对于每一行都从该行的第一列开始放置,并判断它同前面的那些皇后是否互相

  攻击,如是就换成下一列,否则继续放置下一个皇后,直至放好8个皇后。依照这种思想,

  其中k表示已放置的皇后个数,而ai(此处i=k)表示第i行上的皇后所在列的列号,因

  此这9个自变量能够代表求解过程中任一时刻的状态,而函数值定义为从此状态出发能

  为真,就是说ai≠ak且i+ai≠k+aki且i-ai≠k-ak。将上面的递归公式很容易地翻译成如

  递归公式中的自变量a1,…,a8是一个相关的序列,在程序中只好用数组a表示。在q( )中

  首先计算ak是否同其前的所有ai相容,若是变量u非0。q( )与递归公式严格对应,呈现

  出有三个选择的分支结构。在u非0且k为8的情况下,置函数值v为1,并显示已得到的

  解。显然这个程序编写起来最为简单,而且最好理解。下面给出该程序的交互会线 84136275

  公式化方法是一种简单而有效的设计思想,它把程序设计和程序理解的难点都集中

  到递归公式上。从上面的例子可以看到这种思想能够简化程序设计,而且得到的程序显然好于通常的程序。这种思想有普遍性,至少适用多数递归程序的设计。由递归公式设计出的程序具有标准的分支结构,编写和理解都要简单得多。

  上面的两个例题在求得函数值的同时,很容易地得到了要求的序列,但对于一般的

  问题未必总是这样。笔者曾给出一种伴随序列法,可以用来得到某些问题(如显示所有从m个数中取n个数的组合)要求的序列。

本文链接:http://windsorflowers.net/diguikuaibianma/89.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部