程序设计基础讲义(6).ppt

第六章算法与问题求解6.1算法是程序的核心—算法的概念6.1算法是程序的核心—算法的性质6.1算法是程序的核心—算法、数据结构与程序设计6.1算法是程序的核心—算法的操作与控制算法的控制结构操作的执行顺序是算法的重要组成部分，算法的控制结构给出算法的执行框架，决定算法中各种操作的执行顺序。1)顺序结构最基本的控制结构，从算法入口开始到算法出口结束，算法操作顺序执行，具有单入单出性质。2)选择结构通过逻辑或关系表达式结果，算法有选择地执行相应的操作，进行条件分支。选择结构也具有单入单出性质，而且是开放型的。可分为：单选结构、双选结构和多选结构。3)循环结构算法中某组操作要求执行多次时采用的结构。具有单入单出性质，但它是封闭型的。可分为：先判断后执行先执行后判断6.2算法的描述6.2算法的描述——自然语言6.2算法的描述——伪代码6.2算法的描述——传统流程图流程图常用符号用流程图描述算法应注意1、应根据解决问题的步骤从上至下顺序地画出流程图，各图框中的文字要尽量简洁。2、为避免流程图的图形显得过长，图中的流程线要尽量短。3、用流程图描述算法时，流程图的描述可粗可细，总的原则是：根据实际问题的复杂性，流程图达到的最终效果应该是，依据此图就能用某种程序设计语言实现相应的算法（即完成编程）。流程图描述算法示例输入整数（输入0表示停止输入），分别计算输入的正整数和负整数之和。6.2算法的描述——N-S结构化流程图N-S流程图描述算法示例输入一个正整数m，判断是否为素数。（若m不能被2~sqrt(m)之间的数整除，则m是素数。）6.3算法设计基本方法——穷举法穷举法解百钱百鸡问题鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?
问题分析首先建立这个问题的数学模型，数学模型这里指数学方程：假设：要买x只公鸡，y只母鸡，z只小鸡，根据题目的意思可以得到两个方程：x+y+z=100①5x+3y+z/3=100②另外根据题意，可以确定变量的取值范围：0<=x、y、z<=100;且z%3==0;采用穷举法进行求解：对于变量x,y,z的不同组合，看它们是否满足上面的两个方程，如果满足了，就是问题的一个解。如果不满足，就不是问题的解。N-S流程图描述百钱百鸡问题百钱百鸡问题源程序#include<stdio.h>main(){intx,y,z,j=0;for(x=0;x<=100;x++)for(y=0;y<=100;y++)for(z=0;z<=100;z+=3)if(x+y+z==100&&5*x+3*y+z/3==100)printf("%2d:cock=%2dhen=%2dchicken=%2d\n",++j,x,y,z);}百钱百鸡问题算法的进一步优化作为多层循环，优化主要集中在减少循环层数以及缩小变量的穷举范围上：1、穷举变量x的取值范围其实只能在0～20之间；2、并且，此时y的穷举范围由方程1可以减少为0~100-x，由方程2可以减少为0~(100-5x)/3，取较小的范围应该是：0~(100-5x)/3；3、进一步：x和y取值后，z的值唯一(z=100-x-y)，可以减少一层循环。优化后的百钱百鸡问题源程序#include<stdio.h>main(){intx,y,z,j=0;for(x=0;x<=20;x++)for(y=0;y<=(100-5*x)/3;y++){z=100-x-y;if(z%3==0&&5*x+3*y+z/3==100)printf("%2d:cock=%2dhen=%2dchicken=%2d\n",++j,x,y,z);}}穷举法解排列问题小明有5本新书，要借给a、b、c三位小朋友，若每人每次只能借一本，则可有多少种不同的借法？
问题分析对5本书从1至5进行编号。当a=i时，表示a借了编号为i的书。当3个人所借的书的编号都不相同时，就是满足题意的一种借阅方法。则：a、b、c取值范围：1<=a、b、c<=5且当：a!=b&&a!=c&&b!=c时，即为一种可能的借书方法。N-S流程图描述借书问题借书问题源程序#include<stdio.h>main(){inta,b,c,count=0;for(a=1;a<=5;a++)for(b=1;b<=5;b++)for(c=1;a!=b&&c<=5;c++)if(c!=a&&c!=b)printf("%d:%d,%d,%d\n",++count,a,b,c);}6.3算法设计基本方法——递归法递归问题示例—阶乘阶乘定义如下：n!=n*(n-1)!(n>0)且0!=1对于这种递归定义的函数，可以使用递归过程来求解:longFactorial(longn){if(n==0)return1;/*递归终止条件*/elsereturnn*Facto