第2童 程序的灵魂一算法
第2章程序的灵魂一算法 本章内容 1.算法的概念 2.简单算法举例 3.算法的特性 4.算法的表示 5.结构化程序设计方法
-2- 第2章 程序的灵魂—算法 本 章 内 容 1. 算法的概念 2. 简单算法举例 3. 算法的特性 4. 算法的表示 5. 结构化程序设计方法
第2章程序的灵魂一算法 2.1算法的概念 程序的几个要素 程序三算法+数据结构+程序设计方法+语言工具+环境 ☆算法是灵魂,程序语句是算法的体现 数据结构是加工对象 ◇语言是工具 编程需要采用合适的方法一结构化的程序设计方法
-3- 第2章 程序的灵魂—算法 2.1 算法的概念 程序的几个要素 程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具 + 环境 v 算法是灵魂，程序语句是算法的体现 v 数据结构是加工对象 v 语言是工具 v 编程需要采用合适的方法—结构化的程序设计方法
第2章程序的灵魂一算法 2.1算法的概念 广义算法 ◇算法是为解决一个问题而采取的方法和步骤。 对同一个问题,可以有不同的解题方法和步骤。 例如:求1+2+3+…+100 方法1:先进行1+2,再加3,再加4,一直加到100 方法2:100+(1+99)+(2+98)+…+(49+51)+50 100+50+49×100=5050
-4- 第2章 程序的灵魂—算法 2.1 算法的概念 广义算法 v 算法是为解决一个问题而采取的方法和步骤。 v 对同一个问题，可以有不同的解题方法和步骤。 例如：求1+2+3+…+100 方法1：先进行1+2，再加3，再加4，一直加到100。 方法2：100 + (1+99)+(2+98)+…+(49+51)+50 =100 + 50 + 49×100 = 5050
第2章程序的灵魂一算法 2.1算法的概念 计算机算法 即计算机能执行的算法 ◆数值运算的算法 可由库函数实现,如求函数的定积分等。 ◆非数值运算的算法 如査找、排序,事务管理系统等
-5- 第2章 程序的灵魂—算法 2.1 算法的概念 计算机算法 即计算机能执行的算法。 v 数值运算的算法 可由库函数实现，如求函数的定积分等。 v 非数值运算的算法 如查找、排序，事务管理系统等
第2章程序的灵魂一算法 2.2简单算法举例 例2.1求1×2×3×4×5 设被乘数为T,乘数为I,乘积结果仍放在变量T中,作为下一个被乘数。 S1:使T=1 S2:使 S3:使T×I,可表示为:T×I=T S4:使I的值加1,即I+1=I。 S5:如果I不大于5,返回重新执行S3,以及其后的步骤S4,S5;否则, 算法结束
-6- 第2章 程序的灵魂—算法 2.2 简单算法举例 例2.1 求1×2 ×3 ×4 ×5 设被乘数为T，乘数为I，乘积结果仍放在变量T中，作为下一个被乘数。 S1：使T = 1 S2：使I = 2 S3：使T ×I，可表示为：T ×I=>T。 S4：使I的值加1，即I+1=>I。 S5：如果I不大于5，返回重新执行S3，以及其后的步骤S4， S5；否则， 算法结束
第2章程序的灵魂一算法 2.2简单算法举例 例2.2有50个学生,要求将他们之中成绩在80分以上者打印出来。 用代表学生数,N代表第个学生的学号,G1代表第个学生成绩。 S1:1=>i S2:如果G1≥80,则打印N1和G1,否则不打印。 S3:i+1=>i S4:如果i≤50,返回S2,继续执行。否则,算法结束
-7- 第2章 程序的灵魂—算法 2.2 简单算法举例 例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来。 用i代表学生数，Ni代表第i个学生的学号， Gi代表第i个学生成绩。 S1：1=>i S2：如果Gi≥80，则打印Ni和 Gi，否则不打印。 S3：i+1=>i S4：如果i≤50，返回S2，继续执行。否则，算法结束
第2章程序的灵魂一算法 2.2简单算法举例 例23将20002500年中每一年是否闰年打印出来。 ☆闰年的条件是: 能被4整除,但不能被10整除的年份都是闰年 ■能被100整除,又能被400整除的年份是闰年。 设Y为年份,算法表示如下: S1:2000=Y S2:若Y不能被4整除,则打印Y“不是闰年”,然后转到S5。 S3:若Y能被4整除,不能被100整除,打印“是闰年”,然后转到S5。 S4:若Y能被100整除,又能被400整除,打印Y“是闰年”;否则打印 “不是闰年” S5:Y+1=>Y S6:当Y2500,算法停止
-8- 第2章 程序的灵魂—算法 2.2 简单算法举例 例2.3 将2000~2500年中每一年是否闰年打印出来。 v 闰年的条件是： 能被4整除，但不能被100整除的年份都是闰年； 能被100整除，又能被400整除的年份是闰年。 v 设Y为年份，算法表示如下： S1：2000=>Y S2：若Y不能被4整除，则打印Y“不是闰年” ，然后转到S5。 S3：若Y能被4整除，不能被100整除，打印“是闰年” ，然后转到S5。 S4：若Y能被100整除，又能被400整除，打印Y“是闰年” ；否则打印 “不是闰年” 。 S5：Y+1=>Y S6：当Y2500，算法停止
第2章程序的灵魂一算法 2.2简单算法举例 例24求1-1+11+1+…+1-1 234 99100 Sl: sign=l S2: sum=1 S3: deno=2 S4: sign=(1)x sign S5: term=sign x(1/deno) S6: sum=sum+term S7: deno=deno+ S8:若deno≤100返回S4;否则结束
-9- 第2章 程序的灵魂—算法 2.2 简单算法举例 例2.4 求 S1: sign=1 S2: sum=1 S3: deno=2 S4: sign=(-1) x sign S5: term=sign x (1/deno) S6: sum=sum+term S7: deno=deno+1 S8: 若deno≤100返回S4；否则结束。 100 1 99 1 .... 5 1 4 1 3 1 2 1 1
第2章程序的灵魂一算法 2.2简单算法举例 例2.5对一个大于或等于3的正整数,判断它是不是一个素数。 素数是指除1和该数本身之外不能被其它任何整数整除的数。 ◇判断一个数N(N≥3)是否素数的方法:将N作为被除数,将2到 sQRT(N)各个整数轮流作为除数,如果都不能被整除,则N为素 数 S1:输入N的值。 S2:i=2。 S3:N被i除,得余数R。 S4:如果R=0,表示N能被i整除,则打印N“不是素数”,算法结束。 否则执行S5。 S5:i+1=>i S6:如果i≤SQRT(N,返回S3。否则打印N“是素数”,算法结束。 10
-10- 第2章 程序的灵魂—算法 2.2 简单算法举例 例2.5 对一个大于或等于3的正整数，判断它是不是一个素数。 v 素数是指除1和该数本身之外不能被其它任何整数整除的数。 v 判断一个数N(N≥3)是否素数的方法：将N作为被除数，将2到 SQRT(N)各个整数轮流作为除数，如果都不能被整除，则N为素 数。 S1: 输入N 的值。 S2: i=2。 S3: N被i除，得余数R。 S4: 如果R=0，表示N能被i整除，则打印N“不是素数” ，算法结束。 否则执行S5。 S5: i+1=>i S6: 如果i≤SQRT(N)，返回S3。否则打印N“是素数” ，算法结束