算法及算法的描述方法.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 Ado 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+100BEGIN 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 print“n是素数”else print“n不是素数”END,输出n不是素数,西安电子科技大学计算机学院-School of Computer Science&Engineering,Xidian University,China 35,本次课程的内容提要,结构化方法的三种基本结构顺序结构、选择结构、循环结构如果一个算法不能分解为若干个基本结构，则不是一个结构化的算法在计算机软件技术的发展过程中，结构化是一种重要的技术流程图描述算法时直观形象，易于理解，但是不加限制地使用流线随意转向，可能使算法的逻辑难以理解N-S盒图克服了流程图表示方法的缺点，能更好地体现结构化思想伪代码表示算法时比较灵活，也易于修改，通常采用比较接近于计算机程序的符号流程图、N-S盒图、伪代码都是常用的算法描述方法，必须掌握其中的一种或多种描述方法,西安电子科技大学计算机学院-School of Computer Science&Engineering,Xidian University,China 36,下次课的主要内容,自顶向下、逐步求精方法筛选法求素数简单排序算法分治法,西安电子科技大学计算机学院-School of Computer Science&Engineering,Xidian University,China 37,作业,有两个杯子A和B，A中盛水，B中盛果汁，考虑一下如何能互换A和B中的内容。输入10个整数，设计算法，找出其中最大的数并打印输出。设计算法，找出2255之间的所有素数。,
