大学计算机基础-第4章 算法基础.pptx
1第4章 算法基础24.1 算法的基本概念4.2 算法的三种结构4.3 算法的表示4.4 算法设计基本方法4.5 算法的评价34.1.1 算法的起源周髀算经九章算术最早四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法（简称埃氏筛），线性方程组求解第一个算法欧几里得算法（辗转相除法）求两个正整数A和B的最大公约数：Step 1: 比较A和B两个数，将A设置为较大的数，B为较小的数；Step 2: A除以B，得到余数R；Step 3: 如果R等于0，则最大公约数就是B，否则将B赋值给A，R赋值给B，重复Step2、Step3。44.1.2 算法的定义和特性为解决问题采用的方法和步骤。算法是一组明确步骤的有序集合，它产生结果并在有限时间内终止。算法特性 有穷性：一个算法必须在执行有穷步之后结束。 确定性：算法的每一步骤都必须是确切定义的。 输入：一个算法有0个、1个或多个输入。 输出：一个算法必须有1个或多个输出值。 可行性：算法的每一步操作都应该是可执行的。 51.顺序结构 按照顺序从上向下依次执行A和B，A和B代表算法的步骤。2.选择结构根据给定的条件判断选择哪一条分支，执行相应的步骤。3.循环结构在给定条件成立时，反复执行某些步骤，直到条件不成立为止。AAA64.3.1 自然语言自然语言（Natural Language）人们日常使用的语言。【案例4.1】求任意3个正整数a、b、c中的最大者。用自然语言可将算法表示如下：Step 1：输入3个正整数 a，b，c。Step2：若a大于b，则将a放到max中，否则将b放到max中。Step 3：若c大于max，则将c放到max中。Step 4：输出max。74.3.2 流程图 常用传统流程图符号求任意3个正整数a、b、c中的最大者的流程图84.2.3 伪代码伪代码（Pseudo-code）又称程序设计语言PDL，是用介于自然语言和计算机语言之间的文字和符号来描述算法。read a, b, cif ab amaxelse bmaxif cmax cmaxprint max94.2.4 程序设计语言用程序设计语言（Programming Language）表示算法就是用计算机高级语言编写程序，程序是可以在计算机上经过编译、连接、运行出结果的算法表示。int max( int a, int b, int c) int max; if(a b)max = a;elsemax = b;if(c max)max = c;return max; int main(void) int a, b, c,Imax;scanf(%d%d%d,&a,&b,&c);Imax=max(a, b, c);printf(max=%d, Imax);104.3.1 求和【案例4.2】计算1100的和。YN开始0=sum1=kk100sum + k =sumk+1 = k结束思考1：如何计算mn之间的偶数或奇数之和。ns.3211.32112111思考2：如何计算下式：114.3.2 累乘【案例4.3】计算10！ 。思考1：如何计算 的流程图。思考2：如何计算下式：nx!9!7!5!3)sin(9753xxxxxx124.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。134.3.4 迭代【案例4.5】猴子吃桃问题。一只猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求猴子第一天共摘了多少个桃子？迭代法又称递推法，它是从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。144.3.4 迭代素数是指只能被1和它自己整除的数。【案例【案例4.6】给定一个数】给定一个数n，判，判断断n是不是素数。是不是素数。可以证明，只需依次用2 或2 之间的各数去除n就可说明n是不是素数。154.3.5 递归递归是把一个复杂的问题逐层分解为最简单问题，再由最简单问题逐层回代，直到求出问题的解。【案例案例4.6】年龄问题。有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人的岁数，他说比第3个人大2岁。问第3个人的岁数，他说比第2个人大2岁。问第2个人，他说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大？164.3.5 递归（续）17【案例案例4.7】Fibonacci数列。“兔子繁殖问题”：假定一对小兔子一个月就可以长成大兔子（一雄一雌），而一对大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，到年底时将有多少对兔子? （假设兔子没有死亡而且严格按照上述规律长大与繁殖）月兔1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合计1123581321345589144兔子繁殖的结果兔子繁殖的结果4.3.5 递归（续）18假设第N个月的兔子数目是F(N)，可以得到如下公式：该公式递归地定义了Fibonacci数列。2N)2N(F)1N(F2N1)N(F开始F1=1,f2=1i=3i=12f=f1+f2, f1=f2, f2=fi=i+1输出f结束20【案例案例4.8】给2个变量a和b分别输入50和10，然后将大数50存放在b中，小数10存放在a中。4.3.6 两个变量值的交换211顺序查找顺序查找4.3.7 查找【案例【案例4.9】在给定的10个数23，45，62，12，33，87，90，55，13，79组成的列表中查找数12。222二分查找二分查找4.3.7 查找查找是从列表的中间位置开始，如果该位置上的数据和目标数据（待查找的数据）相等，则查找成功；若目标数据大于中间位置的数据，则在查找表的后半部分继续进行二分查找，否则在前半部分进行二分查找。即先确定目标数据所在区域，然后逐步缩小区域，直到查找成功或失败为止。【案例【案例4.10】在给定的10个数8，12，35，46，55，67，78，82，90，96的列表中查找数35。234.3.7 查找【案例【案例4.10】在给定的10个数8，12，35，46，55，67，78，82，90，96的列表中查找数35。244.3.8 排序1冒泡排序冒泡排序将待排序的数据依次进行相邻两个数据的比较，如不符合顺序要求（由大到小或由小到大）就立即交换。这样值大（或小）的就会像冒气泡一样逐步升起。按此方法对数据经过一轮比较移位后称为一趟冒泡，第1趟冒泡的效果是将数据值最大（或最小）的元素交换到了最后的位置，即该数据排序的最终位置。n个数据最多需要进行n1趟冒泡。254.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）其按升序排列。264.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）其按升序排列。初始数据 30 16 25 17 12第 1 步 16 30 25 17 12第 2 步 16 25 30 17 12第 3 步 16 17 25 30 12第 4 步 12 16 17 25 30 27算法算法是为解决问题采用的方法和步骤，它具有5个重要特性：有穷性、确定性、输入、输出、可行性。算法有三种结构算法有三种结构：顺序、选择（分支）、循环。顺序结构按照顺序从上向下依次执行算法步骤；选择结构根据给定的条件判断选择执行相应的步骤；循环结构在给定条件成立时，反复执行某些算法步骤。算法的表示算法的表示有多种方法，常用的有：自然语言、流程图、伪代码、程序设计语言等。求和求和是对数相加时用到的一种基本方法。累乘累乘对一系列数的求乘积的方法。穷举法穷举法是依题目的部分条件确定答案的大致范围，在此范围内对所有可能的情况逐一验证，直到全部情况验证完。28迭代法迭代法是从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。递归递归是把一个复杂的问题逐层分解为最简单问题，再由最简单问题逐层回代，直到求出问题的解。顺序查找顺序查找和二分查找二分查找是常用的查找算法，前者适用无序数据，后者要求数据是有序的。冒泡排序、选择排序和插入排序冒泡排序、选择排序和插入排序是常用的排序算法。算法的复杂度是指运行算法所需的时间和空间资源的量。
