C程序设计第三版(谭浩强) 第二章 程序的灵魂-算法.ppt

第二章 程序的灵魂—算法 一、算法的概念 二、算法的简单举例 三、算法的特性 四、怎样表示一个算法 五、结构化程序设计 一、算法的概念 程序=数据结构+算法 程序=算法+数据结构+程序设计方法+语言工具和环境 算法：为了解决一个问题而采取的方法和步骤。 2.2简单算法举例 例2.1 求1×2 ×3 ×4 ×5 算法： s1：使p=1； s2: 使i=2； s3: 使p ×i ，乘积放在变量p中，表示p=p × i; s4: 使i的值加1，即i+1 i; s5: 如果不大于5，返回重新执行步骤s3和s5;否则算法结束。 p=5 题目：1×3 ×5 ×7 ×9 ×11 算法： s1:1 p s2:3 i s3:p× i p s4:i+2 i s5:若i≤11,返回s3；否则，结束。 例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来 　用表示学生学号，ni代表第i个学生,g代表学生成绩，gi代表第i个学生成绩; 算法： s1:1 　i; s2:如果gi≥80,则打印ni和gi，否则不打印 s3:i+1 　i; s4:如果i≤50，返回s2，继续执行；否则，算法结束。 例2.3　判断2000-2500年中的闰年，将结果输出 判断闰年的条件： １、能被4整除，但不能被100整除; ２、能被100整除，又能被400整除; s1:2000 　y; s2:如果y不能被４整除,则输出y “不是闰年” ； s3:若y能被４整除,不能被100整除，则输出y “是闰年”，然后转到s6. s4:若y能被100整除,又能被400整除，则输出y “是闰年”，否则“不是闰年”然后转到s6. s5:输出“不是闰年” s6:y+1 y; s7:当y≤2500时，转到s2继续执行，如果y≥2500时，算法结束。 例２.4 求-1/2+1/3-1/4+…+1/99-1/100 算法分析： １、符号变化规律 　　sign=(-1) ×sign ２、分母变化规律 　　 deno=deno+1 ３、每一项 　　term=sign ×(1/deno) ４、求和 　　 sum=sum+term ５、起始值和终止值 算法 s1:sign=1 s2:sum=1 s3:deno=2 s4:sign=(-1) ×sign s5:term=sign ×(1/deno) s6:sum=sum+term s7:deno=deno+1 s8:若deno≤100返回s4;否则算法结束。 例２.5　对于一个大于或等于３的正整数，判断它是不是一个素数。 算法： s1:输入n的值; s2:i=2; s3:n被i除，得余数r; s4:如果r=0,表示n能被i整除，则打印n “不是素数” ，算法结束；否则执行s5; s5:i+1 i; s6:如果i≤n-1,返回s3;否则打印n“是素数”,然后结束。 2.3 算法的特性 １、有穷性; ２、确定性; ３、有零个或多个输入; ４、有一个或多个输出; ５、有效性; 2.4　怎样表示一个算法 一、用自然语言表示 二、用流程图表示 三、用Ｎ－Ｓ图表示 四、用伪代码表示 2.4.2　用流程图表示算法 流程图是用各种框图表示各种操作。 例2.6 将例2.1求５！的算法用流程图表示，流程图为： 例2.7　将例2.2的算法用流程图表示 例2.10 将例2.5判断素数的算法用流程图表示 2 三种基本结构 直到型循环 只有一个入口； 只有一个出口； 注意：菱形框有2个出口，选择结构的出口只有一个； 结构内的每一部分都有机会被执行到； 结构内不存在“死循环”； 基本结构 2.4.4 用N-S流程图表示算法 例2.11 求5！算法的N-S图表示 例2.12 求50名学生中成绩高于80分的学号和成绩打印出来的算法的N-S图表示 例2.13 将判断闰年的算法用N-S图表示 例2.14 求例2.4的算法的N-S图 例2.15 求例2.5判断素数的算法的N-S图 2.4.5 用伪代码表示算法 1、打印x的绝对值的算法 IF x is positive THEN print x ELSE print -x 图 2.24 A B 图 2.28 p ≥100 成立 不成立 r =0.08 r =0.06 当n ≤10 p×(1+r) = p A B A本身是一个分支结构，B是一个循环结构 四搀眼洲琼寝最溪剃耙衷遁删脆拴案侦桐疏譬蹲的瞥品雏丑砒箔溉寡幕中C程序设计第三版(谭浩强) 第二章 程序的灵魂-算法C程序设计第三版(谭浩强) 第二章 程序的灵魂-算法 1=i 图 2.30 g i≥80 是 否 打印n i g i i +1 = i 直到