计算机算法初步.ppt

《计算机算法初步.ppt》由会员分享，可在线阅读，更多相关《计算机算法初步.ppt（75页珍藏版）》请在三一办公上搜索。

1、第三章 计算机算法初步,一、解题方法及算法概念二、算法举例-穷举法三、算法举例-递推与迭代法四、良好的编程风格,计算机求解问题的一般过程,问题分析阶段认真分析问题，建立正确的模型,找出解题方法数据结构设计阶段找出所涉及的数据信息，根据已经建立的正确模型设计相应的数据结构算法设计阶段根据数据结构，详细设计计算步骤，并加以描述编码与调试阶段用计算机语言实现所描述的算法，并调试正确,一、解题方法及算法概念,举例：求绿化带宽度,如图：在长500m、宽300m的地域内保护80000m2的地块，求沿四周植树建设绿化带的宽度。,分析：把题目中提出的问题数学化,设 x：绿化带宽度 length：地块长度 wi

2、dth：地块宽度 area：保护面积,列出计算式：area=(length-2x)(width-2x),得到一元二次方程：4x2-2(length+width)x+length*width-area=0,找出计算方法X=根据求根公式求解方程找出算法用C语言写出程序调试和测试,算法概念,算法解题过程（步骤）的具体描述可完全精确执行、有确定结果的有穷指令序列算法的控制结构选择结构（如：C语言的 if 语句）循环结构（如：C语言的 while 语句）顺序结构（语句组）3种结构可以满足各种算法的所有控制要求,算法描述的必要性,程序设计过程 算法设计 程序实现算法描述：描述解题逻辑，验证正确性独立于程序

3、设计语言程序实现：利用程序设计语言的功能，实现算法熟悉语言的语法、语义、支撑环境,算法描述方法,自然语言描述易于理解；与计算机语言差别较大，不严谨，容易出现二义性图形方式描述比较直观，无二义性，易于掌握，过度为编码比较容易流程图(P60 表3-1)、N-S图、PAD图等伪代码方式描述很严谨，与计算机语言很接近，很容易过度为编码，掌握的难度略大,起止框,I/O框,处理框,判断框,调用框,连接框,有向边,常用流程图符号(P60 表3-1),用流程图表示算法,循环结构,用N-S图表示算法,顺序结构,选择结构,当型循环（先判断条件）,直到型循环（后判断条件）,用PAD图表示算法,A,B,顺序结构,P,

4、选择结构,当型循环（先判断条件）,直到型循环（后判断条件）,A,B,伪码描述例：求5个整数之和,数据分析sum 保存已经输入的整数之和算法描述：赋值 0 sum重复执行 5 次2.1 读入一个整数2.2 累加到 sum输出整数和 sum仅考虑主要的数据对象和控制结构程序实现阶段考虑数据对象和控制结构的具体实现,3.1 实例1：考试成绩统计,任务：输入某班级人数和某课程的考试成绩（100分制），输出及格率(60)和不及格率。问题分析（基本方法）输入学生人数后，逐个输入成绩，判断及格否，统计及格人数和不及格人数数据分析班级人数num及格人数pass不及格人数fail输入成绩score,过程描述（流

5、程图）,初值设置0 pass0 fail,读入成绩 score,读入学生人数 num,num=0,score 60,fail 加一num 减一,pass 加一num 减一,计算及格率pass/(pass+fail)和不及格率fail/(pass+fail)并输出,Y,N,Y,N,算法的验证,模拟算法的计算过程，跟踪数据的变化,程序结构设计（本题）,流程图的结构从外层到内层顺序 循环 选择程序结构复合语句 while 语句 if 语句while 条件：num=0if 条件：score 60细节问题输出格式：65.5%涉及浮点数的处理,程序实现,#include main()int num,pas

6、s,fail,score;while(0!=num),printf(“输入分数：”);scanf(“%d”,num=pass+fail;printf(“passed%f%n”,(float)pass/num*100);printf(“failed%f%n”,(float)fail/num*100);,pass=fail=0;printf(“请输入学生人数：”);scanf(“%d”,初值设置和输入学生人数,输出及格率和不及格率,输入分数统计及格人数和不及格人数,语言现象,赋值表达式pass=(fail=0)赋值运算符=右结合简化赋值（自反运算、复合赋值）pass+=1等价于 pass=pass

7、+1自动类型变换 printf(“passed%lf%n”,100.0*pass/num);强制类型变换（类型名）表达式/*改变其数据类型*/转义字符%或%用于输出%,设计方法分析,计算机科学家尼克劳斯沃思（Niklaus Wirth）提出 Programs=Algorithms+Data Strcture 程序=算法+数据结构程序设计过程问题定义：输入输出要求（数据与格式）数据结构：分析需要保存的信息，组织数据结构算法设计：编制解题步骤程序编码：选用程序设计语言，实现解题步骤程序测试：排错和测试,例3-2 求解一元二次方程,问题分析一元二次方程可以写成ax2+bx+c=0方程由三个系数a、b

8、、c惟一确定需要用户输入三个系数，然后根据一元二次方程的求解规则计算最终的结果，并将结果显示输出,流程剖析,变量t1,t2保存数学计算中的中间结果,输入a,b,c,b2-4act1,t1=0,Y,N,t1t2,t10,输出-b/2a,输出(-bt2)/2a,输出“无解”,Y,N,程序实现,#include#include main()int a,b,c,t1;double t2;scanf(“%d%d%d”,类型转换,数学函数说明,求平方根,强制类型转换,程序测试,测试设计考虑数据的各种取值，准备测试用例检查每个程序分支b2-4ac 等于 0，大于 0，小于 0测试用例1 2 1 b2-4ac

9、=02 6 3 b2-4ac=124 3 3 b2-4ac=-39,TC 程序跟踪,TURBO C 跟踪调试F7单步跟踪设置监视点(Watch):Ctrl+F7输入变量名跟踪过程message窗将显示被跟踪变量的值,学习方法,算法的学习（长期任务）利用变量就是存储器的概念，考虑解题过程中必须保存的数据利用3种控制结构（顺序、选择、循环），考虑数据变化过程，设计处理过程应能够熟练地设计数据结构和简单的算法程序设计语言的学习阅读程序实例，理解新的语言现象程序设计实践，上机排错调试对主要语言功能和上机编程操作应该达到十分熟练,二、算法举例-穷举法（P63）,穷举法也称为枚举法，是一种一一列举各种情况

10、的求解问题的方法。基本思想：对问题的所有可能情形一一罗列，直到找出符合条件的解或将全部可能情形都测试过为止。,实例3 素数的判断题目判断给定的整数（大于1），是否为素数。问题分析素数（质数）是指除了1和它本身外，没有其它因子的大于1的整数。,例如2 3 13 17 23 等是素数4 12 20 等不是素数,编程思路：要判断给定整数a是不是素数，应该根据素数的定义，用2、3、a-1分别去试除如果其中有能整除a的数，则a不是素数如果这些数都不能整除a，则a是素数只要找到一个能整除a的数，就能断定a不是素数，因此这时应提前退出循环 循环结束后判是哪种情况，输出相应信息,算法流程图：P64,算法描述,

11、else,#include main()int i,a;printf(Input a(1):);scanf(%d,for(i=2;i=a-1;i+)if(a%i=0)break;,if(ia-1),/*用2、3、a-1去试*/,/*找到因子提前退出*/,/*若真，说明正常退出，是素数*/,/*若假，说明提前退出，不是素数*/,printf(%d is a prime number.n,a);,printf(%d is not a prime number.n,a);,讨论为减少循环次数，只需用2a/2之间或用 2a1/2 之间的整数试除,第一次运行：Input a(1):1111 is a p

12、rime number.第二次运行：Input a(1):1515 is not a prime number.,运行情况：,3.4 实例4 百钱买百鸡,问题陈述某人有钱百枚，希望买一百只鸡；假设不同的鸡价格不同，公鸡5枚钱一只，母鸡3枚钱一只，而1枚钱可以买3只小鸡。试问如果正好使用百枚钱买到一百只鸡，其中有几只公鸡、母鸡和小鸡。解题思路（穷举法）考虑公鸡、母鸡和小鸡数量的所有可能的取值，依次检查是否构成了问题的解，找出价钱正好是100的组合约束条件：各种鸡的数量一定小于100，数量之和为100数据结构公鸡数量x母鸡数量y小鸡数量z,数学模型,算法设计（用伪码表示）,1：0 x2：如果 x=

13、100/5（即20）2.1：0 y2.2：如果 y=100/3（即33）：0z：如果z=100：如果 x+y+z=100 并且 5x+3y+z/3=100：输出 x,y,z（解）：z+,重复：y+,重复2.22.3：x+,重复23：结束,流程图,程序实现,循环控制变量明确的情况：采用 for 语句包括循环次数固定的情况实数的比较不用 x=y用 fabs(x-y)1e-5(差的绝对值小于10-5),程序编码,#include#include main()int x,y,z;/*公鸡、母鸡、小鸡的个数*/for(x=0;x=100/5;x+)for(y=0;y=100/3;y+)for(z=0;z

14、=100;z+)if(x+y+z=100,结果与分析,x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84笨拙的穷举法符合计算机解题的特点,程序说明,逻辑运算与求 x 的绝对值数学计算头文件：math.h,浮点数的判断问题,机器中二进制表示的浮点数是有误差的判断问题：double x,y;if(x=y)应使用 if(fabs(x-y)0.00001)控制误差限制在一定的精度内即可。浮点常量的默认类型为doublefloat x;if(x=-1.2),注意：类型不一致,可写成：1e-5,#include main()int x,y,z;for(

15、x=0;x=20;x+)for(y=0;y=33;y+)for(z=0;z=100;z+)if(x+y+z=100,程序代码(用精确值整型处理),改进的程序代码（减少执行时间）,#include main()int x,y,z;for(x=0;x=20;x+)for(y=0;y=33;y+)z=100-x-y;if(15*x+9*y+z=300)printf(“x=%d,y=%d,z=%dn”,x,y,z);只用两层循环。,穷举法小结,基本方法通过分析，确定可能的取值范围对该范围的每个值进行检测，找出所有符合要求的值可以用循环语句实现穷举优点容易理解、不会遗漏某些解缺点时间效率欠佳,穷举法小结

16、,特点常用于问题有多个(有限)解的情况当没有或很难找到解析方式求解时可使用穷举法时间效率不是最佳的,三、算法举例-递推与迭代法,在计算机数值计算中，递推也称为迭代。递推基本策略是将复杂的运算划分为可以重复操作的若干个简单的运算，进而充分利用计算机擅长重复计算的特点。递推求解的基本思想：不断用变量的旧值递推其新值的过程。采用循环结构完成一个迭代处理过程。关键在于找出递推公式和边界条件（初始值、终止条件）,P67,实例5 Fibonacci 序列,问题,Fibonacci（斐波那契）序列有如下定义：,，,要求：输出斐波纳契（Fibonacci）级数的前三十项，并一行输出6项。,问题分析解决Fibo

17、nacci序列的递推计算方法（1）序列的头两个数已知；（2）已知连续的两个Fibonacci数，可以算下一个数。数据对象 解决应用问题：a,b,next（long类型）解决输出问题：n（int类型）,求解过程,+,a,b,next 第5项,+,next 第3项,a,b,next 第4项,a,b,next 第6项,+,2,8,1,2,3,2,3,5,3,5,next=a+b;a=b;b=next;,规律：,算法流程,选择结构,#include main()int i,n;long a,b,next;,a=b=1;printf(%8ld%8ld,a,b);n=2;,/*处理前两项*/,for(i=

18、3;i=30;i+)next=a+b;a=b;b=next;,/*处理后28项*/,printf(%8ld,next);n+;if(n%6=0)printf(n);,/*输出并控制换行*/,程序实现,运行结果如下：1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040,实例6：求圆周率,问题分析圆周率的计算公式：=4 4/3+4/5 4/7+4/9 4/11+,数据对象PI 表示圆周率，f

19、loat或double。而且有一定的精度要求。item：每一个数据项，类型同PI。sign：保存符号,算法描述,终止条件：由于数据项的绝对值是递减的，且相邻项的符号不同，如果第n个数据项的绝对值已经小于精度值，则前n项之和一定已经满足精度,#include#include main()int sign=1;long i=1;double PI=0.0,item;do item=sign*4.0/(2*i+-1);sign=-sign;PI+=item;while(fabs(item)1e-4);/*数据项精度控制循环*/printf(“PI=%lfn”,PI);,程序代码,实例7：按位分解整数

20、 P71,题目要求从键盘输入一个整数，然后将它的每一位分解成独立的数字字符并输出之。问题分析利用整除和求余运算实现将整数分解例如，对整数 73267326/1000可得到最高位7；7326%1000可得到其余的位数326这种方法要求首先获得整数最高位的权（本例为1000），然后从高向低逐个分离出每位数字,算法描述,#include main()long x,y,n;printf(“Enter an integer:”);scanf(“%ld”,程序代码,递推与迭代法小结,思路利用上一个或上几个值推出后一个值，使后一个值与问题的解更接近要点建立递推或迭代关系（递推公式）有明确的初始值有明确的结束

21、条件,3.5 实例5 统计数字字符的出现次数,任务统计一行输入字符中每个数字字符的出现次数数据分析应保存10个整数；（需要一组相关数据）设置数组 int digits10每个元素存一个数字字符的出现次数 例如：数字字符3的出现次数保存在 digits3中输入字符 ch,算法的描述（穷举法）,1.digits数组元素初始化为02.读入一个字符 ch3.如果ch不是换行符，则3.1 如果ch是数字字符，则3.1.1 digitsch 加一3.2 读入一个字符 ch3.3 重复处理34.输出digits数组,先考虑整体算法,digits数组初始化,digitsch加1,再读ch,ch=n,ch是数字

22、,输出统计数字,读ch,Y,Y,N,N,流程图,？,？,算法细化,digits 数组元素初始化1.设循环变量 i 为 02.当 i 小于 10 时2.1 设 0 digits i 2.2 i 加一2.3 重复 2,局部算法与外部逻辑处理关系不大,输出 digits 数组1.设循环变量 i 为 02.当 i 小于 10 时2.1 输出 digits i 2.2 i 加一2.3 重复 2,程序结构设计,算法过程分析3个循环：主算法、2个细化算法程序结构采用 while 语句循环控制：换行符检查、数组下标数据结构一维整数数组下标问题：数字字符整数（利用ASCII值）ch 0 0,#include m

23、ain()int digits10,i=0;char ch;while(i=0,利用字符的ASCII值,程序实现,自增运算赋值后加1,整数数组,逻辑与运算,程序说明,数组说明（定义）类型 数组名 数组大小N；数组引用数组名 表达式 下标范围 0 到 N-1(下标越界,编译查不出来)字符的运算以其ASCII值参加整数运算C语言支持不同类型的混合运算,如：（c+2）是ASCII的值printf(“%d”,c+2);101printf(“%c”,c+2);e,结构化程序设计方法,自顶向下首先描述外层核心算法与主要数据对象突出解题逻辑，忽略细节控制结构不超过两层循环限制了算法的难度逐步求精在确立了外部

24、算法的基础上逐步描述各个细节算法及其相关数据对象（如：上例中的digits初始化和输出）复杂情况下，细节算法仍应进一步逐步求精,数据与变量,数据的分析分析算法中，需要保存的数据有明确的意义，不多不少，避免重复变量的设置为数据的保存提供存储空间提供数据结构（如：数组等）避免同一变量在不同时刻代表不同的数据影响程序可读性的关键因素之一,方法分析,基于数学关系数学模型是解题方法算法是解题过程的描述（穷举、递推、）程序设计是解题过程的具体实现穷举过程、迭代过程的算法实现可以用算法的循环控制编程中用循环语句实现实现细节熟悉各种运算、各种数据类型的使用方法,四、良好的编程风格,依据规约，编写正确的程序完全

25、按要求实现功能格式一行一语句。太长的语句可占多行，使其不溢出画面。括号嵌套缩进对应，不要齐头并进适当留空格、空行等，增加可读性下面是一段微软的代码：,int WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,LPSTR lpCmdLine,int nCmdShow)MSG msg;HACCEL hAccelTable;/Initialize global stringsLoadString(hInstance,IDS_APP_TITLE,szTitle,MAX_LOADSTRING);LoadString(hInstance,IDC_A,s

26、zWindowClass,MAX_LOADSTRING);MyRegisterClass(hInstance);/Perform application initialization:if(!InitInstance(hInstance,nCmdShow)return FALSE;hAccelTable=LoadAccelerators(hInstance,(LPCTSTR)IDC_A);/Main message loop:while(GetMessage(,不好的例子,#include int main()printf(Hello,World.n);return 0;,main()int

27、i,x,max=0;for(i=0;imax)max=x;,/与本书P47对比,每个变量有明确的角色注释（反映你的文字水平）文件注释函数注释程序片断关键点注释关键数据结构注释通常没必要每句话写注释程序员友好你的程序是给人看的，不要写的晦涩难懂。,正确性可懂度时间复杂度空间复杂度健壮性可扩展性可移植性,本章小结,算法用一系列动作来描述问题求解的过程算法描述方法流程图：图形化的算法描述伪码：算法过程的动作说明算法设计与实现算法设计描述解题方法；程序设计描述算法的具体实现；排错方法算法设计错误：代入数据验证（对复杂算法无效）程序设计错误：编译检查、结果不对、或出现异常解决方法：跟踪调试、设置监视点、逐步检查,第三章作业,阅读教科书第三章练习题要求：提供变量说明、流程图73页：3.1、3.2、3.3、3.4上机作业74页：3.1、3.2换硬币：把1元人民币换成50枚5分、2分、1分的硬币，有多少种换法？自测题（自我检测，要求）,