算法及算法的描述方法.ppt

School of Computer Science & Engineering, Xidian University, China,C程序设计 (Programming in C ),西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 2,上次课程的内容提要,C语言是一种得到广泛应用的高级程序设计语言 用高级程序语言编写的程序需要进行翻译才能被计算机执行，对于C语言程序，该翻译过程由C编译器完成 明确本课程的学习目标：初步掌握程序设计基本知识和良好的程序设计风格 用计算机解决问题的首要步骤是分析问题并设计算法 算法描述了给定问题的解题步骤 流程图是一种算法描述方法,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 3,素性判别,素性判别就是给定一个正整数，判定其是否为素数,素数的定义：一个大于1的整数，如果它的正因数只有1和它本身，就叫做素数，否则就叫合数。,如何判定给定正整数n是否为素数呢？根据定义。,从2开始找n的因子，若能找到一个介于2和n-1之间的n的因子，说明n不是素数；否则，n是素数。,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 4,素性判别,Y,N,K 2,K不能整除n?,K K+1,输出n是素数,输入n的值,开始,结束,Y,N,K等于n?,输出n不是素数,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 5,求最大公约数,设有两个正整数m和n，如何求其最大公约数？,有多种方法，例如 求解速度最快的方法是辗转相除法。,辗转相除法(欧几里得算法)： 给定两个正整数m和n，求它们的最大公约数(公因子)。 步骤1:【求余数】以n除m并令r为所得余数(0rn) 步骤2:【余数为0?】若r=0，算法结束；n即为答案 步骤3:【互换】置mn， nr，转向步骤1。,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 6,求最大公约数流程图,Y,N,rm被n除的余数,r不等于0?,n r,输出n的值,输入正整数m和n,开始,结束,m n,结构不好！,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 7,这次课的主要内容,结构化方法的基本结构：顺序结构、选择结构、循环结构 其他算法描述方法 N-S盒图方法 伪代码方法,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 8,三种基本结构,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 9,三种基本结构,1966年，Bohra和Jacopini提出了以下三种基本结构，作为构造算法的基本单元 顺序结构 选择结构 循环结构 顺序结构和选择结构的流程图如下图所示,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 10,三种基本结构,循环结构 当型循环结构(while型循环）如图循环结构1所示 直到型循环结构(Until型循环) 如图循环结构2所示,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 11,基本结构小结,只有一个入口 只有一个出口 结构中的每一部分都存在一条从入口到出口的路径 结构内不存在“死循环”,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 12,计算1+2+100的流程图,A,B,C,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 13,判断闰年的流程图,k能被4整除？,输入一个年份值k,开始,结束,输出k不是闰年,输出k是闰年,Y,N,k能被100整除？,Y,k能被400整除？,Y,N,N,输出k是闰年,输出k不是闰年,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 14,判断闰年的流程图,k能被4整除？,输入一个年份值k,开始,结束,输出k不是闰年,Y,N,k能被100整除？,Y,k能被400整除？,Y,N,N,输出k是闰年,输出k是闰年,输出k不是闰年,A,B,C,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 15,判断闰年的流程图,k能被4整除？,输入一个年份值k,开始,结束,输出k不是闰年,输出k是闰年,Y,N,k能被100整除？,Y,k能被400整除？,Y,N,N,结构不好！,A,B,无法划分基本单元！,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 16,求最大公约数流程图,结构不好！,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 17,求最大公约数流程图,A,B,C,D,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 18,求最大公约数流程图,Y,N,r不等于0?,输出m的值,输入正整数m和n,开始,结束,rm被n除的余数 m n; n r,A,B,C,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 19,流程图的优缺点,优点 直观形象，比较清楚地表现了各个框图的逻辑关系 缺点 占用篇幅较多 对流程线的使用没有限制，允许随意转向可能造成流程混乱，理解困难,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 20,其他算法描述方法,用N-S盒图表示算法 用伪代码描述算法 用PAD图描述算法(略) 用计算机语言描述算法(程序) .,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 21,用N-S盒图描述算法,N-S盒图的基本符号,流程图符号,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 22,用N-S盒图描述算法,N-S盒图的基本符号,流程图符号,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 23,求最大公约数流程图,输入正整数m和n,rm被n除的余数,输出n的值,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 24,N-S盒图表示法小结,与流程图相比，N-S盒图 保留了流程图方式直观、形象和易于理解的优点 去掉了流程线，形式上更紧凑 避免了流程的随意跳转，确保了结构化技术,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 25,用伪代码表示算法,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 26,规定一些基本符号,运算符号 简单算术运算符号： +、-、/、 mod(整除取余) 关系运算符号: 、 逻辑运算符号: and 、or、not 括号: (、) 用于表示某种对象名字的符号 以英文字母开头的字母、数字符号串 例如：sum, price, i, m, k, n, a1, a2 其他(处理、语句) 赋值: ，例如 i 1 如果p成立则A否则B: if p then A else B 当p成立时，则A: while p do A do A while p 输入和输出(打印) ：input、print 基本块起、止符号: 、 算法开始和结束：BEGIN、END,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 27,伪代码算法中基本符号的使用,运算符号（a 5；b 3） 简单算术运算符号： +、-、/、 mod(整除取余) 例如：a+b、a-b、ab、a/b、a mod b 关系运算符号: 、 成立：true(Yes、Y) 不成立：false(No、N) 括号: (、),西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 28,伪代码算法中基本符号的使用,逻辑运算 逻辑运算符号: and 、or、not 并且：and 或者：or 非(不是)：not,因此，给定一个年号k，判断是否为闰年的条件是： (k mod 4 = 0) and (k mod 100 0) or (k mod 100 = 0) and (k mod 400 = 0),例如，判断闰年的条件(给定一个年号k) 能被4整除，但是不能被100整除的年份是闰年 (k mod 4 = 0) and (k mod 100 0) 能同时被100和400整除的年份是闰年 (k mod 100 = 0) and (k mod 400 = 0),西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 29,伪代码算法中基本符号的使用,选择结构 如果p成立则A否则B: if p then A else B,例如,if ab then max a else max b,例如： if (k mod 4 = 0) and (k mod 100 0) or (k mod 100 = 0) and (k mod 400 = 0) then print “k is a leap year.” else print “k is not a leap year.”,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 30,伪代码算法中基本符号的使用,循环结构 当p成立时，则A: while p do A,例如,while ab do a a - b,while I=100 do S S + I; I I + 1; ,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 31,伪代码描述计算1+2+100的算法,算法1：计算1+2+100 BEGIN S 0; I 1; while (I 100) do S S + I; I I + 1; print S； END,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 32,伪代码算法：求最大公约数,算法2：辗转相除法求最大公约数 BEGIN input m,n; /*输入正整数m和n*/ rm mod n; /*求m被n除的余数*/ while (r0) do m n; n r; rm mod n; print n； /*输出最大公约数*/ END,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 33,伪代码算法：求最大公约数,算法3：辗转相除法求最大公约数 BEGIN input m,n; /*输入正整数m和n*/ do rm mod n; m n; n r; while r0; print m； /*输出最大公约数*/ END,Y,N,r不等于0?,输出m的值,输入正整数m和n,开始,结束,rm被n除的余数 m n; n r,西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 34,伪代码算法：素性判别,Y,N,K 2,K不能整除n?,K K+1,输出n是素数,输入n的值,开始,结束,Y,N,K等于n?,算法2：素性判别 BEGIN input n; /*输入正整数n*/ k2; while (n mod k 0) do k k+1; if (k=n) then prin