《项目三 基本算法》由会员分享，可在线阅读，更多相关《项目三 基本算法（54页珍藏版）》请在金锄头文库上搜索。
1、项目三 基本算法应用,主讲：高成强,课程回顾,1. while(条件） 循环体内语句 ,2. do 循环体内语句 while(条件）;,3. for( ; ; ) 循环体内语句 ,当条件满足时,循环体,项目三 基本算法应用,【百鸡问题】公元五世纪末，我国古代数学家张丘建在算经中提出了如下问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百钱买百鸡，问鸡翁、母、雏各几何？,问题引入,现实生活中有各种要处理的问题,项目三 基本算法应用,算法,算法（Algorithm）：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。,程序仅仅是用某种计算机语言所描述的算法，是算法的实现形式。,算法是程
2、序的灵魂，程序设计的核心就是算法设计。,算法设计的实质就是克服客观的复杂性，建立问题的求解模型。,项目三 基本算法应用,项目任务,任务2.1 求和、求阶乘算法 任务2.2 穷举算法 任务2.3 最大公约数、最小公倍数 任务2.4 求素数算法 任务2.5 递推与迭代算法,项目三 基本算法应用,理解算法的概念 掌握求和、求阶乘算法 掌握穷举算法 掌握最大公约数、最小公倍数 掌握求素数算法 掌握递推与迭代算法,项目目标,项目三 基本算法应用,任务 2.1 求和、求阶乘算法,sum=1+(1+2!)+(1+2!+3!)+(1+2!+3!+4!+10!),此题可看作几项求和？后一项与前一项之间比较有什么
3、特点？第n项的值？,分组讨论：,项数：1 2 3 10, SF1-1 求 Sum = 1 + 2 + 3 + 5 + +100 SF1-2 求 P = 10! SF1-3 求 Sum = 1! + 2! + 3! + + 10!,SF1-1,SF1-2,SF1-3,SF1 求：1+(1+2!)+(1+2!+3!)+(1+2!+3!+4!+10!),有许多问题的解“隐藏”在多个可能之中。穷举就是对多种可能情形一一测试，从多种可能中找出符合条件的（一个或一组）解。当然，也可能得出无解的结论。,任务2.2 穷举算法,任务描述：,【SF2】百钱买百鸡问题,鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百
4、钱买百鸡，问鸡翁、母、雏各几何？,分组讨论：,此问题可以列出几个方程？请列出相应方程？此题有唯一解否，如何解？,设鸡翁、鸡母、鸡雏的数量分别为cocks、hens、chicks，则可得如下模型：5 * cocks + 3 * hens + chicks / 3.0 = 100cocks + hens + chicks = 100下面考虑如何寻找另外的约束条件。按常识，cocks、hens、chicks都应为正整数，且它们的取值范围分别应为：cocks：020 (假如100元全买cocks，最多20只)hens：033(假如100元全买hens，最多33只)chicks：0100(假如全买chi
5、cks，最多100只),分组讨论分析,本题的穷举过程如下： 首先从0开始，列举cocks（鸡翁）的各个可能值，在每个cocks值下找满足两个方程的一组解,算法如下：for(cocks = 0; cocks 20; +cocks) s1：找满足两个方程的解的hens，chickss1.1：找满足两个方程的解的hens（鸡母）s1.2：找满足两个方程的解的chicks（鸡雏）s2：输出一组解,算法如下：for(cocks = 0; cocks 20; +cocks) /* 下面进一步用穷举法来表现S1： */for(hens = 0; hens 33; + hens) s1.2 找满足方程的一个c
6、hicks s2 输出一组解 ,由于对列举的每个cocks与每个hens都可以按下式chicks = 100 - cocks hens 求出一个chicks。因此，只要该chicks满足另一个方程5 * cocks + 3 * hens + chicks / 3.0 = 100 便可以得到一组满足题意的cocks、hens、chicks。故S1.2可以改写为：chicks=100-cockshens; if(5*cocks+3*hens+chicks/3.0 = 100) printf(“%dt%dt%dn”,cocks,hens,chicks); 经过剥葱头似的几步求精过程，再加入类型声明语
7、句并调整输出格式，便可以得到一个C程序。,算法如下：for(cocks = 0; cocks 20; +cocks) /* 下面进一步用穷举法来表现S1： */for(hens = 0; hens 33; + hens) chicks = 100 cokcs - hens; if(5*cocks+3*hens+chicks/3.0=100) printf(“%dt%dt%dn”,cocks,hens,chicks); ,/* 程序名: SF2.c */#include void main() int cocks, hens, chicks; printf(“n公鸡数t母鸡数t小鸡数“); fo
8、r(cokcs=0; cocks20;+cocks) /* 穷举cocks */ for(hens=0; hens33;+hens) chicks = 100 cokcs - hens; if(5*cocks+3*hens+chicks/3.0=100) printf(“%dt%dt%dn”,cocks,hens,chicks); ,运行结果公鸡数 母鸡数 小鸡数0 25 754 18 788 11 8112 4 84,编程练习,搬砖问题：36块砖，36人搬，男搬4、女搬3、两个小儿抬一砖，要求一次全搬完，问男、女、小儿须若干？ Armstrong数具有如下特征：一个n位数等于其各位数的n次方
9、之和。如:153=13+53+331634=14+64+34+44请找出2、3、4位数中的所有Armstrong数。,父子俩的年龄：父亲今年30岁，儿子今年6岁，问多少年后父亲的年龄始儿子年龄的2倍。 换硬币：把一元人民币换成5分、2分、1分的硬币，有多少种换法? 要登上n阶楼梯，每一步允许跨1阶或2阶。共有多少种登楼梯方法？ 打印出500之内所有能被7或9整除的数。,7. 奇妙的算式：有人用字母代替十进制数字写出下面的算式。请找出这些字母代表的数字E G A L L L G A E 8. 找赛手：两个羽毛球队进行比赛，各出三人。甲队为A，B，C三人，乙队为x、y、z三人。已抽签决定比赛名单。
10、有人向队员打听比赛的名单。A说他不和x比，C说他不和x、z比。请编写一个程序找出三对赛手的名单。,课程回顾,任务2.1 求和、求阶乘算法,任务2.2 穷举算法,穷举就是对多种可能情形一一测试，从多种可能中找出符合条件的（一个或一组）解。也可能得出无解的结论。,任务2.3 最大公约数、最小公倍数,27 除 18 余数为 9 18 除 9 余数为 0 最后一次的除数 9 为最大公约数,分组讨论： “辗转相除”,【SF3】任意输入两个正整数,求它们的最大公约数。,输入 m , n 的值,求 m / n 的余数 r,当 r 0 时,输出最大公约数 n,n m,r n,求 m / n 的余数 r,例如：
11、求 27 和 18 的最大公约数,任务2.4 求素数算法,分组讨论：,【SF4】任意输入一个正数整 m ,判断它是否是素数。,素数：只能被1和它本身整除的正整数。,方法：,用 2 sqrt(m) 分别去除，都不能整出，则 m 为素数。如果有一次能被整出，则m 不是素数。,【SF4】任意输入一个正数整 m ,判断它是否是素数。,【SF4-1】求5 100之间的所有素数。,课程回顾,任务2.3 最大公约数和最小公倍数算法,任务2.4 求素数算法,假定一对新出生的兔子一个月后成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，到一年头上，可以繁殖成多少对兔子？,
12、任务2.5 递推与迭代算法,问题导入,现实生活中有各种要处理的问题,【兔子繁衍问题】,Fibonacci是中世纪意大利的一位极有才华的数学家。他在1202年出版的算盘的书中提出一个问题：,哪一类问题？,C语言如何解决？,任务2.5 递推与迭代算法,任务描述：,递推：是由一个变量的值推出另外的变量的值。例如若每代人之间的年龄相差25岁。则由一个人的年龄推出起父亲年龄、爷爷年龄的过程，就称为递推。迭代：就是不断用变量的新值替代其旧值。例如，一笔存款每年自动转存，就形成利滚利的情况，本金每年不同，不断迭代。实际上，迭代与递推没有严格的区别。例如在上述存款问题中，将各年的本金用不同的变量表示，就成了递
13、推问题。,假定一对新出生的兔子一个月后成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，到一年头上，可以繁殖成多少对兔子？,【SF5】兔子繁衍问题,分组讨论：,分析第 n 个月兔子（对）数与前几个月兔子（对）数的关系？ 分析给出前6个月，每个月兔子（对）数 ；,1，1，2，3，5，8，13，21，34，55,等于前两项之和,分析：各月的兔子数序列,f3=f1+f2,f1 f2,f1 f2,f3,f3,f1 f2,f3,f1=f2 f2=f3,【SF3-1】编程：输出下列数列的前50项值。 1, 2, 5, 10, 21, 42, 85, 170, 341
14、, 682, ,a ba=2*b+1b=2*a,编写一个C程序，利用如下的格里高利公式求的值。直到最后一项的值小于10-5为止。编写一个C程序，计算y的值，n由键盘输入。 编写一个C程序，把下列数列延长到第50项： 1，2，5，10，21，42，85，170，341，682， 切饼问题。一张大饼放在板上，如果不许将饼移动，问切n刀时，最多可以切成几块。,制定进货方案。某商店经营红旗牌小车。需求量的历史统计数据如表5.1所示。 进货量要与需求量有关。但是需求是不能控制的，只能 根据历史数据推测。为此，该商店提出了两种进货方案：（）按照上月的需求量Dt，决定本月的进货量Qt。即 Qt = Dt-1
15、（）按照前两个月的需求量的平均数，决定本月的进 货量。 即 Qt = （Dt-1 Dt-）若每兽一辆车，可获利万元，问哪种方案获利大？,5.2.2 猴子吃桃子,题目一天一只小猴子摘下一堆桃子，当即吃去一半，还觉得不过瘾，又多吃了一个。第二天接着吃了前一天剩下的一半，馋不忍罢又多吃了一个。以后每天如此。到第十天小猴子去吃时，只剩下一个桃子了。问小猴子共摘了多少桃子。,分析,设小猴子当初共摘了x个桃子。则根据题意，有： 第1天：吃掉x/2 + 1个，剩下x/2 1 = （x 2）/2个； 第2天：吃掉（x 2）/2）/2 + 1个，剩下（x 2）/2 （x 2）/2 + 1）= （x 2）/2 -（x 2 + 22）/22 =（x 2 22）/22 个； 第i天：剩下：（x 2 22 - - 2i）/2i个； 第9天：剩下：（x 2 22 - - 29）/29 = 1（第10天小猴子看到的那1个桃子）。,
