第二章 算法簡介及程序的基本结构.pptVIP

第二章 算法简介及程序的基本结构 本章要点： 了解算法的基本概念 掌握程序的基本结构 算法(algorithm)是对特定问题求解步骤的一种描述。 程序=数据结构+算法+程序设计方法+编程语言 2.1 算法的概念 例1. 有50个学生 ，要求将他们之中成绩在80分以上者打印出来。用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩， gi 代表第i个学生成绩，算法可表示如下： S1：1?i S2：如果gi ?80 ，则打印 ni 和gi ，否则不打印 S3： i+1 ?i S4: 如果 i? 50, 返回S2， 继续执行； 否则，算法结束。 2.2 简单算法举例 (用自然语言描述法） 例2 将学生百分成绩按分数段分级的程序。 该算法的核心部分是对输入的每一个数进行比较判断，以确定属于的级别。若学生成绩分布是均匀的，算法描述 如下： S1：1?i S2: 输入10000个数据，则需进行31500次比较。 S3: i+1 ?i S4:如果i ? 10000, 返回S2； 否则，算法结束。 转S3 转S3 转S3 转S3 转S3 分数 0—59 60—69 70—79 80—89 90—99 比例 0.05 0.15 0.4 0.3 0.10 学生成绩分布不是均匀的情况，算法改进如下： 输入10000个数据，仅需进行22000次比较。 例3：对一个大于或等于3的正整数，判断它是不是一个素数。 方法：将 n (其中n ?3) 作为被除数， 将2 到（n-1) 各个整数轮流作为除数，如果都不能被整除，则n为素数。 算法表示如下： S1：输入n的值 S2：2 ?i ( i 作为除数） S3: n 被 i 除，得余数 r S4: 如果 r 等于 0 ， 表示 n 能 被 i 整除，则打印 n “不是素数”，算法结束；否则执行S5 S5：i+1 ?i S6: 如果 i ? n-1, 返回S3；否则，打印 n “是素数”，算法结束。 例4：求 1-1/2 + 1/3 –1/4 +…+ 1/99 –1/100。 S1: 1 ?sign S2: 1 ?sum S3: 2 ?deno S4: (-1)*sign ?sign S5: sign*(1/deno) ?term S6: sum+term ?sum S7: deno+1 ?deno S8: 若deno ?100 返回S4；否则算法结束。 2.3 算法的特性 1.算法(algorithm)是对特定问题求解步骤的一种描述。 程序=数据结构+算法 2. 算法的五个特性： 有穷性：一个算法必须在执行有穷步之后结束。 确定性：算法的每一步必须是确切定义的。 对于相同输入必须得到相同结果 。 有效性：算法的每一步都是能够实现的，即可操作的。 输 入：算法有零个或多个输入。 有输出：算法执行完毕，必须有一个或若干个输出结果。 2.4 怎样描述算法 2.4.1 自然语言描述法 2.4.2 流程图表示 常用符号有: 2.4.3 程序的三种基本结构和改进的流程图（N-S结构流程图） 一、顺序结构 先执行A操作，再执行B操作，两者是顺序执行关系。 N-S结构流程图 二、选择结构 当P条件为真时，执行A模块，否则执行B模块。 三、循环结构 当P条件成立时，反复执行A,直到P为假。 1.当型循环结构 2.直到型循环结构 先执行A操作，再判断P是否为假，若P为假，再执行A，直到P为真为止。 2.4.5 用伪代码表示算法：用介于自然语言和计算机语言之间的文字和符号来描述算法 BEGIN 1 =i while(i ? 50) { input ni和gi i+1=I } 1 =i while(i ? 50) { if (gi =80) print ni和gi i+1=i } END