《算法设计与分析》实验一

学号1421050102算法设计与分析实验报告一学生姓名Cherish专业、班级地 理指导教师唐 国 峰成绩计算机与信息工程学院软件工程系2017 年 3 月 14 日实验一：递归策略运用练习一、实验目的本次 是 算法的算法 及 用 ，旨在加深学生 算法原理的理解，提高学生运用 算法解决 的能力。二、实验步骤与要求1 前复 程所学知 以及 和理解指定的 外 材料；2学生独自完成 指定内容；3 束后，用 一的 告模板 写 告。4 提交 明：（ 1） 子版提交 明：a 需要提交Winrar 包，文件名 “算法 与分析 一_学号 _姓名”，如“算法 与分析 一_09290101_ 三”。b 包内 一个“ 算法 与分析 一其下 两个文件 ，一个文件 命名 “源程序” 告 子版” 。其下分 放置 成果物。_学号 _姓名”命名的 文件 ，另一个文件 命名 “ （ 2）打印版提交 明：a 不可随意更改模板 式。b 字体：中文 宋体，大小 10 号字，英文 Time New Roman ，大小 10 号字。c 行 距： 倍行距。（ 3）提交截止 ： 2017 年 3 月 28 日 16:00。三、 实验项目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 老大”。 果大家手中的桔子正好一 多。 六兄弟原来手中各有多少桔子？（ 8）某种 染病第一天只有一个患者，前5 天 潜伏期，不 作也不会 染人，第6 天开始 作，从 作到治愈需要5 天 ，期 每天 染3 个人，求第N 天共有多少患者。【 做 】（ 5 选 3）（ 1） 了保障社会秩序，保 人民群众生命 安全，警察叔叔需要与罪犯斗智斗勇，因而需要 常性地 行体力 和智力 ！某批警察叔叔正在 行智力 ：1 2 3 4 5 6 7 8 9 = 110; 看上 的算式， 了使等式成立，需要在数字 填入加号或者减号（可以不填， 但不能填入其它符号） 。之 没有填入符号的数字 合成一个数，例如：12+34+56+7-8+9就是一种合格的填法； 123+4+5+67-89是另一个可能的答案。 你利用 算机的 ，帮助警察叔叔快速找到所有答案。每个答案占一行。形如：12+34+56+7-8+9123+4+5+67-89（ 2） 将一个整数 出。形如654321， 出 1,2,3,4,5,6（ 3）用 分解 因数。形如：12=2*2*3（ 4）50 个 梯，你一次可以上一 或两 ，走上去，共有多少种走法？（ 5） 号 的字符 合。 目：在 或者手机上，一个数字如2 着字母ABC ，7 着 PQRS。那么数字串 27 所 的字符的可能 合就有 3*4=12 种（如 AP， BR 在 入一个 3 到 11 位 的 号 ， 打印出 个 号 所 的字符的所有可能 合和 等）。 合数。四、实验过程以下程序都是在VS2010 下编译与VC6.0代码稍有不同。（1）运 会开了N 天，一共 出金牌M 枚。第一天 金牌1 枚加剩下的七分之一枚，第二天 金牌 2 枚加剩下的七分之一枚，第 3 天 金牌3 枚加剩下的七分之一枚，以后每天都照此 理。到了第 N 天 好 有金牌N 枚，到此金牌全部 完。 程求N 和 M 。 目分析依据 目可写出 式：(F(n)-n)*6/7=F(n+1);F(n)是第n天 牌 数即第n-1天剩余的包括第n天 的和剩下的。每天 放的金牌数：当天天数 +（前一天剩余金牌 -当天天数） /7，所以判 的条件是（前一天剩余金牌 -当天天数） 为 7的整数倍， 第 i+1 天的金牌数即 i天剩下的必 是 6的整数倍。算法构造递归函数： nSum(i+1,n)=(nSum(i,n)-i)*6/7.筛选条件：(nSum(i,n)-i)%7=0&&(nSum(i,n)%6=0)算法实现#include<stdio.h>#define devide 7; /不知什么原因这样定义下面不能用？vc6.0未安上，不知与vs2010 有和区别？int nSum(int i,int n)/nSum()函数定义第i 天的金牌数即i-1天剩下.int result=0;if(i=n)return n;elseresult=(nSum(i+1,n)*7)/6+i);/ 递归函数：nSum(i+1,n)=(nSum(i,n)-i)*6/7.return result;void main()for(int n=2;n<=10;n+)/ 递增比赛天数逐个验证int skip=0;for(int i=1;i<=n;i+)/ 依次筛选从 i=1 到 n符合条件的 n值剩余金牌if(nSum(i,n)-i)%7=0&&(nSum(i,n)%6=0)/ 每天发放的金牌数：当天天数- 当天天数）/7 ，即（前一天剩余金牌- 当天天数）为7的整数倍+（前一天int skip=1; /递归函数：nSum(i+1,n)=(nSum(i,n)-i)*6/7即nSum(i,n)=nSum(i+1,n)*7/6+i，第 i+1 天的金牌数即i 天剩下的必须是6的整数倍printf( " 共有金牌 %d枚, 共进行 %d天 n" ,nSum(1,n),n); / 金牌总数即第一天金牌数 for(int j=1;j<=n;j+)printf( " 第 %d天, 发放 %d+%d枚, 还剩 %d枚n",j,j,(nSum(j,n)-j)/7,(nSum(j,n)-j)*6/7);break;if(skip=1 ) / / 用于跳出双层循环结构即n递增时第一个满足时即可输出，可运行结果却不然break;/ 会有在 n上界内更多的结构输出，只有第一个n值满足不知为何？getchar();运行 果经验归纳 式容易想出，但是相 的 条件比 确定。（2）国王分 。某国王 前 儿子 分 。他把 分 若干份，然后 第一个儿子一份，再加上剩余 的 1/10 ； 第二个儿子两份，再加上剩余 的 1/10 ； 第 i 个儿子 i 份，再加上剩余 的 1/10 。每个儿子都窃窃自喜。 以 得到了父王的偏 ， 孰不知国王是 “一碗水端平”的。 用程序回答，老国王共有几个儿子？ 共分成了多少份？ 目分析 道国王分 的 和上 运 会 金牌 似，不 在 条件 由 意略不同其 也是一 ，每个儿子分到的 相同即：E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)，且第i 个儿子分i 份及剩下的1/10，即E(i,n)-i的差是10 的整数倍。算法构造 函数： E(i+1,