计算机算法初步 75页

第三章计算机算法初步一、解题方法及算法概念二、算法举例---穷举法三、算法举例---递推与迭代法四、良好的编程风格\n计算机求解问题的一般过程问题分析阶段认真分析问题，建立正确的模型,找出解题方法数据结构设计阶段找出所涉及的数据信息，根据已经建立的正确模型设计相应的数据结构算法设计阶段根据数据结构，详细设计计算步骤，并加以描述编码与调试阶段用计算机语言实现所描述的算法，并调试正确一、解题方法及算法概念\n举例：求绿化带宽度如图：在长500m、宽300m的地域内保护80000m2的地块，求沿四周植树建设绿化带的宽度。80000m2500m300mx分析：把题目中提出的问题数学化设x：绿化带宽度length：地块长度width：地块宽度area：保护面积列出计算式：area=(length-2x)(width-2x)\n得到一元二次方程：4x2-2(length+width)x+length*width-area=0找出计算方法X=根据求根公式求解方程找出算法用C语言写出程序调试和测试计算b计算Δ的开方计算x1计算x2输出x1和x2开始结束b2-4ac-b±2a\n算法概念算法解题过程（步骤）的具体描述可完全精确执行、有确定结果的有穷指令序列算法的控制结构选择结构（如：C语言的if语句）循环结构（如：C语言的while语句）顺序结构（语句组）3种结构可以满足各种算法的所有控制要求\n算法描述的必要性程序设计过程算法设计程序实现算法描述：描述解题逻辑，验证正确性独立于程序设计语言程序实现：利用程序设计语言的功能，实现算法熟悉语言的语法、语义、支撑环境\n算法描述方法自然语言描述易于理解；与计算机语言差别较大，不严谨，容易出现二义性图形方式描述比较直观，无二义性，易于掌握，过度为编码比较容易流程图(P60表3-1)、N-S图、PAD图等伪代码方式描述很严谨，与计算机语言很接近，很容易过度为编码，掌握的难度略大\n起止框I/O框处理框判断框调用框连接框有向边常用流程图符号(P60表3-1)\n用流程图表示算法顺序结构选择结构ynyn\n循环结构YNYN\n用N-S图表示算法AB顺序结构PTFAB选择结构当P成立A直到P成立A当型循环（先判断条件）直到型循环（后判断条件）\n用PAD图表示算法AB顺序结构P选择结构当型循环（先判断条件）直到型循环（后判断条件）ABAPAP\n伪码描述例：求5个整数之和数据分析sum保存已经输入的整数之和算法描述：赋值0sum重复执行5次2.1读入一个整数2.2累加到sum输出整数和sum仅考虑主要的数据对象和控制结构程序实现阶段考虑数据对象和控制结构的具体实现\n3.1实例1：考试成绩统计任务：输入某班级人数和某课程的考试成绩（100分制），输出及格率(>60)和不及格率。问题分析（基本方法）输入学生人数后，逐个输入成绩，判断及格否，统计及格人数和不及格人数数据分析班级人数num及格人数pass不及格人数fail输入成绩score\n过程描述（流程图）初值设置0pass0fail读入成绩score读入学生人数numnum=0score<60fail加一num减一pass加一num减一计算及格率pass/(pass+fail)和不及格率fail/(pass+fail)并输出YNYN\n算法的验证模拟算法的计算过程，跟踪数据的变化动作numpassfailScore初值设置00输入人数3输入分数2169输入分数1157输入分数0282输出\n程序结构设计（本题）流程图的结构从外层到内层顺序循环选择程序结构复合语句while语句if语句while条件：num==0if条件：score<60细节问题输出格式：65.5%涉及浮点数的处理\n程序实现#includemain(){intnum,pass,fail,score;while(0!=num){}}printf(“输入分数：”);scanf(“%d”,&score);if(score<60){fail+=1;num-=1;}else{pass+=1；num-=1;}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”,&num);初值设置和输入学生人数输出及格率和不及格率输入分数统计及格人数和不及格人数\n语言现象赋值表达式pass=(fail=0)赋值运算符=右结合简化赋值（自反运算、复合赋值）pass+=1等价于pass=pass+1自动类型变换printf(“passed%lf\%\n”,100.0*pass/num);强制类型变换（类型名）表达式/*改变其数据类型*/转义字符\%或%%用于输出%\n设计方法分析计算机科学家尼克劳斯·沃思（NiklausWirth）提出Programs=Algorithms+DataStrcture程序=算法+数据结构程序设计过程问题定义：输入输出要求（数据与格式）数据结构：分析需要保存的信息，组织数据结构算法设计：编制解题步骤程序编码：选用程序设计语言，实现解题步骤程序测试：排错和测试\n例3-2求解一元二次方程问题分析一元二次方程可以写成ax2+bx+c=0方程由三个系数a、b、c惟一确定需要用户输入三个系数，然后根据一元二次方程的求解规则计算最终的结果，并将结果显示输出\n流程剖析变量t1,t2保存数学计算中的中间结果输入a,b,cb2-4act1t1=0YNt1t2t1>0输出-b/2a输出(-b±t2)/2a输出“无解”YN\n程序实现#include#includemain(){inta,b,c,t1;doublet2;scanf(“%d%d%d”,&a,&b,&c);t1=b*b–4*a*c;if(t1==0)printf(“x=%lf\n”,-b/(2.0*a));elseif(t1>0){t2=sqrt((double)t1);printf(“x1=%lf,x2=%lf\n”,(-b+t2)/(2*a),(-b-t2)/(2*a));}elseprintf(“无解\n”);}类型转换数学函数说明求平方根强制类型转换\n程序测试测试设计考虑数据的各种取值，准备测试用例检查每个程序分支b2-4ac等于0，大于0，小于0测试用例121b2-4ac=0263b2-4ac=12433b2-4ac=-39\nTC程序跟踪TURBOC跟踪调试F7单步跟踪设置监视点(Watch):Ctrl+F7输入变量名跟踪过程message窗将显示被跟踪变量的值\n学习方法算法的学习（长期任务）利用变量就是存储器的概念，考虑解题过程中必须保存的数据利用3种控制结构（顺序、选择、循环），考虑数据变化过程，设计处理过程应能够熟练地设计数据结构和简单的算法程序设计语言的学习阅读程序实例，理解新的语言现象程序设计实践，上机排错调试对主要语言功能和上机编程操作应该达到十分熟练\n二、算法举例---穷举法（P63）穷举法也称为枚举法，是一种一一列举各种情况的求解问题的方法。基本思想：对问题的所有可能情形一一罗列，直到找出符合条件的解或将全部可能情形都测试过为止。\n实例3素数的判断题目判断给定的整数（大于1），是否为素数。问题分析素数（质数）是指除了1和它本身外，没有其它因子的大于1的整数。例如23131723等是素数41220等不是素数\n编程思路：要判断给定整数a是不是素数，应该根据素数的定义，用2、3、…、a-1分别去试除如果其中有能整除a的数，则a不是素数如果这些数都不能整除a，则a是素数只要找到一个能整除a的数，就能断定a不是素数，因此这时应提前退出循环循环结束后判是哪种情况，输出相应信息算法流程图：P64\n算法描述NY开始输入a2ii<=a-1i加1a%i==0结束输出“不是素数”输出“是素数”YNi>a-1YN\nelse#includemain(){inti,a;printf("Inputa(>1):");scanf("%d",&a);for(i=2;i<=a-1;i++)if(a%i==0)break;if(i>a-1)/*用2、3、…、a-1去试*//*找到因子提前退出*//*若真，说明正常退出，是素数*//*若假，说明提前退出，不是素数*/printf("%disaprimenumber.\n",a);printf("%disnotaprimenumber.\n",a);}讨论为减少循环次数，只需用2~a/2之间或用2~a1/2之间的整数试除\n第一次运行：Inputa(>1):1111isaprimenumber.第二次运行：Inputa(>1):1515isnotaprimenumber.运行情况：\n3.4实例4百钱买百鸡问题陈述某人有钱百枚，希望买一百只鸡；假设不同的鸡价格不同，公鸡5枚钱一只，母鸡3枚钱一只，而1枚钱可以买3只小鸡。试问如果正好使用百枚钱买到一百只鸡，其中有几只公鸡、母鸡和小鸡。解题思路（穷举法）考虑公鸡、母鸡和小鸡数量的所有可能的取值，依次检查是否构成了问题的解，找出价钱正好是100的组合约束条件：各种鸡的数量一定小于100，数量之和为100数据结构公鸡数量x母鸡数量y小鸡数量z5x+3y+z/3=100x+y+z=100数学模型\n算法设计（用伪码表示）1：0x2：如果x<=100/5（即20）2.1：0y2.2：如果y<=100/3（即33）2.2.1：0z2.2.2：如果z<=1002.2.2.1：如果x+y+z=100并且5x+3y+z/3=1002.2.2.1.1：输出x,y,z（解）2.2.2.2：z++,重复2.2.22.2.3：y++,重复2.22.3：x++,重复23：结束\n流程图开始0xx<=20y<=330y0zz<=100判断条件输出x,y,zz加1y加1结束x加1YNYYNNYN\n程序实现循环控制变量明确的情况：采用for语句包括循环次数固定的情况实数的比较不用x==y用fabs(x-y)<1e-5(差的绝对值小于10-5)\n程序编码#include#includemain(){intx,y,z;/*公鸡、母鸡、小鸡的个数*/for(x=0;x<=100/5;x++)for(y=0;y<=100/3;y++)for(z=0;z<=100;z++){if(x+y+z==100&&/*公鸡、母鸡、小鸡的个数之和为100*/fabs(5*x+3*y+z/3.0–100)<1e-5)/*一共使用百元*/printf(“x=%d,y=%d,z=%d\n”,x,y,z);}}\n结果与分析x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84笨拙的穷举法符合计算机解题的特点\n程序说明逻辑运算与&&或||非！自增和自减运算（++,--）前置：++i等效于i=i+1后置：i++计算在得到i的值之后，将i加一求绝对值doublefabs(doublex);求x的绝对值数学计算头文件：math.h\n浮点数的判断问题机器中二进制表示的浮点数是有误差的判断问题：doublex,y;if(x==y)应使用if(fabs(x-y)<0.00001)控制误差限制在一定的精度内即可。浮点常量的默认类型为doublefloatx;if(x==-1.2)注意：类型不一致可写成：1e-5\n#includemain(){intx,y,z;for(x=0;x<=20;x++)for(y=0;y<=33;y++)for(z=0;z<=100;z++){if(x+y+z==100&&15*x+9*y+z==300)printf(“x=%d,y=%d,z=%d\n”,x,y,z);}}程序代码(用精确值整型处理)\n改进的程序代码（减少执行时间）#includemain(){intx,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=%d\n”,x,y,z);}}只用两层循环。\n穷举法小结基本方法通过分析，确定可能的取值范围对该范围的每个值进行检测，找出所有符合要求的值可以用循环语句实现穷举优点容易理解、不会遗漏某些解缺点时间效率欠佳\n穷举法小结特点常用于问题有多个(有限)解的情况当没有或很难找到解析方式求解时可使用穷举法时间效率不是最佳的\n三、算法举例--递推与迭代法在计算机数值计算中，递推也称为迭代。递推基本策略是将复杂的运算划分为可以重复操作的若干个简单的运算，进而充分利用计算机擅长重复计算的特点。递推求解的基本思想：不断用变量的旧值递推其新值的过程。采用循环结构完成一个迭代处理过程。关键在于找出递推公式和边界条件（初始值、终止条件）P67\n实例5Fibonacci序列问题Fibonacci（斐波那契）序列有如下定义：１，１，２，３，５，８，１３，２１，３４，．．．．．．要求：输出斐波纳契（Fibonacci）级数的前三十项，并一行输出6项。\n问题分析解决Fibonacci序列的递推计算方法（1）序列的头两个数已知；（2）已知连续的两个Fibonacci数，可以算下一个数。数据对象解决应用问题：a,b,next（long类型）解决输出问题：n（int类型）\n求解过程+abnext第5项++abnext第3项abnext第4项abnext第6项+……112812323535next=a+b;a=b;b=next;规律：\n开始结束输出前两项初始设置a1，b1计数n2，i3i<=30NY输出当前项nextnexta+b计数n增一n/6的余数为0ab，bnext循环计数i增一输出回车换行符YN算法流程选择结构\n#includemain(){inti,n;longa,b,next;}a=b=1;printf("%8ld%8ld",a,b);n=2;/*处理前两项*/for(i=3;i<=30;i++){next=a+b;a=b;b=next;}/*处理后28项*/printf("%8ld",next);n++;if(n%6==0)printf("\n");/*输出并控制换行*/程序实现\n运行结果如下：112358132134558914423337761098715972584418167651094617711286574636875025121393196418317811514229832040\n实例6：求圆周率π问题分析圆周率π的计算公式：π=4–4/3+4/5–4/7+4/9–4/11+…数据对象PI表示圆周率π，float或double。而且有一定的精度要求。item：每一个数据项，类型同PI。sign：保存符号\n算法描述终止条件：由于数据项的绝对值是递减的，且相邻项的符号不同，如果第n个数据项的绝对值已经小于精度值，则前n项之和一定已经满足精度\n#include#includemain(){intsign=1;longi=1;doublePI=0.0,item;do{item=sign*4.0/(2*i++-1);sign=-sign;PI+=item;}while(fabs(item)>1e-4);/*数据项精度控制循环*/printf(“PI=%lf\n”,PI);}程序代码\n实例7：按位分解整数P71题目要求从键盘输入一个整数，然后将它的每一位分解成独立的数字字符并输出之。问题分析利用整除和求余运算实现将整数分解例如，对整数73267326/1000可得到最高位7；7326%1000可得到其余的位数326这种方法要求首先获得整数最高位的权（本例为1000），然后从高向低逐个分离出每位数字\n算法描述NY开始输入x计算整数最高位权nn>=1x/n的余数xn/10n（商）结束打印x/n\n#includemain(){longx,y,n;printf(“Enteraninteger:”);scanf(“%ld”,&x);y=x;/*保存x*/n=1;while(y>=10){/*计算整数最高位权n*/n*=10;y=y/10;}do{/*分解出每一位*/printf(“%ld\t”,x/n);x=x%n;n=n/10;}while(n>=1);}程序代码\n递推与迭代法小结思路利用上一个或上几个值推出后一个值，使后一个值与问题的解更接近要点建立递推或迭代关系（递推公式）有明确的初始值有明确的结束条件\n3.5实例5统计数字字符的出现次数任务统计一行输入字符中每个数字字符的出现次数数据分析应保存10个整数；（需要一组相关数据）设置数组intdigits[10]每个元素存一个数字字符的出现次数例如：数字字符3的出现次数保存在digits[3]中输入字符ch\n算法的描述（穷举法）1.digits数组元素初始化为02.读入一个字符ch3.如果ch不是换行符，则3.1如果ch是数字字符，则3.1.1digits[ch]加一3.2读入一个字符ch3.3重复处理34.输出digits数组先考虑整体算法\ndigits数组初始化digits[ch]加1再读chch=‘\n’ch是数字输出统计数字读chYYNN流程图？？\n算法细化digits数组元素初始化1.设循环变量i为02.当i小于10时2.1设0digits[i]2.2i加一2.3重复2局部算法与外部逻辑处理关系不大输出digits数组1.设循环变量i为02.当i小于10时2.1输出digits[i]2.2i加一2.3重复2\n程序结构设计算法过程分析3个循环：主算法、2个细化算法程序结构采用while语句循环控制：换行符检查、数组下标数据结构一维整数数组下标问题：数字字符整数（利用ASCII值）ch–‘0’0\n#includemain(){intdigits[10],i=0;charch;while(i<10)digits[i++]=0;scanf(“%c”,&ch);while(ch!=‘\n’){if(ch>=‘0’&&ch<=‘9’)digits[ch–‘0’]+=1;scanf(“%c”,&ch);}i=0;while(i<10){printf(“%d:%d\n”,i,digits[i]);i++;}}利用字符的ASCII值程序实现自增运算赋值后加1整数数组逻辑与运算\n程序说明数组说明（定义）类型数组名[数组大小N]；数组引用数组名[表达式]下标范围0到N-1(下标越界,编译查不出来)字符的运算以其ASCII值参加整数运算C语言支持不同类型的混合运算如：（‘c’+2）是ASCII的值printf(“%d”,‘c’+2);101printf(“%c”,‘c’+2);e\n结构化程序设计方法自顶向下首先描述外层核心算法与主要数据对象突出解题逻辑，忽略细节控制结构不超过两层循环限制了算法的难度逐步求精在确立了外部算法的基础上逐步描述各个细节算法及其相关数据对象（如：上例中的digits初始化和输出）复杂情况下，细节算法仍应进一步逐步求精\n数据与变量数据的分析分析算法中，需要保存的数据有明确的意义，不多不少，避免重复变量的设置为数据的保存提供存储空间提供数据结构（如：数组等）避免同一变量在不同时刻代表不同的数据影响程序可读性的关键因素之一\n方法分析基于数学关系数学模型是解题方法算法是解题过程的描述（穷举、递推、…）程序设计是解题过程的具体实现穷举过程、迭代过程的算法实现可以用算法的循环控制编程中用循环语句实现实现细节熟悉各种运算、各种数据类型的使用方法\n四、良好的编程风格依据规约，编写正确的程序完全按要求实现功能格式一行一语句。太长的语句可占多行，使其不溢出画面。括号嵌套缩进对应，不要齐头并进适当留空格、空行等，增加可读性…下面是一段微软的代码：\nintWinMain(HINSTANCEhInstance,HINSTANCEhPrevInstance,LPSTRlpCmdLine,intnCmdShow){MSGmsg;HACCELhAccelTable;//InitializeglobalstringsLoadString(hInstance,IDS_APP_TITLE,szTitle,MAX_LOADSTRING);LoadString(hInstance,IDC_A,szWindowClass,MAX_LOADSTRING);MyRegisterClass(hInstance);//Performapplicationinitialization:if(!InitInstance(hInstance,nCmdShow)){returnFALSE;}hAccelTable=LoadAccelerators(hInstance,(LPCTSTR)IDC_A);//Mainmessageloop:while(GetMessage(&msg,NULL,0,0)){if(!TranslateAccelerator(msg.hwnd,hAccelTable,&msg)){TranslateMessage(&msg);DispatchMessage(&msg);}}returnmsg.wParam;}\n不好的例子#includeintmain(){printf("Hello,World.\n");return0;}main(){inti,x,max=0;for(i=0;i<80;i++){x=getchar();if(x>max){max=x;}}}//与本书P47对比\n每个变量有明确的角色注释（反映你的文字水平）文件注释函数注释程序片断关键点注释关键数据结构注释通常没必要每句话写注释程序员友好你的程序是给人看的，不要写的晦涩难懂。\n正确性可懂度时间复杂度空间复杂度健壮性可扩展性可移植性…\n本章小结算法用一系列动作来描述问题求解的过程算法描述方法流程图：图形化的算法描述伪码：算法过程的动作说明算法设计与实现算法设计描述解题方法；程序设计描述算法的具体实现；排错方法算法设计错误：代入数据验证（对复杂算法无效）程序设计错误：编译检查、结果不对、或出现异常解决方法：跟踪调试、设置监视点、逐步检查\n第三章作业阅读教科书第三章练习题要求：提供变量说明、流程图73页：3.1、3.2、3.3、3.4上机作业74页：3.1、3.2换硬币：把1元人民币换成50枚5分、2分、1分的硬币，有多少种换法？自测题（自我检测，要求）