第4章 算法基础

,第4章算法基础,目录,4.1算法的基本概念4.2算法的三种结构4.3算法的表示4.4算法设计基本方法4.5算法的评价,4.1算法的基本概念,4.1.1算法的起源,周髀算经九章算术,最早,四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法（简称埃氏筛），线性方程组求解,第一个算法,欧几里得算法（辗转相除法）,求两个正整数A和B的最大公约数：Step1:比较A和B两个数，将A设置为较大的数，B为较小的数；Step2:A除以B，得到余数R；Step3:如果R等于0，则最大公约数就是B，否则将B赋值给A，R赋值给B，重复Step2、Step3。,4.1算法的基本概念,4.1.2算法的定义和特性,为解决问题采用的方法和步骤。算法是一组明确步骤的有序集合，它产生结果并在有限时间内终止。,算法,特性,有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步骤都必须是确切定义的。输入：一个算法有0个、1个或多个输入。输出：一个算法必须有1个或多个输出值。可行性：算法的每一步操作都应该是可执行的。,4.2算法的三种结构,1.顺序结构,按照顺序从上向下依次执行A和B，A和B代表算法的步骤。,2.选择结构,根据给定的条件判断选择哪一条分支，执行相应的步骤。,3.循环结构,在给定条件成立时，反复执行某些步骤，直到条件不成立为止。,4.3算法的表示,4.3.1自然语言,自然语言（NaturalLanguage）,人们日常使用的语言。,【案例4.1】求任意3个正整数a、b、c中的最大者。,用自然语言可将算法表示如下：Step1：输入3个正整数a，b，c。Step2：若a大于b，则将a放到max中，否则将b放到max中。Step3：若c大于max，则将c放到max中。Step4：输出max。,4.3算法的表示,4.3.2流程图,常用传统流程图符号,求任意3个正整数a、b、c中的最大者的流程图,4.3算法的表示,4.2.3伪代码,伪代码（Pseudo-code）又称程序设计语言PDL，是用介于自然语言和计算机语言之间的文字和符号来描述算法。,reada,b,cifabamaxelsebmaxifcmaxcmaxprintmax,4.3算法的表示,4.2.4程序设计语言,用程序设计语言（ProgrammingLanguage）表示算法就是用计算机高级语言编写程序，程序是可以在计算机上经过编译、连接、运行出结果的算法表示。,intmax(inta,intb,intc)intmax;if(ab)max=a;elsemax=b;if(cmax)max=c;returnmax;,intmain(void)inta,b,c,Imax;scanf(%d%d%d,4.3算法设计基本方法,4.3.1求和,【案例4.2】计算1100的和。,思考1：如何计算mn之间的偶数或奇数之和。,思考2：如何计算下式：,4.3算法设计基本方法,4.3.2累乘,【案例4.3】计算10！。,思考1：如何计算的流程图。,思考2：如何计算下式：,4.3算法设计基本方法,4.3.3穷举,【案例4.4】百钱买百鸡。我国古代的张丘建算经中有一个著名的百鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？,假设鸡翁、鸡母、鸡雏分别为a,b,c只，由题意可得如下两个方程：a+b+c=100（1）5a+3b+c/3=100（2）,采用穷举法，依次对a,b,c取值范围内的各数一一试探，找出满足方程（1）和（2）的组合。,流程图参见教材4.9。,4.3算法设计基本方法,4.3.4迭代,【案例4.5】猴子吃桃问题。一只猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求猴子第一天共摘了多少个桃子？,迭代法又称递推法，它是从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。,4.3算法设计基本方法,4.3.4迭代,素数是指只能被1和它自己整除的数。,【案例4.6】给定一个数n，判断n是不是素数。,可以证明，只需依次用2或2之间的各数去除n就可说明n是不是素数。,4.3算法设计基本方法,4.3.5递归,递归是把一个复杂的问题逐层分解为最简单问题，再由最简单问题逐层回代，直到求出问题的解。,【案例4.6】年龄问题。有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人的岁数，他说比第3个人大2岁。问第3个人的岁数，他说比第2个人大2岁。问第2个人，他说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大？,4.3算法设计基本方法,4.3.5递归（续）,4.3算法设计基本方法,【案例4.7】Fibonacci数列。“兔子繁殖问题”：假定一对小兔子一个月就可以长成大兔子（一雄一雌），而一对大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，到年底时将有多少对兔子?（假设兔子没有死亡而且严格按照上述规律长大与繁殖）,兔子繁殖的结果,4.3.5递归（续）,4.3算法设计基本方法,假设第N个月的兔子数目是F(N)，可以得到如下公式：该公式递归地定义了Fibonacci数列。,4.3.5递归（续）,4.3算法设计基本方法,【案例4.8】给2个变量a和b分别输入50和10，然后将大数50存放在b中，小数10存放在a中。,4.3.6两个变量值的交换,4.3算法设计基本方法,1顺序查找,4.3.7查找,【案例4.9】在给定的10个数23，45，62，12，33，87，90，55，13，79组成的列表中查找数12。,4.3算法设计基本方法,2二分查找,4.3.7查找,查找是从列表的中间位置开始，如果该位置上的数据和目标数据（待查找的数据）相等，则查找成功；若目标数据大于中间位置的数据，则在查找表的后半部分继续进行二分查找，否则在前半部分进行二分查找。即先确定目标数据所在区域，然后逐步缩小区域，直到查找成功或失败为止。,【案例4.10】在给定的10个数8，12，35，46，55，67，78，82，90，96的列表中查找数35。,4.3算法设计基本方法,4.3.7查找,【案例4.10】在给定的10个数8，12，35，46，55，67，78，82，90，96的列表中查找数35。,4.3算法设计基本方法,4.3.8排序,1冒泡排序,将待排序的数据依次进行相邻两个数据的比较，如不符合顺序要求（由大到小或由小到大）就立即交换。这样值大（或小）的就会像冒气泡一样逐步升起。按此方法对数据经过一轮比较移位后称为一趟冒泡，第1趟冒泡的效果是将数据值最大（或最小）的元素交换到了最后的位置，即该数据排序的最终位置。n个数据最多需要进行n1趟冒泡。,4.3算法设计基本方法,4.3.8排序,2选择排序,从待排序的n个数据的列表（R1,R2,R3,.,Rn）中选出最小的数（按升序）或最大的数（按降序），将它与R1交换；然后再从余下的n-1个数中选出次小（或次小）的元素与R2进行交换；第i趟排序时（R1,R2,.,Ri-1）已排好序，在当前无序的（Ri,.,Rn）中再选出最小（或最大）的元素，将它与Ri元素交换，使（R1,R2,.,Ri）成为有序。依此类推，经过n-1趟排序后，全部数据就递增（或递减）有序了。,【案例4.12】用选择排序法将N（N=7）个无序数据（9,5,7,2,4,8,3）其按升序排列。,4.3算法设计基本方法,4.3.8排序,3插入排序,把n个待排序的数据分为两部分：R1，.，Ri1为已排好序的有序表，Ri，Ri+1，.，Rn为未排序的无序表（初始时，令i=2）。然后，把未排序部分的第1个数据Ri依次与R1，.，Ri-1比较，并插入到有序表的适当位置上，使得R1，.，Ri变为一个新的有序表，直到未排序表中的数据元素全部插入到有序表中。,【案例4.13】用插入排序法将N（N=5）个无序数据（30,16,25,17,12）其按升序排列。,初始数据3016251712第1步1630251712第2步1625301712第3步1617253012第4步1216172530,4.4算法的评价,1时间复杂度,算法的时间复杂度（TimeComplexity）是指算法执行所需要的计算工作量。,按数量级递增排列，常见的时间复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)等，线性对数阶O(nlog2n)，平方阶O(n2)，立方阶O(n3)，.，k次方阶O(nk)，指数阶O(2n)。,2空间复杂度,一个算法的空间复杂度（SpaceComplexity）是指算法运行所需的内存大小，包括输入数据所占空间、程序本身所占空间以及算法执行过程中所需要的辅助空间，其中辅助空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。,本章小结,算法是为解决问题采用的方法和步骤，它具有5个重要特性：有穷性、确定性、输入、输出、可行性。,算法有三种结构：顺序、选择（分支）、循环。顺序结构按照顺序从上向下依次执行算法步骤；选择结构根据给定的条件判断选择执行相应的步骤；循环结构在给定条件成立时，反复执行某些算法步骤。,算法的表示有多种方法，常用的有：自然语言、流程图、伪代码、程序设计语言等。,求和是对数相加时用到的一种基本方法。累乘对一系列数的求乘积的方法。穷举法是依题目的部分条件确定