C语言程序设计第二章课件

C语言程序设计主讲：龚文引第二讲：程序设计的灵魂——算法2.1算法的概念要利用计算机处理问题，光学习语言的语法规则还不够，最重要的是要学会针对各类型的问题，拟定出有效的解题方法和步骤。解题方法和步骤就是算法。算法为了解决一个问题而采取的有限步骤。计算机算法如何使计算机一步一步地工作的具体过程。2.1算法的概念(Cont.)利用计算机处理问题的步骤：设计好算法——算法设计；用计算机语言实现算法——程序设计。算法设计还要充分考虑算法的好坏。衡量算法好坏的主要标准：程序简练执行速度快占空间少2.1算法的概念(Cont.)算法的特点有穷性确定性有效性有零个或多个输入有一个或多个输出2.1算法的概念(Cont.)例2.1考虑的算法算法①：直接表达。直接用语句s=1+2+3+4+5+6+7+8+9+10101isi当项数较多时该算法不适用2.1算法的概念(Cont.)算法②：迭代法（累加求和法）s=1+2+3+4+5+6+7+8+9+10算法步骤：①使s=0②使i=1③s+i→s④i+1→i⑤若i≤10转③，否则转⑥⑥输出s01123364105该算法通用，是好算法si+累加器计数器2.2算法的表示算法需要有统一的表示方法常见的表示方法有：自然语言流程图结构化程序图N-S流程图2.2算法的表示(Cont.)自然语言表示对于计算s=1+2+3+4+5+6+7+8+9+10用自然语言表示为：①使s=0（s为累加器）②使i=1（i为计数器）③s+i→s（累加求和公式）④i+1→i（计数器加1）⑤若i≤10转③,否则转⑥⑥输出s的值特点：通俗易懂；文字冗长、含义不大严格。2.2算法的表示(Cont.)流程图表示用流程图符号表示算法常用的流程图符号有：起至框输入输出框处理框流程线判断框对于计算s=1+2+3+4+5+6+7+8+9+10用流程图表示为：Starts+i→si+1→ii≤10输出sEnd0→s1→i直观形象，易于理解，次序清楚YN2.2算法的表示(Cont.)流程图包含以下部分表示相应操作的框带有箭头的流程线框内外必要的问题说明流程线不要忘记画箭头2.2算法的表示(Cont.)结构化表示传统的流程图有一个弊端：对流程线没有严格的限制，对于较复杂的算法可能会变成乱麻一般(BS型算法—aBowlofSpaghetti)为克服这一弊端，提出了由三个基本结构组成算法流程图的思想：结构化流程图2.2算法的表示(Cont.)结构化表示——顺序结构按固定顺序（从上到下或从左到右）执行的结构ABab2.2算法的表示(Cont.)结构化表示——选择结构根据条件p选择执行哪一个分支pABab成立不成立例：计算y=1/x当x≠0时y=10000当x=0时的算法流程图：选择结构开始输入xX=0?10000→y1/x→y输出y结束YN2.2算法的表示(Cont.)结构化表示——循环结构重复执行某些操作的结构：当型(while)循环和直到型(until)循环P1AAP2aabbYYNN当型循环直到型循环2.2算法的表示(Cont.)结构化表示的特点只有一个入口只有一个出口结构内每一部分都有机会被执行到不存在死循环pAAB观察前例：开始0→s1→iS+i→si+1→ii≤10输出s结束顺序结构循环结构yn2.2算法的表示(Cont.)N-S流程图表示N-S流程图的三个基本结构ABP成立不成立ABAB当P1直到P2顺序结构选择结构循环结构例：计算y=1/x当x≠0时y=10000当x=0时的N-S流程图：输入xx=0?是否10000→y1/x→y输出y例：计算s=1+2+3+4+5+6+7+8+9+10的N-S流程图：直到型当型0→s1→i输出s1→i0→ss+i→si+1→is+i→si+1→i输出si≤10直到i10算法设计实例判定2000～2500年中的每一年是否闰年，将结果输出。分析：闰年的条件是：能被4整除，但不能被100整除的年份都是闰年，如1996,2004年是闰年；能被100整除，又能被400整除的年份是闰年。如1600,2000年是闰年。不符合这两个条件的年份不是闰年。算法设计实例(Cont.)自然语言表示S1：2000→yS2：若y不能被4整除，则输出y“不是闰年”。然后转到S6。S3：若y能被4整除，不能被100整除，则输出y“是闰年”。然后转到S6S4：若y能被100整除，又能被400整除，输出y“是闰年”，否则输出“不是闰年”。然后转到S6。S5:输出y“不是闰年”。S6：y+1→yS7：当y≤2500时，转S2继续执行，若y＞2500，算法停止。算法设计实例(Cont.)流程图表示算法设计实例(Cont.)N-S图表示