算法及算法的描述方法

C程序设计(ProgramminginC).上次课程的内容提要C语言是一种得到广泛应用的高级程序设计语言用高级程序语言编写的程序需要进行翻译才能被计算机执行，对于C语言程序，该翻译过程由C编译器完成明确本课程的学习目标：初步掌握程序设计基本知识和良好的程序设计风格用计算机解决问题的首要步骤是分析问题并设计算法算法描述了给定问题的解题步骤流程图是一种算法描述方法.素性判别素性判别就是给定一个正整数，判定其是否为素数素数的定义：一个大于1的整数，如果它的正因数只有1和它本身，就叫做素数，否则就叫合数。如何判定给定正整数n是否为素数呢？根据定义。从2开始找n的因子，若能找到一个介于2和n-1之间的n的因子，说明n不是素数；否则，n是素数。.素性判别YNK←2K不能整除n?K←K+1输出n是素数输入n的值开始结束YNK等于n?输出n不是素数.求最大公约数设有两个正整数m和n，如何求其最大公约数？有多种方法，例如求解速度最快的方法是辗转相除法。辗转相除法(欧几里得算法)：给定两个正整数m和n，求它们的最大公约数(公因子)。步骤1:【求余数】以n除m并令r为所得余数(0≤r＜n)步骤2:【余数为0?】若r=0，算法结束；n即为答案步骤3:【互换】置m←n，n←r，转向步骤1。.求最大公约数流程图YNr←m被n除的余数r不等于0?n←r输出n的值输入正整数m和n开始结束m←n结构不好！.这次课的主要内容结构化方法的基本结构：顺序结构、选择结构、循环结构其他算法描述方法N-S盒图方法伪代码方法.三种基本结构.三种基本结构1966年，Bohra和Jacopini提出了以下三种基本结构，作为构造算法的基本单元顺序结构选择结构循环结构顺序结构和选择结构的流程图如下图所示AB顺序结构abpAB成立不成立ab选择结构1pA成立不成立ab选择结构2.三种基本结构循环结构当型循环结构(while型循环）如图循环结构1所示直到型循环结构(Until型循环)如图循环结构2所示pA成立不成立ab循环结构2pA成立不成立ab循环结构1.基本结构小结只有一个入口只有一个出口结构中的每一部分都存在一条从入口到出口的路径结构内不存在“死循环”AB死循环apAB成立不成立ab.计算1+2+…+100的流程图

YNI←1S←0I<=100?S←S+I输出S的值开始结束I←I+1ABCABC.判断闰年的流程图

k能被4整除？输入一个年份值k开始结束输出k不是闰年输出k是闰年YNk能被100整除？Yk能被400整除？YNN输出k是闰年输出k不是闰年.判断闰年的流程图

k能被4整除？输入一个年份值k开始结束输出k不是闰年YNk能被100整除？Yk能被400整除？YNN输出k是闰年输出k是闰年输出k不是闰年ABCApBC成立不成立ab.判断闰年的流程图

k能被4整除？输入一个年份值k开始结束输出k不是闰年输出k是闰年YNk能被100整除？Yk能被400整除？YNN结构不好！ABABab无法划分基本单元！.求最大公约数流程图YNr←m被n除的余数r不等于0?n←r输出n的值输入正整数m和n开始结束m←n结构不好！pA成立不成立ab循环结构2pA成立不成立ab循环结构1.求最大公约数流程图成立不成立abYNr不等于0?输出n的值输入正整数m和n开始结束m←n;n←rr←m被n除的余数r←m被n除的余数ABCDABCD.求最大公约数流程图YNr不等于0?输出m的值输入正整数m和n开始结束r←m被n除的余数m←n;n←rABCABC成立不成立.流程图的优缺点优点直观形象，比较清楚地表现了各个框图的逻辑关系缺点占用篇幅较多对流程线的使用没有限制，允许随意转向可能造成流程混乱，理解困难.其他算法描述方法用N-S盒图表示算法用伪代码描述算法用PAD图描述算法(略)用计算机语言描述算法(程序)....用N-S盒图描述算法N-S盒图的基本符号AB顺序结构选择结构ABp成立不成立AB顺序结构ab流程图符号pAB成立不成立ab选择结构.用N-S盒图描述算法N-S盒图的基本符号流程图符号A当型循环结构当p成立A直到型循环结构直到p成立pA成立不成立ab循环结构1pA成立不成立ab循环结构2.求最大公约数流程图YNr不等于0?输出n的值输入正整数m和n开始结束m←n;n←rr←m被n除的余数r←m被n除的余数输入正整数m和nr←m被n除的余数m←n;n←rr←m被n除的余数当r不等于0输出n的值.N-S盒图表示法小结与流程图相比，N-S盒图保留了流程图方式直观、形象和易于理解的优点去掉了流程线，形式上更紧凑避免了流程的随意跳转，确保了结构化技术.用伪代码表示算法.规定一些基本符号运算符号简单算术运算符号：+、-、×、/、mod(整除取余)关系运算符号:＞、≥、＜、≤、＝、≠逻辑运算符号:and、or、not括号:(、)用于表示某种对象名字的符号以英文字母开头的字母、数字符号串例如：sum,price,i,m,k,n,a1,a2其他(处理、语句)赋值:←，例如i←1如果p成立则A否则B:ifpthenAelseB当p成立时，则A:whilepdoAdoAwhilep输入和输出(打印)：input、print基本块起、止符号:{、}算法开始和结束：BEGIN、END.伪代码算法中基本符号的使用运算符号（a←5；b←3）简单算术运算符号：+、-、×、/、mod(整除取余)例如：a+b、a-b、a×b、a/b、amodb关系运算符号:＞、≥、＜、≤、＝、≠成立：true(Yes、Y)不成立：false(No、N)括号:(、).伪代码算法中基本符号的使用逻辑运算逻辑运算符号:and、or、not并且：and或者：or非(不是)：not因此，给定一个年号k，判断是否为闰年的条件是：((kmod4=0)and(kmod100≠0))or((kmod100=0)and(kmod400=0))例如，判断闰年的条件(给定一个年号k)能被4整除，但是不能被100整除的年份是闰年(kmod4=0)and(kmod100≠0)能同时被100和400整除的年份是闰年(kmod100=0)and(kmod400=0).伪代码算法中基本符号的使用选择结构如果p成立则A否则B:ifpthenAelseBpAB成立不成立ab选择结构例如ifa>bthenmax←aelsemax←b例如：if((kmod4=0)and(kmod100≠0))or((kmod100=0)and(kmod400=0))thenprint“kisaleapyear.”elseprint“kisnotaleapyear.”.伪代码算法中基本符号的使用循环结构当p成立时，则A:whilepdoAYNI<=100?S←S+II←I+1pA成立不成立ab循环结构1例如whilea>bdoa←a-b

whileI<=100do{S←S+I;I←I+1;}.伪代码描述计算1+2+…+100的算法算法1：计算1+2+…+100BEGINS←0;I←1;while(I≤100)do{S←S+I;I←I+1;}printS；ENDYNI←1S←0I<=100?S←S+I输出S的值开始结束I←I+1.伪代码算法：求最大公约数YNr不等于0?输出n的值输入正整数m和n开始结束m←n;n←rr←m被n除的余数r←m被n除的余数算法2：辗转相除法求最大公约数BEGINinputm,n;/*输入正整数m和n*/r←mmodn;/*求m被n除的余数*/while(r≠0)do{m←n;n←r;r←mmodn;}printn；/*输出最大公约数*/END.伪代码算法：求最大公约数算法3：辗转相除法求最大公约数BEGINinputm,n;/*输入正整数m和n*/do{r←mmodn;m←n;n←r;}whiler≠0;printm；/*输出最大公约数*/ENDYNr不等于0?输出m的值输入正整数m和n开始结束r←m被n除的余数m←n;n←r.伪代码算法：素性判别Y

NK←2K不能整除n?K←K+1输出n是素数输入n的值开始结束YNK等于n?算法2：素性判别BEGINinputn;/*输入正整数n*/k←2;while(nmodk≠0)do{k←k+1;}if(k=n)thenprint“n是素数”elseprint“n不是素数”END输出n不是素数.本次课程的内容提要结构化方法的三种基本结构顺序结构、选择结构、循环结构如果一个算法不能分解为若干个基本结构，则不是一个结构化的算法在计算机软件技术的发展过程中，结构化是一种重要的技术流程图描述算法时直观形象，易于理解，但是不加限制地使用流线随意转向，可能使算法的逻辑难以理解N-S盒图克服了流程图表示方法的缺点