《C语言程序设计第二章程序的灵魂算法》由会员分享，可在线阅读，更多相关《C语言程序设计第二章程序的灵魂算法（21页珍藏版）》请在金锄头文库上搜索。
1、主讲教师：李艺主讲教师：李艺C语言程序设计第二章程序的灵魂 - 算法主要内容主要内容2.1 2.1 算法的概念算法的概念2.2 2.2 简单算法举例简单算法举例2.3 2.3 算法的特性算法的特性2.4 2.4 怎样表示一个算法怎样表示一个算法2.5 2.5 结构化算法设计方法结构化算法设计方法22.1 算法的概念p沃思公式：沃思公式： 数据结构数据结构算法算法程序程序p具体化：具体化：程序算法数据结构程序设计方法语言工具和环境程序算法数据结构程序设计方法语言工具和环境对数据的描述，要指定对数据的描述，要指定数据的类型、数据的组数据的类型、数据的组织形式织形式对操作的描述，对操作的描述，即操作
2、步骤即操作步骤32.1 算法的概念u做任何事都有一定的次序和步骤；如：召开会议，购做任何事都有一定的次序和步骤；如：召开会议，购物等；物等；u算法是为解决一个问题而采取的方法和步骤；算法是为解决一个问题而采取的方法和步骤；u注意：注意：l解决同一个问题可以有不同的方法和步骤，方法有解决同一个问题可以有不同的方法和步骤，方法有优劣之分，优劣之分，l采用简单的和运算步骤少的方法为优！采用简单的和运算步骤少的方法为优！42.1 算法的概念p算法分两大类别算法分两大类别n数值运算算法：目的是求数值解，算法成熟；数值运算算法：目的是求数值解，算法成熟；n非数值运算算法：种类繁多，要求各异，难以规范非数值
3、运算算法：种类繁多，要求各异，难以规范52.2 简单算法举例p例例1求求n手工计算方法：手工计算方法：n通用的方法通用的方法: 设两个变量（被乘数设两个变量（被乘数p,乘数乘数i）l第一步：第一步：1=pl第二步：第二步：2=il第三步：第三步：pi=pl第四步：第四步： i+1=il第五步：若第五步：若i5，返回第三步；否则结束，返回第三步；否则结束，得，得2 2；，得，得24;24;，得，得6 6；=120=12062.2 简单算法举例p如果题目改为求如果题目改为求1357911l第一步：第一步：1=pl第二步：第二步：3=il第三步：第三步：pi=pl第四步：第四步： i+2=il第五步
4、：若第五步：若i11，返回第三步；否则结束，返回第三步；否则结束p用这种方法表示的算法具有通用性、灵活性用这种方法表示的算法具有通用性、灵活性72.2 简单算法举例p例例2 有有50个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在80分以上者打分以上者打印出来印出来p算法分析：用算法分析：用n表示学生学号，表示学生学号，n1代表第一个学生学号，代表第一个学生学号，ni代表第代表第i个学生的学号，个学生的学号，g1代表第一个学生成绩，代表第一个学生成绩，gi代代表第表第i个学生成绩个学生成绩p算法算法n第一步第一步: 1=in第二步第二步: 若若gi80则打印则打印ni和和gi，否则不打
5、印，否则不打印n第三步第三步: i+1=in第四步第四步: 若若i50返回第二步，否则算法结束返回第二步，否则算法结束82.2 简单算法举例p例例3 判断判断2000-2500年中的每一年是否闰年，将结果输年中的每一年是否闰年，将结果输出。出。p分析：闰年的条件：分析：闰年的条件：n能被整除，但不能被能被整除，但不能被100整除的整除的年份都是闰年，如年份都是闰年，如1996,2004年是闰年是闰年；年；n能被能被100整除，又能被整除，又能被400整除的年整除的年份是闰年，如份是闰年，如1600,2000年是闰年。年是闰年。n不符合这两个条件的年份不是闰年不符合这两个条件的年份不是闰年y不能
6、被整不能被整除除 y能被能被整除整除但不能但不能被被100整除整除闰年闰年非闰年非闰年y能被能被100整除整除又能被又能被400整除整除闰年闰年其他其他非闰年非闰年92.2 简单算法举例p算法算法1.2000=y2.若若y不能被整除，输出不能被整除，输出y“不是闰年不是闰年”，然后转到第，然后转到第5步步3.若若y能被整除，不能被能被整除，不能被100整除，则输出整除，则输出y“是闰年是闰年”，转第，转第6步步4.若若y能被能被100整除，又能被整除，又能被400整除，则输出整除，则输出y“是闰年是闰年”， 转第转第6步，（否则顺序执行）步，（否则顺序执行）5.输出输出y“不是闰年不是闰年”6
7、.y+1=y7.当当y2500时转第时转第2步，否则算法结束步，否则算法结束102.2 简单算法举例p例例4 求求 1- 1/2 + 1/3 -1/4+ + 1/99 - 1/100p算法：算法：1.1.sign=1sign=12.2.sum=1sum=13.3.denodeno=2=24.4.sign=-signsign=-sign5.5.term=signterm=sign(1/deno)(1/deno)6.6.sum=sum=sum+termsum+term7.7.denodeno=deno+1=deno+18.8.若若deno100deno100返回第返回第4 4步步, ,否则算法结束
8、否则算法结束112.3 算法的特性p算法应具有以下特点算法应具有以下特点:1.有穷性有穷性2.确定性确定性3.有零个或多个输入有零个或多个输入4.有一个或多个输出有一个或多个输出5.有效性有效性122.4 怎样表示一个算法p用自然语言表示算法：通俗易懂，但文字冗长，容易产生用自然语言表示算法：通俗易懂，但文字冗长，容易产生歧义。歧义。p用流程图表示算法：用流程图表示算法： 直观形象，容易理解。直观形象，容易理解。132.4 怎样表示一个算法p算法的三种基本结构算法的三种基本结构ABab顺顺序序结结构构选选择择结结构构pAB成立成立不成立不成立abAp不成立不成立成立成立ab.直直到到型型（un
9、til）循循环环当当型型（while）循循环环p成立成立Aba.不成立不成立142.4 怎样表示一个算法p例例1用流程图表示算法：用流程图表示算法：n第一步：第一步：1=pn第二步：第二步：2=in第三步：第三步：pi=pn第四步：第四步： i+1=in第五步：若第五步：若i5，返回第三，返回第三步；否则结束步；否则结束开始开始1=p2=i pi=pi+1=ii5N结束结束Y152.4 怎样表示一个算法p例例2 有有50个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在80分以上者打分以上者打印出来用流程图表示算法。印出来用流程图表示算法。n第一步第一步: 1=in第二步第二步: 若若g
10、i80则打则打印印ni和和gi，否则不打印，否则不打印n第三步第三步: i+1=in第四步第四步: 若若i50返回第返回第二步，否则算法结束二步，否则算法结束开始开始1=igi80YN打印打印ni和和gii+1=ii50N结束结束Y162.4 怎样表示一个算法p例用伪代码表示例用伪代码表示：开始开始 置置t的初值为的初值为1 置置i的初值为的初值为2 当当i，执行下面操作，执行下面操作 使使tti 使使ii1 (循环到此结束循环到此结束) 打印打印t的值的值结束结束172.4 怎样表示一个算法p也可以写成以下形式：也可以写成以下形式：BEGIN(算法开始算法开始) 1=t 2=i while
11、it i+1=i print tEND (算法结束算法结束)182.4 怎样表示一个算法p用计算机语言表示算法：用计算机语言表示算法：求！用求！用c语言表示语言表示void main( )void main( ) intint i,t; i,t; t=1; t=1; i=2; i=2; while(iwhile(i=5)=5)t=t*i; t=t*i; /* 120 */* 120 */ i=i+1;i=i+1; printf(%d,tprintf(%d,t); ); 192.5 结构化程序设计方法p一个结构化程序就是用高级语言表示的结构化算法一个结构化程序就是用高级语言表示的结构化算法p用三种基本结构组成的程序必然是结构化程序用三种基本结构组成的程序必然是结构化程序p结构化程序的特点结构化程序的特点n自顶向下自顶向下n逐步细化逐步细化n模块化设计模块化设计n结构化编码结构化编码20本章小结p算法的概念算法的概念p简单算法的设计简单算法的设计p算法的特性算法的特性p算法的表示（流程图、伪代码）算法的表示（流程图、伪代码）p算法的算法的3种结构种结构p结构化程序设计思想结构化程序设计思想21
