《算法设计与分析》递归算法典型例题
更新时间:2024-05-11 16:28:01 阅读量: 综合文库 文档下载
算法递归典型例题
实验一:递归策略运用练习
三、 实验项目
1.运用递归策略设计算法实现下述题目的求解过程。 题目列表如下:
(1)运动会开了N天,一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚,第二天发金牌2枚加剩下的七分之一枚,第3天发金牌3枚加剩下的七分之一枚,以后每天都照此办理。到了第N天刚好还有金牌N枚,到此金牌全部发完。编程求N和M。
(2)国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份,然后给第一个儿子一份,再加上剩余财产的1/10;给第二个儿子两份,再加上剩余财产的1/10;??;给第i个儿子i份,再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几个儿子?财产共分成了多少份? 源程序:
(3)出售金鱼问题:第一次卖出全部金鱼的一半加二分之一条金鱼;第二次卖出乘余金鱼的三分之一加三分之一条金鱼;第三次卖出剩余金鱼的四分之一加四分之一条金鱼;第四次卖出剩余金鱼的五分之一加五分之一条金鱼;现在还剩下11条金鱼,在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼?
(4)某路公共汽车,总共有八站,从一号站发轩时车上已有n位乘客,到了第二站先下一半乘客,再上来了六位乘客;到了第三站也先下一半乘客,再上来了五位乘客,以后每到一站都先下车上已有的一半乘客,再上来了乘客比前一站少一个??,到了终点站车上还有乘客六人,问发车时车上的乘客有多少?
(5)猴子吃桃。有一群猴子摘来了一批桃子,猴王规定每天只准吃一半加一只(即第二天吃剩下的一半加一只,以此类推),第九天正好吃完,问猴子们摘来了多少桃子?
(6)小华读书。第一天读了全书的一半加二页,第二天读了剩下的一半加二页,以后天天如此??,第六天读完了最后的三页,问全书有多少页?
(7)日本著名数学游戏专家中村义作教授提出这样一个问题:父亲将2520个桔子分给六个儿子。分完 后父亲说:“老大将分给你的桔子的1/8给老二;老二拿到后连同原先的桔子分1/7给老三;老三拿到后连同原先的桔子分1/6给老四;老四拿到后连同原先的桔子分1/5给老五;老五拿到后连同原先的桔子分1/4给老六;老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子?
四、 实验过程
(一) 题目一:??
1. 题目分析
由已知可得,运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一天的金牌剩余数,且每天的金牌数应为6的倍数。 2. 算法构造
设运动会举行了N天, If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;
3. 算法实现
#include
int i=0,count=0; //count表示运动会举办的天数
int gold[100]; //定义储存数组 {
count=count+6; // 运动会天数加六 gold[count]=count; for (i=count-1; i>=1; i--) {
if (gold[i+1]%6!=0 )
break; // 跳出for循环
gold[i]=gold[i+1]*7/6+i; //计算第i天剩余的金牌数 else
do
//主函数
}
} while( i>=1 ); // 当 i>=1 继续做do循环
cout <<\运动会开了\天\ //返回天数 cout<<\总共发了\枚金牌\ //返回金牌数 4. 运行结果
}
(二) 题目二:??
1. 题目分析
由已知可得,最后一个儿子得到的遗产份数即为王子数目,由此可得到每个儿子得到的遗产份数,在对遗产数目进行合理性判断可得到符合要求的结果。 2. 算法构造
设皇帝有count个王子,
property[count]=count; for (i=count-1; i>=1; i--) {
if (property[i+1]%9!=0 ) else
break;
// 数目不符跳出for循环
property[i]=property[i+1]*10/9+i; //计算到第i个王子时剩余份数
}
3. 算法实现 #include
int i=0,count=0; //count表示国王的儿子数
int property[100]; //定义储存数组,表示分配到每个王子时剩余份数 do {
count=count+9; //王子数目为9的倍数
property[count]=count; for (i=count-1; i>=1; i--) {
if (property[i+1]%9!=0 ) else
property[i]=property[i+1]*10/9+i; //计算到第i个王子时剩余份数 break;
// 数目不符跳出for循环 //主函数
// 预编译命令
}
} while( i>=1 ); // 当 i>=1 继续做do循环
cout <<\皇帝有\个儿子\ //返回王子数 cout<<\遗产被分成\份\ //返回遗产份数 4. 运行结果
}
(三)题目三:??
1. 题目分析
由最后一天的金鱼数目,可递推得到每天的金鱼数目,第一天的数目即为金鱼总数。 2. 算法构造 fish[5]=11; for (i=4; i>=1; i--)
fish[i]=(fish[i+1]*(i+1)+1)/i; //计算到第i天剩余金鱼条数 3. 算法实现
#include
int i=0;
//主函数
int fish[6]; //定义储存数组各天剩余金鱼数 fish[5]=11; for (i=4; i>=1; i--) }
4. 运行结果
fish[i]=(fish[i+1]*(i+1)+1)/i; //计算到第i天剩余金鱼条数 cout<<\浴缸里原有金鱼\条\ //返总金鱼数
(四)题目四:?? 1. 题目分析
有到终点站时车上的乘客数可求得到任意一站的乘客人数,到第二站时车上的乘客数目即为发车时车上的乘客数。 2. 算法构造
num[8]=6; //到终点站车上还有六人 for(i=7; i>=2; i--)
3. 算法实现
#include
int i=0;
int num[9]; //定义储存数组 num[8]=6; //到终点站车上还有六人 for(i=7; i>=2; i--)
num[i]=2*(num[i+1]-8+i); //计算到第i站车上的人数
cout<<\发车时车上有\位乘客\ //返总发站人数,即为到第二站时车上人数
}
4. 运行结果
//主函数
num[i]=2*(num[i+1]-8+i); //计算到第i站车上的人数
(五)题目五:??
1. 题目分析
可假设有第十天,则第十天剩余的桃子数目为0,由此递推可得每一天剩余的桃子数目。第一天的桃子数目即为猴子摘桃子的总数。 2. 算法构造
num[10]=0; //第n天吃前的桃子数 for(i=9; i>=1; i--) 3. 算法实现
num[i]=2*(num[i+1]+1); //计算到第i天剩余的桃子数算法实现
#include
int i=0;
int num[11]; //定义储存数组 num[10]=0; //第n天吃前的桃子数 for(i=9; i>=1; i--) 的数目
}
4. 运行结果
num[i]=2*(num[i+1]+1); //计算到第i天剩余的桃子数
cout<<\猴子共摘来了\个桃子\ //输出总的桃子数,即第一天吃前
//主函数
(六)题目六:??
1. 题目分析
由第六天剩余的页数可递推得到每天的剩余页数,第一天的页数即为全书的页数 2. 算法构造
num[6]=3; //到第n天时剩余的页数 for(i=5; i>=1; i--)
num[i]=2*(num[i+1]+2); //计算到第i天剩余的页数 3. 算法实现
#include
int num[7]; //定义储存数组 num[6]=3; //到第n天时剩余的页数 for(i=5; i>=1; i--)
num[i]=2*(num[i+1]+2); //计算到第i天剩余的页数
//主函数
正在阅读:
《算法设计与分析》递归算法典型例题05-11
甘肃省水产养殖公司名录2018版333家 - 图文06-05
河北省安平中学2017-2018学年高一化学下学期第一次月考试题11-17
灌溉与排水工程施工方案11-25
浅春柳韵优美散文03-30
基层党组织专题组织生活会及民主生活会议程04-14
资 料1 「今後の学校における食育の在り方に関する有识者 …05-13
环境工程专业英语课后习题部分答案01-31
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 递归
- 算法
- 例题
- 典型
- 分析
- 设计
- 侵权责任方式与归责事由、归责原则的关系
- 军训国旗下讲话稿:收获的军训
- 2016年《证券投资基金》各章节重点归纳
- 陕西师范大学中文本科函授作业《古代汉语基础》附答案
- 研究内容- 副本
- 工程质量实测实量操作
- 2017-2022年中国全脂奶粉市场研究与市场全景评估报告(目录) -
- PLC课程设计:自动洗车机控制设计
- 二年级语文课外读书知识竞赛题(无答案)
- 初中化学重点难点2013 - 图文
- 九年级化学下册课程纲要
- 福州三中2015届高三年级第二次月考——语文
- 人民代表大会
- 南京市金陵中学2011届高三第四次模拟数学
- 2018银行党支部工作计划策划学习参考范文
- 2018年初级会计职称初级会计实务测试题
- 前厅培训知识
- 对提高英语教学质量的几点思考-精选作文
- 会计电算化理论考试题十套
- 第四单元 分数的意义和性质