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

1、第二章 程序的灵魂算法,一、算法的概念 二、算法的简单举例 三、算法的特性 四、怎样表示一个算法 五、结构化程序设计,一、算法的概念,程序=数据结构+算法 程序=算法+数据结构+程序设计方法+语言工具和环境 算法：为了解决一个问题而采取的方法和步骤。,2.2简单算法举例,例2.1 求12 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,题目：13 5 7 9 11 算法： s1:1 p s2:3 i s3:p i p

2、s4:i+2 i s5:若i11,返回s3；否则，结束。,s5:若i11,返回s3? 结果会怎样？,例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来 用表示学生学号，ni代表第i个学生,g代表学生成绩，gi代表第i个学生成绩; 算法： s1:1 i; s2:如果gi80,则打印ni和gi，否则不打印 s3:i+1 i; s4:如果i50，返回s2，继续执行；否则，算法结束。,例2.3判断2000-2500年中的闰年，将结果输出 判断闰年的条件： 、能被4整除，但不能被100整除; 、能被100整除，又能被400整除;,s1:2000 y; s2:如果y不能被整除,则输出y “不

3、是闰年” ； s3:若y能被整除,不能被100整除，则输出y “是闰年”，然后转到s6. s4:若y能被100整除,又能被400整除，则输出y “是闰年”，否则“不是闰年”然后转到s6. s5:输出“不是闰年” s6:y+1 y; s7:当y2500时，转到s2继续执行，如果y2500时，算法结束。,算 法：,图 2.1,例.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

4、=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:若deno100返回s4;否则算法结束。,例.5对于一个大于或等于的正整数，判断它是不是一个素数。 算法： s1:输入n的值; s2:i=2; s3:n被i除，得余数r; s4:如果r=0,表示n能被i整除，则打印n “不是素数” ，算法结束；否则执行s5; s5:i+1 i; s6:如果in-1,返回s3;否则打印n“是素数”,然后结束。,n/2 or n,2.3 算法的特性,、有穷性; 、确定性; 、

5、有零个或多个输入; 、有一个或多个输出; 、有效性;,2.4怎样表示一个算法,一、用自然语言表示 二、用流程图表示 三、用图表示 四、用伪代码表示,2.4.2用流程图表示算法,流程图是用各种框图表示各种操作。,起止框,输入输出框,判断框,处理框,或 流程线,连接点,注释框,图 2.3,菱形框,连接点,例2.6 将例2.1求！的算法用流程图表示，流程图为：,例2.7将例2.2的算法用流程图表示,Y,N,图 2.9,输入ni,gi,ni,gi为第i个学生 的学号和成绩,g80?,打印ni,gi,N,N,Y,例2.9 将例2.4的算法用流程图表示 求1-1/2+1/3-1/4+1/99-1/100,

6、图 2.11,例2.10 将例2.5判断素数的算法用流程图表示,开始,2= i,n%i 的余数=r,i += i,结 束,Y,N,图 2.12,输入 n,r= 0 ?,N,打印 n 是素数,打印 n 不是素数,y,isqrt(n)?,2 三种基本结构,（1） 顺序结构 （2） 选择结构 （3） 循环结构 当型循环结构 直到型循环结构,顺序结构,分支结构,循环结构,当型循环,直到型循环,以上2个框图的作用是打印5个数,只有一个入口； 只有一个出口； 注意：菱形框有2个出口，选择结构的出口只有一个； 结构内的每一部分都有机会被执行到； 结构内不存在“死循环”；,归纳总结：,死循环,菱形框、分支结构,基本结构,2.4.4 用N-S流程图表示算法,顺序结构,分支结构,A,图 2.27,直到p1成立,当型循环,直到型循环,A本身是一个分支结构，B是一个循环结构,例2.11 求5！算法的N-S图表示,例2.12 求50名学生中成绩高于80分的学号和成绩打印出来的算法的N-S图表示,例2.13 将判断闰年的算法用N-S图表示,例2.14 求例2.4的算法的N-S图,图 2.33,例2.15 求例2.5判断素数的算法的N-S