算法及算法的描述方法.ppt
西安电子科技大学计算机学院西安电子科技大学计算机学院 张淑平张淑平2004200420042004秋季计算机学院本科课程秋季计算机学院本科课程秋季计算机学院本科课程秋季计算机学院本科课程C程序设计程序设计(Programming in C)School of Computer Science&Engineering,Xidian University,China 上次课程的内容提要上次课程的内容提要l lC C语言是一种得到广泛应用的高级程序设计语言语言是一种得到广泛应用的高级程序设计语言语言是一种得到广泛应用的高级程序设计语言语言是一种得到广泛应用的高级程序设计语言l l用高级程序语言编写的程序需要进行翻译才能被计算用高级程序语言编写的程序需要进行翻译才能被计算用高级程序语言编写的程序需要进行翻译才能被计算用高级程序语言编写的程序需要进行翻译才能被计算机执行，对于机执行，对于机执行，对于机执行，对于C C语言程序，该翻译过程由语言程序，该翻译过程由语言程序，该翻译过程由语言程序，该翻译过程由C C编译器编译器编译器编译器完成完成完成完成l l明确本课程的学习目标：初步掌握程序设计基本知识明确本课程的学习目标：初步掌握程序设计基本知识明确本课程的学习目标：初步掌握程序设计基本知识明确本课程的学习目标：初步掌握程序设计基本知识和良好的程序设计风格和良好的程序设计风格和良好的程序设计风格和良好的程序设计风格l l用计算机解决问题的首要步骤是分析问题并设计算法用计算机解决问题的首要步骤是分析问题并设计算法用计算机解决问题的首要步骤是分析问题并设计算法用计算机解决问题的首要步骤是分析问题并设计算法l l算法描述了给定问题的解题步骤算法描述了给定问题的解题步骤算法描述了给定问题的解题步骤算法描述了给定问题的解题步骤l l流程图是一种算法描述方法流程图是一种算法描述方法流程图是一种算法描述方法流程图是一种算法描述方法西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 2 素性判别素性判别l l素性判别就是给定一个正整数，判定其是否为素数素性判别就是给定一个正整数，判定其是否为素数素性判别就是给定一个正整数，判定其是否为素数素性判别就是给定一个正整数，判定其是否为素数素数的定义：一个大于素数的定义：一个大于1的整数，如果它的正因数只有的整数，如果它的正因数只有1和它和它本身，就叫做本身，就叫做素数素数，否则就叫，否则就叫合数合数。l l如何判定给定正整数如何判定给定正整数如何判定给定正整数如何判定给定正整数n n是否为素数呢？根据定义。是否为素数呢？根据定义。是否为素数呢？根据定义。是否为素数呢？根据定义。l l从从从从2 2开始找开始找开始找开始找n n的因子，若能找到一个介于的因子，若能找到一个介于的因子，若能找到一个介于的因子，若能找到一个介于2 2和和和和n-1n-1之间的之间的之间的之间的n n的因子，说明的因子，说明的因子，说明的因子，说明n n不是素数；否则，不是素数；否则，不是素数；否则，不是素数；否则，n n是素数。是素数。是素数。是素数。西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 3 素性判别素性判别YNK 2K不能整除不能整除n?K K+1输出输出n是素数是素数 输入输入n的值的值开始开始结束结束YNK等于等于n?输出输出n不是素数不是素数西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 4 求最大公约数求最大公约数l l设有两个正整数设有两个正整数设有两个正整数设有两个正整数mm和和和和n n，如何求其最大公约数？，如何求其最大公约数？，如何求其最大公约数？，如何求其最大公约数？l l有多种方法，例如有多种方法，例如有多种方法，例如有多种方法，例如l l求解速度最快的方法是辗转相除法。求解速度最快的方法是辗转相除法。求解速度最快的方法是辗转相除法。求解速度最快的方法是辗转相除法。辗转相除法辗转相除法(欧几里得算法欧几里得算法)：给定两个正整数给定两个正整数m m和和n n，求它们的最大公约数，求它们的最大公约数(公因子公因子)。步骤步骤1:1:【求余数】以【求余数】以n n除除m m并令并令r r为所得余数为所得余数(0r(0rn)n)步骤步骤2:2:【余数为【余数为0?0?】若】若r=0r=0，算法结束；，算法结束；n n即为答案即为答案步骤步骤3:3:【互换】置【互换】置mnmn，nr nr，转向步骤，转向步骤1 1。西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 5 求最大公约数流程图求最大公约数流程图YNrm被被n除的余数除的余数r不等于不等于0?n r输出输出n的值的值输入正整数输入正整数m和和n开始开始结束结束m n结构不好！结构不好！西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 6 这次课的主要内容这次课的主要内容l l结构化方法的基本结构：顺序结构、选择结构、循环结构化方法的基本结构：顺序结构、选择结构、循环结构化方法的基本结构：顺序结构、选择结构、循环结构化方法的基本结构：顺序结构、选择结构、循环结构结构结构结构l l其他算法描述方法其他算法描述方法其他算法描述方法其他算法描述方法N-SN-S盒图方法盒图方法盒图方法盒图方法伪代码方法伪代码方法伪代码方法伪代码方法西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 7 三种基本结构三种基本结构西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 8 三种基本结构三种基本结构l l19661966年，年，年，年，BohraBohra和和和和JacopiniJacopini提出了以下三种基本结构，提出了以下三种基本结构，提出了以下三种基本结构，提出了以下三种基本结构，作为构造算法的基本单元作为构造算法的基本单元作为构造算法的基本单元作为构造算法的基本单元顺序结构顺序结构顺序结构顺序结构选择结构选择结构选择结构选择结构循环结构循环结构循环结构循环结构l l顺序结构和选择结构的流程图如下图所示顺序结构和选择结构的流程图如下图所示顺序结构和选择结构的流程图如下图所示顺序结构和选择结构的流程图如下图所示AB顺序结构顺序结构abpAB成立成立不成立不成立ab选择结构选择结构1pA成立成立不成立不成立ab选择结构选择结构2西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 9 三种基本结构三种基本结构l l循环结构循环结构循环结构循环结构当型循环结构当型循环结构当型循环结构当型循环结构(while(while型循环）如图循环结构型循环）如图循环结构型循环）如图循环结构型循环）如图循环结构1 1所示所示所示所示直到型循环结构直到型循环结构直到型循环结构直到型循环结构(Until(Until型循环型循环型循环型循环)如图循环结构如图循环结构如图循环结构如图循环结构2 2所示所示所示所示pA成立成立不成立不成立ab循环结构循环结构2pA成立成立不成立不成立ab循环结构循环结构1西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 10 基本结构小结基本结构小结l l只有一个入口只有一个入口只有一个入口只有一个入口l l只有一个出口只有一个出口只有一个出口只有一个出口l l结构中的每一部分都存在一条从入口到出口的路径结构中的每一部分都存在一条从入口到出口的路径结构中的每一部分都存在一条从入口到出口的路径结构中的每一部分都存在一条从入口到出口的路径l l结构内不存在结构内不存在结构内不存在结构内不存在“死循环死循环死循环死循环”AB死循环死循环apAB成立成立不成立不成立ab西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 11 计算计算1+2+100的流程图的流程图 YNI 1S 0Ib then max a else max b 例如：例如：if(k mod 4=0)(k mod 4=0)andand(k mod 100 0)(k mod 100 0)oror(k mod 100=0)(k mod 100=0)and and(k mod 400=0)(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 29 伪代码算法中基本符号的使用伪代码算法中基本符号的使用l l循环结构循环结构循环结构循环结构当当当当p p p p成立成立成立成立时，则时，则时，则时，则A:while p do AA:while p do AA:while p do AA:while p do AYNIb do a a-b while I=100 do S S+I;I I+1;西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 30 伪代码描述计算伪代码描述计算1+2+1001+2+100的算法的算法算法算法1：计算：计算1+2+100BEGIN S 0;I 1;while (I 100)do S S+I;I I+1;print S；ENDYNI 1S 0I=100?S S+I输出输出S的值的值开始开始结束结束I I+1西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 31 伪代码算法：求最大公约数伪代码算法：求最大公约数YNr不等于不等于0?输出输出n的值的值输入正整数输入正整数m和和n开始开始结束结束m n;n rrm被被n除的余数除的余数rm被被n除的余数除的余数算法算法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 32 伪代码算法：求最大公约数伪代码算法：求最大公约数算法算法3：辗转相除法求最大公约数：辗转相除法求最大公约数BEGIN input m,n;/*输入正整数输入正整数m和和n*/do rm mod n;m n;n r;while r0;print m；/*输出最大公约数输出最大公约数*/ENDYNr不等于不等于0?输出输出m的值的值输入正整数输入正整数m和和n开始开始结束结束rm被被n除的余数除的余数m n;n r西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 33 伪代码算法：素性判别伪代码算法：素性判别Y N K 2K不能整除不能整除n?K K+1输出输出n是素数是素数 输入输入n的值的值开始开始结束结束YNK等于等于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 34 本次课程的内容提要本次课程的内容提要l l结构化方法的三种基本结构结构化方法的三种基本结构结构化方法的三种基本结构结构化方法的三种基本结构顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构l l如果一个算法不能分解为若干个基本结构，则不是一如果一个算法不能分解为若干个基本结构，则不是一如果一个算法不能分解为若干个基本结构，则不是一如果一个算法不能分解为若干个基本结构，则不是一个结构化的算法个结构化的算法个结构化的算法个结构化的算法l l在计算机软件技术的发展过程中，结构化是一种重要在计算机软件技术的发展过程中，结构化是一种重要在计算机软件技术的发展过程中，结构化是一种重要在计算机软件技术的发展过程中，结构化是一种重要的技术的技术的技术的技术l l流程图描述算法时直观形象，易于理解，但是不加限流程图描述算法时直观形象，易于理解，但是不加限流程图描述算法时直观形象，易于理解，但是不加限流程图描述算法时直观形象，易于理解，但是不加限制地使用流线随意转向，可能使算法的逻辑难以理解制地使用流线随意转向，可能使算法的逻辑难以理解制地使用流线随意转向，可能使算法的逻辑难以理解制地使用流线随意转向，可能使算法的逻辑难以理解l lN-SN-S盒图克服了流程图表示方法的缺点，能更好地体现盒图克服了流程图表示方法的缺点，能更好地体现盒图克服了流程图表示方法的缺点，能更好地体现盒图克服了流程图表示方法的缺点，能更好地体现结构化思想结构化思想结构化思想结构化思想l l伪代码表示算法时比较灵活，也易于修改，通常采用伪代码表示算法时比较灵活，也易于修改，通常采用伪代码表示算法时比较灵活，也易于修改，通常采用伪代码表示算法时比较灵活，也易于修改，通常采用比较接近于计算机程序的符号比较接近于计算机程序的符号比较接近于计算机程序的符号比较接近于计算机程序的符号l l流程图、流程图、流程图、流程图、N-SN-S盒图、伪代码都是常用的算法描述方法，盒图、伪代码都是常用的算法描述方法，盒图、伪代码都是常用的算法描述方法，盒图、伪代码都是常用的算法描述方法，必须掌握其中的一种或多种描述方法必须掌握其中的一种或多种描述方法必须掌握其中的一种或多种描述方法必须掌握其中的一种或多种描述方法西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 35 下次课的主要内容下次课的主要内容l l自顶向下、逐步求精方法自顶向下、逐步求精方法自顶向下、逐步求精方法自顶向下、逐步求精方法筛选法求素数筛选法求素数筛选法求素数筛选法求素数l l简单排序算法简单排序算法简单排序算法简单排序算法l l分治法分治法分治法分治法西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 36 作业作业1.1.有两个杯子有两个杯子A A和和B B，A A中盛水，中盛水，B B中盛果汁，考虑一下中盛果汁，考虑一下如何能互换如何能互换A A和和B B中的内容。中的内容。2.2.输入输入1010个整数，设计算法，找出其中最大的数并打个整数，设计算法，找出其中最大的数并打印输出。印输出。3.3.设计算法，找出设计算法，找出22552255之间的所有素数。之间的所有素数。西安电子科技大学计算机学院 -School of Computer Science&Engineering,Xidian University,China 37
