递归公式计算二项式_递归公式 每日信息
1、1 引言递归程序处理的问题可以分成两类:第一类是数学上的递归函数,要求算得一个函数值,例如阶乘函数和Fibonacci函数;第二类问题具有递归特征,目的可能是求出满足某种条件的操作序列,例如Hanoi塔和八皇后问题。
(资料图片)
2、第一类问题的程序设计是简单的、机械的,而第二类问题则不然,由于涉及面广,没有统一的规则可循,所以编程过程往往比较复杂,而且编得的程序也不大好理解。
3、究其原因在于,第一类问题已经有了现成的函数公式,第二类则没有。
4、如果我们对于第二类问题也能写出它的递归公式,那么编码过程会大大简化,而且还可以改善程序的可读性。
5、本文将借助两个程序实例讨论这种方法。
6、2 公式化方法程序设计可以分成两个阶段:逻辑阶段和实现阶段。
7、逻辑阶段要确定算法,不必考虑编程语言和实现环境。
8、通常算法可以用自然语言、流程图、NS图等工具来表示,对于第二类问题能在逻辑阶段得出它的递归公式,那么至少有这样几个好处:1. 把逻辑阶段同实现阶段截然分开,大大简化程序设计。
9、2. 用数学方法推导递归公式,要比用其他方法设计算法要简单得多。
10、3. 由于公式是算法的最精确最简洁的描述形式,有了递归公式,编码工作就变得异常简单,而且程序的可读性也会很好。
11、所谓递归程序设计的公式化方法,首先要把问题表示成数学意义下的递归函数,那么关键是确定函数值的意义,尽管问题本身未必需要计算什么函数值。
12、函数值的选取可能不是唯一的,但是愈能表现问题本质愈好。
13、Hanoi塔问题要求显示为把若干个盘子从一柱搬到另一柱要采取的动作,我们可以把动作的个数取为函数值。
14、于是得到有四个自变量的递归函数h(d,f,t,u),其意义是以u柱(using)为缓冲把d个盘子(disks)从f柱(from)搬到t柱(to)。
15、容易得到下面的递归公式:h(1,f,t,u)=1h(d,f,t,u)= h(d-1,f,u,t)+ h(1,f,t,u)+ h(d-1,u,t,f), 如果d>1其实际意义非常明显:搬动一个盘子只需一个动作;而把f柱上的d个盘子从f柱搬到t柱,需要先把上面的d-1个盘子从f柱搬到u柱,再把最下面的一个盘子从f柱搬到t柱,最后把已在u柱上的d-1盘子搬到t柱,因此总的动作个数等于三组动作之和。
16、有了递归公式,编程就变得极为简单。
17、程序的结构是一个多分支结构,恰好同递归公式一一对应,编程几乎变成了机械的翻译。
18、在下面的程序中,递归函数与递归公式的差别只有当d为1时不仅要把动作个数v置为1,同时还要显示此动作。
19、main(){ int d,v,h(int,int,int,int);printf("disks = ");scanf("%d",&d);v=h(d,1,2,3);printf("%d actions for %d disks!",v,d);}int h(int d,int f,int t,int u){ int i,v;if(d==1){v=1;printf("%d->%d ",f,t);}else v=h(d-1,f,u,t)+h(1,f,t,u)+h(d-1,u,t,f);return v;}此程序的运行会话如下:disks = 31->2 1->3 2->3 1->2 3->1 3->2 1->27 actions for 3 disks!3 例子:八皇后问题八皇后问题[2]是一个更有代表性更复杂的递归例题,要求在8×8的国际象棋棋盘上摆放8个皇后,使她们不致互相攻击。
20、我们采取的算法仍然是从棋盘第一行开始每行放一个皇后,对于每一行都从该行的第一列开始放置,并判断它同前面的那些皇后是否互相攻击,如是就换成下一列,否则继续放置下一个皇后,直至放好8个皇后。
21、依照这种思想,我们定义一个有9个自变量的函数:q(k,a1,a2,a3,a4,a5,a6,a7,a8)其中k表示已放置的皇后个数,而ai(此处i<=k)表示第i行上的皇后所在列的列号,因此这9个自变量能够代表求解过程中任一时刻的状态,而函数值定义为从此状态出发能得到的解的个数。
22、按照这一思想不难得到下面的递归公式:q(k,a1,...,ak,0,...0)= 0 如果有0
23、将上面的递归公式很容易地翻译成如下程序:main(){ int a[9],v,q(int,int *);v=q(0,a);printf("There are %d solutions!",v);}int q(int k,int *a){ int i,u,v;for(i=1,u=1;i
24、在q( )中首先计算ak是否同其前的所有ai相容,若是变量u非0。
25、q( )与递归公式严格对应,呈现出有三个选择的分支结构。
26、在u非0且k为8的情况下,置函数值v为1,并显示已得到的解。
27、显然这个程序编写起来最为简单,而且最好理解。
28、下面给出该程序的交互会话,为节省版面只列出92个解中的4个:15863724 16837425 ... 83162574 84136275There are 92 solutions!4 结束语公式化方法是一种简单而有效的设计思想,它把程序设计和程序理解的难点都集中到递归公式上。
29、从上面的例子可以看到这种思想能够简化程序设计,而且得到的程序显然好于通常的程序。
30、这种思想有普遍性,至少适用多数递归程序的设计。
31、由递归公式设计出的程序具有标准的分支结构,编写和理解都要简单得多。
32、上面的两个例题在求得函数值的同时,很容易地得到了要求的序列,但对于一般的问题未必总是这样。
33、笔者曾给出一种伴随序列法,可以用来得到某些问题(如显示所有从m个数中取n个数的组合)要求的序列。
本文到此分享完毕,希望对大家有所帮助。
关键词:
- 递归公式计算二项式_递归公式 每日信息(2023-04-23 04:34:00)
- 英语辅导报官网答案2021七年级下_英语辅导报官网|天天资讯(2023-04-23 03:59:15)
- 青岛公考机构:如何在短时间内提高你的公考成绩?(2023-04-23 03:29:46)
- 焦点简讯:赛默飞中国:用创新助力绿色发展(2023-04-23 03:22:45)
- 环球热点评!孔生生(2023-04-23 03:01:05)
- 环球人文地理_关于环球人文地理介绍|快播(2023-04-23 03:04:32)
- 全球时讯:请安是什么意思-请安(2023-04-23 02:17:00)
- 金弹子几月嫁接成活率高 金弹子什么时间嫁接成活率高|环球速递(2023-04-23 01:57:10)
- 环球今日讯!2023上海车展大奖:先锋科技眼花缭乱 海外品牌概念车花落谁家?(2023-04-23 01:34:00)
- 有关于植物的作文450字左右_有关于植物的作文|天天热门(2023-04-23 01:34:14)
- 曾令旭晒与阿不都合照:新疆队核心被我帽了俩 完全限制住哈哈|世界观焦点(2023-04-23 01:26:45)
- 长沙2个案例获评全省国土空间生态修复范例_今日热讯(2023-04-23 00:48:56)
- 2023年事业单位招聘信息汇总(更新至4月22日)_环球动态(2023-04-23 00:14:48)
- 九牛二虎,打一动物_九牛二虎打一生肖_环球观察(2023-04-22 23:48:38)
- 小林退热贴多久换一次_小林退热贴(2023-04-22 23:48:53)
- 2023江苏邮政首届书报刊“悦读节”启动 将推出1000余场阅读活动 环球微头条(2023-04-22 23:25:43)
- 中级会计专业技术资格考试大纲有用吗|世界快报(2023-04-22 23:16:15)
- 微头条丨个人、企业 专业办理多家银行贷款服务(2023-04-22 22:51:36)
- 股票如何逃顶?分享3个绝招,避免做坐电梯了!(2023-04-22 22:57:37)
- 世界资讯:银行工作人员的存款方式你了解吗?原来他们都是这样存款的!(2023-04-22 22:44:11)
- 兰花可以放室外养吗 能不能室外养兰花 全球时快讯(2023-04-22 22:49:49)
- 美国上周首申失业金人数上升 专家忧未来或进入经济衰退-快讯(2023-04-22 22:49:43)
- 比亚迪海鸥:小型车市场的黑马,能否飞上天空?(2023-04-22 22:01:19)
- 目前东康线间断性放行!周日夜间至周一,鄂尔多斯将再迎小雨或雨夹雪|天天观天下(2023-04-22 21:56:04)
- 德固特:公司可为制药生产提供相关装备 世界焦点(2023-04-22 21:56:32)
- 中国银行等多家银行:将自动免除2023年度国家助学贷款利息 世界新视野(2023-04-22 21:46:12)
- 天津银行业存款一季度保持较快增速,其中个人存款同比增超两成 天天动态(2023-04-22 22:00:12)
- 最新:4月农业银行最新利率,存10万有2750元,想存钱的人有福了(2023-04-22 22:02:46)
- 最新:交通银行利率上调,存10万利息4500元,要存款的朋友注意了(2023-04-22 21:52:11)
- 强势思维,决定选股收益,明白了,早点远离亏损! 全球速看(2023-04-22 22:02:09)
-
2023年事业单位招聘信息汇总(更新至4月22
4548,2140,2142,3100,3102,4508,3103
-
九牛二虎,打一动物_九牛二虎打一生肖_环球
1、老鼠用了九牛二虎之力还不如只小老鼠脑袋聪明得了第一。本文到此分享完毕,希望对大...
-
小林退热贴多久换一次_小林退热贴
1、一周多的宝宝发烧不退,还是建议到医院儿科检查治疗。2、您的情况小林退热贴是可以...
-
2023江苏邮政首届书报刊“悦读节”启动 将
启动仪式现场。人民网龚世俊摄人民网南京4月22日电(龚世俊)4月22日上午,江苏邮政首...
-
中级会计专业技术资格考试大纲有用吗|世界
中级会计专业技术资格考试大纲有用,考试大纲是考试出题的主要方向,出题的方向不会偏...
-
微头条丨个人、企业 专业办理多家银行贷款
(大理114通讯录↓↓↓)(大理吃喝玩乐↓↓↓)▼【超级推】贷-款找我!个人、企业✅...
-
股票如何逃顶?分享3个绝招,避免做坐电梯
10余年的炒股经历,让我太熟悉顶部形态了,我把自己的3大绝招公开,让你快速识别股票顶...
-
世界资讯:银行工作人员的存款方式你了解吗
银行工作人员的存款方式你了解吗?原来他们都是这样存款的赚到钱存在银行中是每一个中...
-
兰花可以放室外养吗 能不能室外养兰花 全
1、兰花可以放在室外养殖,但是不能够长期放在室外养殖的。如果下大雨,则会导致兰花盆...
-
美国上周首申失业金人数上升 专家忧未来或
中新网4月21日电综合报道,当地时间20日,美国劳工部报告称,上周全美首次申领失业金人...
- 滚动
- 综合
- 房产