第三章计算机算法初步

《第三章计算机算法初步》由会员分享，可在线阅读，更多相关《第三章计算机算法初步（75页珍藏版）》请在装配图网上搜索。

1、第三章第三章 计算机算法初步计算机算法初步一、解题方法及算法概念二、算法举例-穷举法三、算法举例-递推与迭代法四、良好的编程风格 计算机求解问题的一般过程计算机求解问题的一般过程n问题分析阶段问题分析阶段n认真分析问题，建立正确的模型认真分析问题，建立正确的模型,找出解题方法找出解题方法n数据结构设计阶段数据结构设计阶段n找出所涉及的数据信息，根据已经建立的正确模型设计相找出所涉及的数据信息，根据已经建立的正确模型设计相应的数据结构应的数据结构n算法设计阶段算法设计阶段n根据数据结构，详细设计计算步骤，并加以描述根据数据结构，详细设计计算步骤，并加以描述n编码与调试阶段编码与调试阶段n用计算机

2、语言实现所描述的算法，并调试正确用计算机语言实现所描述的算法，并调试正确一、解题方法及算法概念一、解题方法及算法概念举例：求绿化带宽度举例：求绿化带宽度如图：在长如图：在长500m500m、宽、宽300m300m的地域内保护的地域内保护80000m80000m2 2的地块，求沿四周植树建设绿化带的宽度。的地块，求沿四周植树建设绿化带的宽度。80000m2500m300mxn分析：把题目中提出的问分析：把题目中提出的问题数学化题数学化设设x：绿化带宽度：绿化带宽度length：地块长度：地块长度width：地块宽度：地块宽度area：保护面积：保护面积列出计算式：列出计算式：area=(leng

3、th-2x)(width-2x)得到一元二次方程：得到一元二次方程：4x2-2(length+width)x+length*width-area=0n找出计算方法找出计算方法X=根据求根公式求解方程n找出算法找出算法n用用C C语言写出程序语言写出程序n调试和测试调试和测试计算计算b计算计算的开方的开方计算计算x1计算计算x2输出输出x1和和x2开始开始结束结束b2-4ac-b2a算法概念算法概念n算法算法n解题过程（步骤）的具体描述解题过程（步骤）的具体描述n可完全可完全精确精确执行、有执行、有确定结果确定结果的的有穷有穷指令指令序列序列n算法的控制结构算法的控制结构n选择结构（如：选择结构

4、（如：C C语言的语言的 if if 语句）语句）n循环结构（如：循环结构（如：C C语言的语言的 while while 语句）语句）n顺序结构（语句组）顺序结构（语句组）n3 3种结构可以种结构可以满足各种算法满足各种算法的所有控制要求的所有控制要求算法描述的必要性算法描述的必要性n程序设计过程程序设计过程 算法设计算法设计 程序实现程序实现n算法描述：算法描述：n描述解题逻辑，验证正确性描述解题逻辑，验证正确性n独立于程序设计语言独立于程序设计语言n程序实现：程序实现：n利用程序设计语言的功能，实现算法利用程序设计语言的功能，实现算法n熟悉熟悉语言的语法、语义、支撑环境语言的语法、语义、

5、支撑环境算法描述方法算法描述方法n自然语言描述自然语言描述n易于理解；与计算机语言差别较大，不严谨，易于理解；与计算机语言差别较大，不严谨，容易出现二义性容易出现二义性n图形方式描述图形方式描述n比较直观，无二义性，易于掌握，过度为编码比较直观，无二义性，易于掌握，过度为编码比较容易比较容易n流程图流程图(P60(P60 表表3-1)3-1)、N-S图、图、PAD图等图等n伪代码方式描述伪代码方式描述n很严谨，与计算机语言很接近，很容易过度为很严谨，与计算机语言很接近，很容易过度为编码，掌握的难度略大编码，掌握的难度略大起止框起止框I/O框框处理框处理框判断框判断框调用框调用框连接框连接框有向

6、边有向边 n 常用流程图符号常用流程图符号(P60(P60 表表3-1)3-1)n用流程图表示算法用流程图表示算法顺序结构顺序结构选择结构选择结构ynyn循环结构循环结构YNYNn用用N-S图表示算法图表示算法AB顺序结构顺序结构PTFAB选择结构选择结构当当P成立成立A直到直到P成立成立A当型循环（先判断条件）当型循环（先判断条件）直到型循环（后判断条件）直到型循环（后判断条件）n用用PAD图表示算法图表示算法AB顺序结构顺序结构P选择结构选择结构当型循环（先判断条件）当型循环（先判断条件）直到型循环（后判断条件）直到型循环（后判断条件）ABAPAP伪码描述例：求伪码描述例：求5 5个整数之

7、和个整数之和n数据分析数据分析nsum sum 保存已经输入的整数之和保存已经输入的整数之和n算法描述：算法描述：1.1.赋值赋值 0 0 sum sum2.2.重复执行重复执行 5 5 次次2.12.1 读入一个整数读入一个整数2.22.2 累加到累加到 sumsum3.3.输出输出整数和整数和 sumsumn仅仅考虑考虑主要的主要的数据对象数据对象和和控制结构控制结构n程序实现阶段程序实现阶段考虑数据对象和控制结构的考虑数据对象和控制结构的具具体实现体实现3.1 3.1 实例实例1 1：考试成绩统计：考试成绩统计n任务：任务：n输入输入某班级人数和某课程的考试成绩（某班级人数和某课程的考试

8、成绩（100100分制），分制），输输出出及格率及格率(60)(60)和不及格率。和不及格率。n问题分析（基本方法）问题分析（基本方法）n输入学生人数后，输入学生人数后，逐个逐个输入成绩，输入成绩，判断判断及格否，及格否，统计统计及格人数及格人数和和不及格人数不及格人数n数据分析数据分析n班级人数班级人数numnumn及格人数及格人数passpassn不及格人数不及格人数failfailn输入成绩输入成绩scorescore过程描述（流程图）过程描述（流程图）初值设置初值设置0pass0fail读入成绩读入成绩score读入学生人数读入学生人数numnum=0score60fail加一加一nu

9、m减一减一pass加一加一num减一减一计算及格率计算及格率pass/(pass+fail)和不及格率和不及格率fail/(pass+fail)并输出并输出YNYN算法的验证算法的验证n模模拟拟算算法法的的计计算算过过程程，跟跟踪踪数数据据的的变变化化动作动作numnumpasspassfailfailScoreScore初值设置初值设置0 00 0输入人数输入人数3 3输入分数输入分数2 21 16969输入分数输入分数1 11 15757输入分数输入分数0 02 28282输出输出程序结构设计（本题）程序结构设计（本题）n流程图的结构流程图的结构n从外层到内层从外层到内层n顺序顺序 循环循

10、环 选择选择n程序结构程序结构n复合语句复合语句 while while 语句语句 if if 语句语句nwhile while 条件：条件：num=0num=0nif if 条件：条件：score 60score 60n细节问题细节问题n输出格式：输出格式：65.5%65.5%n涉及浮点数的处理涉及浮点数的处理程序实现程序实现#includemain()intnum,pass,fail,score;while(0!=num)printf(“输入分数：输入分数：”);scanf(“%d”,&score);if(score0输出输出-b/2a输出输出(-bt2)/2a输出输出“无解无解”YN程序

11、实现程序实现#include#includemain()inta,b,c,t1;doublet2;scanf(“%d%d%d”,&a,&b,&c);t1=b*b4*a*c;if(t1=0)printf(“x=%lfn”,-b/(2.0*a);elseif(t10)t2=sqrt(double)t1);printf(“x1=%lf,x2=%lfn”,(-b+t2)/(2*a),(-b-t2)/(2*a);elseprintf(“无解无解n”);类型转换类型转换数学函数说明数学函数说明求求平方根平方根强制类型转换强制类型转换程序测试程序测试n测试设计测试设计n考虑数据的各种取值，准备测试用例考虑数

12、据的各种取值，准备测试用例n检查每个程序分支检查每个程序分支nb2-4ac等于等于0，大于大于0，小于，小于0n测试用例测试用例n121b2-4ac=0n263b2-4ac=12n433b2-4ac=-39TC程序跟踪程序跟踪nTURBO C TURBO C 跟踪调试跟踪调试nF7F7单步跟踪单步跟踪n设置监视点设置监视点(Watch):(Watch):Ctrl+F7Ctrl+F7n输入变量名输入变量名n跟踪过程跟踪过程nmessagemessage窗将显示被跟踪变量的值窗将显示被跟踪变量的值学习方法学习方法n算法的学习（长期任务）算法的学习（长期任务）n利用利用变量变量就是就是存储器的概念存

13、储器的概念，考虑解题过程中，考虑解题过程中必须保存的数据必须保存的数据n利用利用3 3种控制结构种控制结构（顺序、选择、循环），考（顺序、选择、循环），考虑虑数据变化过程数据变化过程，设计处理过程，设计处理过程n应能够应能够熟练熟练地设计数据结构和简单的算法地设计数据结构和简单的算法n程序设计语言的学习程序设计语言的学习n阅读程序实例，理解新的语言现象阅读程序实例，理解新的语言现象n程序设计实践，上机排错调试程序设计实践，上机排错调试n对主要语言功能和上机编程操作应该达到对主要语言功能和上机编程操作应该达到十分十分熟练熟练二、算法举例二、算法举例-穷举法穷举法（P63P63）穷举法穷举法也称为

14、也称为枚举法枚举法，是一种一一列举各种，是一种一一列举各种情况的求解问题的方法情况的求解问题的方法。基本思想基本思想：对问题的所有可能情形一一罗列，：对问题的所有可能情形一一罗列，直到找出符合条件的解或将全部可能情形都直到找出符合条件的解或将全部可能情形都测试过为止。测试过为止。实例实例3素数的判断素数的判断n题目题目判断给定的整数（大于判断给定的整数（大于1 1），是否为素数。），是否为素数。n问题分析问题分析素数（质数）是指除了素数（质数）是指除了1 1和它本身外，没有其它和它本身外，没有其它因子的大于因子的大于1 1的整数。的整数。例如例如2 3 13 17 23 等是素数等是素数4 1

15、2 20 等不是素数等不是素数编程思路：编程思路：n要要判断给定整数判断给定整数a a是不是素数是不是素数，应该根据素数的，应该根据素数的定义，用定义，用2 2、3 3、a-1a-1分别去试除分别去试除n如果其中有能整除如果其中有能整除a a的数，则的数，则a a不是素数不是素数n如果这些数都不能整除如果这些数都不能整除a a，则，则a a是素数是素数n只要找到一个能整除只要找到一个能整除a a的数，就能断定的数，就能断定a a不是素数不是素数，因此这时应因此这时应提前退出循环提前退出循环n循环结束后判是哪种情况，输出相应信息循环结束后判是哪种情况，输出相应信息算法流程图：算法流程图：P64n

16、算法描述算法描述 NY开始开始输入输入a2iia-1YN else#includemain()inti,a;printf(Inputa(1):);scanf(%d,&a);for(i=2;ia-1)/*用用2 2、3 3、a-1a-1去试去试 */*找到因子提前退出找到因子提前退出*/*若真，说明正常退出，是素数若真，说明正常退出，是素数*/*若假，说明提前退出，不是素数若假，说明提前退出，不是素数*/printf(%d is a prime number.n,a);printf(%d is not a prime number.n,a);n讨论讨论n为为减少循环次数减少循环次数，只需用只需用

17、2a/2之间或之间或用用2a1/2之间的整数试除之间的整数试除第一次运行：第一次运行：Inputa(1):11 11isaprimenumber.第二次运行：第二次运行：Inputa(1):15 15isnotaprimenumber.运行情况：运行情况：3.4 3.4 实例实例4 4 百钱买百鸡百钱买百鸡n问题陈述问题陈述n某人有钱百枚，希望买一百只鸡；某人有钱百枚，希望买一百只鸡；n假设不同的鸡价格不同，公鸡假设不同的鸡价格不同，公鸡5 5枚钱一只，母鸡枚钱一只，母鸡3 3枚钱一枚钱一只，而只，而1 1枚钱可以买枚钱可以买3 3只小鸡。试问如果正好使用只小鸡。试问如果正好使用百枚钱百枚钱买

18、到一百只鸡买到一百只鸡，其中有几只公鸡、母鸡和小鸡。，其中有几只公鸡、母鸡和小鸡。n解题思路（穷举法）解题思路（穷举法）n考虑公鸡、母鸡和小鸡数量的所有可能的取值，依次检考虑公鸡、母鸡和小鸡数量的所有可能的取值，依次检查是否构成了问题的解，查是否构成了问题的解，找出找出价钱正好是价钱正好是100的组合的组合n约束条件：各种鸡的数量一定小于约束条件：各种鸡的数量一定小于100100，数量之和为数量之和为100n数据结构数据结构n公鸡数量公鸡数量x xn母鸡数量母鸡数量y yn小鸡数量小鸡数量z z5x+3y+z/3=100 x+y+z=100数学模型数学模型算法设计算法设计（用伪码表示）（用伪码

19、表示）1 1：0 0 x x2 2：如果如果 x=100/5 x=100/5（即（即2020）2.12.1：0 0 y y2.22.2：如果如果 y=100/3 y=100/3 （即（即3333）2.2.12.2.1：0 0z z2.2.22.2.2：如果如果z=100z=1002.2.2.12.2.2.1：如果如果 x+y+z=100 x+y+z=100 并且并且 5x+3y+z/3=1005x+3y+z/3=1002.2.2.1.12.2.2.1.1：输出输出 x,y,zx,y,z（解）解）2.2.2.22.2.2.2：z+,z+,重复重复2.2.22.2.22.2.32.2.3：y+,y

20、+,重复重复2.22.22.32.3：x+,x+,重复重复2 23 3：结束：结束流程图流程图开始开始0 xx=20y=330y0zz=100判断条件判断条件输出输出x,y,zz加加1y加加1结束结束x加加1YNYYNNYN程序实现程序实现n循环控制变量明确的情况：循环控制变量明确的情况：n采用采用 for for 语句语句n包括循环次数固定的情况包括循环次数固定的情况n实数的比较实数的比较n不用不用 x=yx=yn用用 fabsfabs(x-y)1e-5(x-y)1e-5n(差的绝对值小于差的绝对值小于1010-5-5)程序编码程序编码1.#include2.#include3.main()

21、4.5.intx,y,z;/*公鸡、母鸡、小鸡的个数公鸡、母鸡、小鸡的个数*/6.for(x=0;x=100/5;x+)7.for(y=0;y=100/3;y+)8.for(z=0;z=100;z+)9.if(x+y+z=100&10./*公鸡、母鸡、小鸡的个数之和为公鸡、母鸡、小鸡的个数之和为100*/11.fabs(5*x+3*y+z/3.0100)1e-5)12./*一共使用百元一共使用百元*/13.printf(“x=%d,y=%d,z=%dn”,x,y,z);14.15.结果与分析结果与分析x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4

22、,z=84笨拙的穷举法符合计算机解题的特点笨拙的穷举法符合计算机解题的特点程序说明程序说明n逻辑运算逻辑运算n与与&或或|非！非！n自增和自减运算（自增和自减运算（+,-+,-）n前置：前置：+i+i 等效于等效于 i=i+1i=i+1n后置：后置：i+i+计算在得到计算在得到 i i的值之后，将的值之后，将i i加一加一n求绝对值求绝对值ndouble double fabsfabs(double x);(double x);n求求 x x 的绝对值的绝对值n数学计算头文件：数学计算头文件：math.hmath.h浮点数的判断问题浮点数的判断问题n机器中二进制表示的浮点数是有误差的机器中二进

23、制表示的浮点数是有误差的判断问题：判断问题：double x,y;double x,y;if(x=y)if(x=y)应使用应使用 if(fabs(x-yif(fabs(x-y)0.000010.00001)控制误差限制在一定的精度内即可。控制误差限制在一定的精度内即可。n浮点常量浮点常量的默认类型为的默认类型为doubledoublefloat x;if(float x;if(x=-1.2x=-1.2)注意：类型不一致注意：类型不一致可写成：可写成：1e-5#includemain()intx,y,z;for(x=0;x=20;x+)for(y=0;y=33;y+)for(z=0;z=100;

24、z+)if(x+y+z=100&15*x+9*y+z=300)printf(“x=%d,y=%d,z=%dn”,x,y,z);n程序代码程序代码 (用精确值整型处理用精确值整型处理)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=%dn”,x,y,z);n只用两层循环。只用两层循环。穷举法小结穷举法小结n基本方法基本方法n通过分析，确定可能的取值范围通过分析，确定可能的取值范围

25、n对该范围的每个值进行检测，找出所有符合要对该范围的每个值进行检测，找出所有符合要求的值求的值n可以用循环语句实现穷举可以用循环语句实现穷举n优点优点n容易理解、不会遗漏某些解容易理解、不会遗漏某些解n缺点缺点n时间效率欠佳时间效率欠佳穷举法小结穷举法小结n特点特点n常用于问题有多个常用于问题有多个(有限有限)解的情况解的情况n当没有或很难找到解析方式求解时可使用穷举当没有或很难找到解析方式求解时可使用穷举法法n时间效率不是最佳的时间效率不是最佳的三、算法举例三、算法举例-递推与迭代法递推与迭代法n在计算机数值计算中，递推也称为迭代。在计算机数值计算中，递推也称为迭代。n递递推推基基本本策策略

26、略是是将将复复杂杂的的运运算算划划分分为为可可以以重重复复操操作作的的若若干干个个简简单单的的运运算算，进进而而充充分分利利用用计计算算机擅长重复计算的特点。机擅长重复计算的特点。n递递推推求求解解的的基基本本思思想想：不不断断用用变变量量的的旧旧值值递递推推其其新新值值的的过过程程。采采用用循循环环结结构构完完成成一一个个迭迭代代处处理过程。理过程。n关关键键在在于于找找出出递递推推公公式式和和边边界界条条件件（初初始始值值、终止条件）终止条件）P67实例实例5 Fibonacci 5 Fibonacci 序列序列n问题问题FibonacciFibonacci（斐波那契）序列有如下定义：斐波

27、那契）序列有如下定义：，要求要求：输出斐波纳契（：输出斐波纳契（FibonacciFibonacci）级数的级数的前三十项，并一行输出前三十项，并一行输出6 6项。项。n问题分析问题分析解决解决FibonacciFibonacci序列的递推计算方法序列的递推计算方法（1 1）序列的头两个数已知；序列的头两个数已知；（2 2）已知连续的两个）已知连续的两个FibonacciFibonacci数，可以算下一个数。数，可以算下一个数。n 数据对象数据对象 解决应用问题：解决应用问题：a a,b,next,b,next（longlong类型）类型）解决输出问题：解决输出问题：n n （intint类型

28、）类型）n求解过程求解过程+abnext第第5项项+abnext第第3项项abnext第第4项项abnext第第6项项+112812323535next=a+b;a=b;b=next;规律：规律：开始开始结束结束输出前两项输出前两项初始设置初始设置a1，b1计数计数n2，i3i=30NY输出当前项输出当前项nextnexta+b计数计数n增一增一n/6的余数为的余数为0ab，bnext循环计数循环计数i增一增一输出回车换行符输出回车换行符YN算法流程算法流程选择结构选择结构#includemain()inti,n;longa,b,next;a=b=1;printf(%8ld%8ld,a,b);

29、n=2;/*/*处理前两项处理前两项*/for(i=3;i=30;i+)next=a+b;a=b;b=next;/*/*处理后处理后2828项项*/printf(%8ld,next);n+;if(n%6=0)printf(n);/*/*输出并控制换行输出并控制换行*/程序实现程序实现运行结果如下：运行结果如下：112358132134558914423337761098715972584418167651094617711286574636875025121393196418317811514229832040实例实例6 6：求圆周率：求圆周率n问题分析问题分析n圆周率圆周率的计算公式：的计算

30、公式：=44/3+4/54/7+4/94/11+n数据对象数据对象nPI PI 表示圆周率表示圆周率，floatfloat或或doubledouble。而且有一定而且有一定的精度要求。的精度要求。nitem item：每一个数据项，类型同每一个数据项，类型同PIPI。nsign sign：保存符号保存符号n算法描述算法描述 终止条件终止条件：由：由于数据项的绝于数据项的绝对值是递减的，对值是递减的，且相邻项的符且相邻项的符号不同，如果号不同，如果第第n个数据项的个数据项的绝对值已经小绝对值已经小于精度值，则于精度值，则前前n项之和一定项之和一定已经满足精度已经满足精度#include#incl

31、udemain()intsign=1;longi=1;doublePI=0.0,item;doitem=sign*4.0/(2*i+-1);sign=-sign;PI+=item;while(fabs(item)1e-4);/*数据项精度控制循环数据项精度控制循环*/printf(“PI=%lfn”,PI);n程序代码程序代码 实例实例7 7：按位分解整数：按位分解整数 P71P71n题目要求题目要求从键盘输入一个整数，然后将它的每一位分解成独立的数字字符并输出之。n问题分析问题分析n利用整除和求余运算实现将整数分解利用整除和求余运算实现将整数分解n例如，对整数例如，对整数 7326n7326

32、/1000可可得得到到最最高高位位7；7326%1000可可得得到到其其余的位数余的位数326n这这种种方方法法要要求求首首先先获获得得整整数数最最高高位位的的权权（本本例例为为10001000），然后从高向低逐个分离出每位数字，然后从高向低逐个分离出每位数字n算法描述算法描述 NY开始开始输入输入x计算整数最高位权计算整数最高位权nn=1x/n的余数的余数xn/10n（商）（商）结束结束打印打印x/n#includemain()longx,y,n;printf(“Enteraninteger:”);scanf(“%ld”,&x);y=x;/*/*保存保存x*/x*/n=1;while(y=1

33、0)/*计算整数最高位权计算整数最高位权n*/n*=10;y=y/10;do/*/*分解出每一位分解出每一位 */printf(“%ldt”,x/n);x=x%n;n=n/10;while(n=1);n程序代码程序代码 递推与迭代法小结递推与迭代法小结n思路思路n利用上一个或上几个值推出后一个值，使后一利用上一个或上几个值推出后一个值，使后一个值与问题的解更接近个值与问题的解更接近n要点要点n建立递推或迭代关系（递推公式）建立递推或迭代关系（递推公式）n有明确的初始值有明确的初始值n有明确的结束条件有明确的结束条件3.5实例实例5统计数字字符的出现次数统计数字字符的出现次数n任务任务n统计一行

34、输入字符中统计一行输入字符中每个数字字符每个数字字符的出现次数的出现次数n数据分析数据分析n应保存应保存1010个整数；（需要一组相关数据）个整数；（需要一组相关数据）n设置数组设置数组 intint digits10digits10n每个元素存一个数字字符的每个元素存一个数字字符的出现次数出现次数 例如：数字字符例如：数字字符3 3的出现次数保存在的出现次数保存在 digitsdigits3 3 中中n输入字符输入字符 chch算法的描述（穷举法）算法的描述（穷举法）1.digits1.digits数组元素数组元素初始化为初始化为0 02.2.读入一个字符读入一个字符 chch3.3.如果如

35、果chch不是不是换行符换行符，则，则3.13.1 如果如果chch是是数字字符，则数字字符，则3.1.1 3.1.1 digitschdigitsch 加一加一3.23.2 读入一个字符读入一个字符 chch3.33.3 重复处理重复处理3 34.4.输出输出digitsdigits数组数组先考虑整体算法先考虑整体算法digits数组初始化数组初始化digitsch加加1再读再读chch=nch是数字是数字输出统计数字输出统计数字读读chYYNN流程图流程图？算法细化算法细化ndigits digits 数组元素初始化数组元素初始化1.设循环变量设循环变量i为为02.当当i小于小于10时时2

36、.1设设0digitsi2.2i加一加一2.3重复重复2局部算法与外部逻局部算法与外部逻辑处理关系不大辑处理关系不大n输出输出 digits digits 数组数组1.设循环变量设循环变量i为为02.当当i小于小于10时时2.1输出输出digitsi2.2i加一加一2.3重复重复2程序结构设计程序结构设计n算法过程分析算法过程分析n3 3个循环：主算法、个循环：主算法、2 2个细化算法个细化算法n程序结构程序结构n采用采用 while while 语句语句n循环控制循环控制：换行符检查、数组下标：换行符检查、数组下标n数据结构数据结构n一维整数数组一维整数数组n下标问题下标问题：数字字符：数字

37、字符整数（利用整数（利用ASCIIASCII值）值）ch0 0 0#includemain()intdigits10,i=0;charch;while(i=0&ch=9)digitsch0+=1;scanf(“%c”,&ch);i=0;while(i10)printf(“%d:%dn”,i,digitsi);i+;利用字符的利用字符的ASCII值值程序实现程序实现自增自增运算运算赋值后加赋值后加1整数数组整数数组逻辑与运算逻辑与运算程序说明程序说明n数组说明（定义）数组说明（定义）n类型类型 数组名数组名 数组大小数组大小N N；n数组引用数组引用n数组名数组名 表达式表达式 n下标范围下标范

38、围 0 0 到到 N-1 (N-1 (下标越界下标越界,编译查不出来编译查不出来)n字符的运算字符的运算n以其以其ASCIIASCII值参加整数运算值参加整数运算nC C语言支持不同类型的混合运算语言支持不同类型的混合运算如：（如：（c+2）是）是ASCII的的值值printf(“%d”,c+2);101printf(“%c”,c+2);e结构化程序设计方法结构化程序设计方法自顶向下自顶向下首先描述外层核心算法与主要数据对象首先描述外层核心算法与主要数据对象突出解题逻辑，忽略细节突出解题逻辑，忽略细节控制结构不超过两层循环控制结构不超过两层循环限制了算法的难度限制了算法的难度逐步求精逐步求精在

39、确立了外部算法的基础上在确立了外部算法的基础上逐步描述各个细节算法及其相关数据对象逐步描述各个细节算法及其相关数据对象（如：上例中的（如：上例中的digitsdigits初始化和输出）初始化和输出）复杂情况下，细节算法仍应进一步逐步求精复杂情况下，细节算法仍应进一步逐步求精数据与变量数据与变量n数据的分析数据的分析n分析算法中，需要保存的数据分析算法中，需要保存的数据n有明确的意义，不多不少，避免重复有明确的意义，不多不少，避免重复n变量的设置变量的设置n为数据的保存提供存储空间为数据的保存提供存储空间n提供数据结构（如：数组等）提供数据结构（如：数组等）n避免避免同一变量在不同时刻代表不同的

40、数据同一变量在不同时刻代表不同的数据n影响程序可读性的关键因素之一影响程序可读性的关键因素之一方法分析方法分析n基于数学关系基于数学关系n数学模型是解题方法数学模型是解题方法n算法是解题过程的描述（穷举、递推、算法是解题过程的描述（穷举、递推、）n程序设计是解题过程的具体实现程序设计是解题过程的具体实现n穷举过程、迭代过程的算法实现穷举过程、迭代过程的算法实现n可以用算法的循环控制可以用算法的循环控制n编程中用循环语句实现编程中用循环语句实现n实现细节实现细节n熟悉各种运算、各种数据类型的使用方法熟悉各种运算、各种数据类型的使用方法四、良好的编程风格四、良好的编程风格n依据规约，编写正确的程序

41、依据规约，编写正确的程序n完全按要求实现功能完全按要求实现功能n格式格式n一行一语句。太长的语句可占多行，使其不溢一行一语句。太长的语句可占多行，使其不溢出画面。出画面。n括号嵌套缩进对应，不要齐头并进括号嵌套缩进对应，不要齐头并进n适当留空格、空行等，增加可读性适当留空格、空行等，增加可读性nn下面是一段微软的代码：下面是一段微软的代码：intWinMain(HINSTANCEhInstance,HINSTANCEhPrevInstance,LPSTRlpCmdLine,intnCmdShow)MSGmsg;HACCELhAccelTable;/Initializeglobalstrings

42、LoadString(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:whi

43、le(GetMessage(&msg,NULL,0,0)if(!TranslateAccelerator(msg.hwnd,hAccelTable,&msg)TranslateMessage(&msg);DispatchMessage(&msg);returnmsg.wParam;不好的例子#includeintmain()printf(Hello,World.n);return0;main()inti,x,max=0;for(i=0;imax)max=x;/与本书与本书P47对对比比n每个变量有明确的角色每个变量有明确的角色n注释（反映你的文字水平）注释（反映你的文字水平）n文件注释文件注释

44、n函数注释函数注释n程序片断关键点注释程序片断关键点注释n关键数据结构注释关键数据结构注释n通常没必要每句话写注释通常没必要每句话写注释n程序员友好程序员友好n你的程序是给人看的，不要写的晦涩难懂。你的程序是给人看的，不要写的晦涩难懂。n正确性正确性n可懂度可懂度n时间复杂度时间复杂度n空间复杂度空间复杂度n健壮性健壮性n可扩展性可扩展性n可移植性可移植性n本章小结本章小结n算法算法n用一系列动作来描述问题求解的过程用一系列动作来描述问题求解的过程n算法描述方法算法描述方法n流程图：图形化的算法描述流程图：图形化的算法描述n伪码：算法过程的动作说明伪码：算法过程的动作说明n算法设计与实现算法设

45、计与实现n算法设计描述解题方法；算法设计描述解题方法；n程序设计描述算法的具体实现；程序设计描述算法的具体实现；n排错方法排错方法n算法设计错误：代入数据验证（对复杂算法无效）算法设计错误：代入数据验证（对复杂算法无效）n程序设计错误：编译检查、结果不对、或出现异常程序设计错误：编译检查、结果不对、或出现异常n解决方法：跟踪调试、设置监视点、逐步检查解决方法：跟踪调试、设置监视点、逐步检查第三章作业第三章作业n阅读教科书第三章阅读教科书第三章n练习题练习题n要求：提供变量说明、流程图要求：提供变量说明、流程图n7373页：页：3.13.1、3.23.2、3.33.3、3.43.4n上机作业上机作业n7474页：页：3.13.1、3.23.2n换硬币：把换硬币：把1元人民币换成元人民币换成50枚枚5分、分、2分、分、1分的硬分的硬币，有多少种换法？币，有多少种换法？n自测题（自我检测，要求）自测题（自我检测，要求）