第二章算法及算法设计简介.ppt

第二章 算法及算法设计简介;算法的概念;实际上，一个程序除了以上两个主要要素之外，还应当采用 结构化程序设计方法进行程序设计，并且用某一种计算机语 言表示。因此，可以这样表示： 程序＝算法＋数据结构＋程序设计方法＋语言工具和环境 在这4个方面中，算法是灵魂，数据结构是加工对象，语言 是工具，编程需要采用合适的算法。算法是解决“做什么” 和“怎么做”的问题。;算法的表示 ;例1： 有50个学生 ，要求将他们之中成绩在80分以上者打印出来。用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩， gi 代表第i个学生成绩，算法可表示如下： S1：1?i S2：读入学号ni和成绩gi S3: 如果gi ?80 ，则打印 ni 和gi ，否则不打印 S4： i+1 ?i S5: 如果 i? 50, 返回S2， 继续执行； 否则，算法结束。 ;起止框;上例用流程图表示： ;3、用N－S图表示算法 ;（2）选择结构：; 上例用N－S图表示：;4、用伪码表示算法 ;BEGIN(算法开始) 1=i While i=50 { input ni and gi if gi≥80 print ni and gi i+1=i } END（算法结束） ;5、用计算机语言表示算法 ;例： 有50个学生，要求将他们之中成绩在80分以上者打印出来。 用n表示学生学号，n1表示第一个学生学号，ni表示第i个学生 学号。用g表示学生成绩，gi表示第i个学生成绩。 ;例2：对一个大于或等于3的正整数，判断它是不是一个素数。;算法表示如下： 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 “是素数”，算法结束。 ;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)? 循环结构，它又称为重复结构，即反复执行某一部分 的操作。又两类循环结构： ;(b)直到型（Until型）循环结构 ;2、结构化程序 ;;解答：（ⅰ）用自然语言表示（???）用传统的流程图表示（ⅲ）N—S流程图（ⅳ）用伪代码表示等。;2、设计算法：A、B两人各有一桶油，现两人要将各自桶 内的油互换。;3、设计算法写出求n!的算法