大学计算机-4-2PPT课件.pptx

1
大学计算机-计算思维的视角© 2014-2020 Powered by Jollyseen
计算机问题求解模型
算法与算法分析
算法设计及其方法
搜索问题与查找算法
排序问题与排序算法
知识要点
算法设计
穷举法
递推法
递归法
回溯法
分治法
贪心法
……
第4章问题求解与算法
算法设计及其方法
1、算法设计:是寻找问题求解的方法并使用自然语言、流程图或伪代码等来描述算法的过程,算法设计完成之后,常需要对算法的正确性及复杂性等进行分析,以保证算法的优良和效率。许多问题通常可以有多个算法。
穷举法
递推法
递归法
回溯法
分治法
贪心法
……
2
大学计算机-计算思维的视角© 2014-2020 Powered by Jollyseen
算法设计及其方法
2、穷举法:也称为枚举法,属于一种暴力算法,就是要列出问题解空间的所有可能情况,并逐个测试从而找出符合问题条件的解(答案)。这个算法很费时,人工求解较困难,常需要利用计算机的强大计算能力求解
当问题的规模n较大时,穷举法将会使问题成为一个NP难度问题
示例:古代数学家张丘建提出了著名的“百钱买百鸡问题”, 鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问翁、母、雏各几何?
3
大学计算机-计算思维的视角© 2014-2020 Powered by Jollyseen
问题分析及数学模型:这是一个典型的不定方程问题。所谓不定方程是一个未知数的个数多于方程的个数,且对解有一定限制的方程。
算法思路:从所有可能的答案范围内逐个计算和验证,从而得到全部正确的解。此类问题通常有明确的条件和与解的计算有关的取值范围,然后就可以通过循环语句和条件判断语句(分支语句)逐个计算和判断是否满足条件,是否是一个解。如上述示例问题就设定了总钱数和总购买标的数及相应条件,可以抽象为一个简单的不定式方程后并基于该数学模型求解
一般性代码示意:设置循环控制变量i、j、k(它们可以直接与问题有关)并假定对应的取值范围分别为(m1~m2)、(n1~n2)、(p1~p2)
4
大学计算机-计算思维的视角© 2014-2020 Powered by Jollyseen
for(i=m1;i<=m2;i++)
for(j=n1;j<=n2;j++)
for(k=p1;k<=p2;k++)
if( i,j,k满足设定条件)
printf(输出当前解);
这是一个多重循环嵌套的代码,循环嵌套层数越多,需要处理的次数越多,所消耗的时间就越多,通常可以深入分析问题涉及的条件,进行算法优化。
算法设计及其方法
算法设计及其方法
3、递推法:简单常用的算法,通过已知条件并利用特定的递推关系得出中间结果,再逐步递推,直到得到最终结果为止。这类算法适合于有明确公式的情况,其关键是得到相邻数据项之间的关系,即递推关系(式),这个递推关系(式)是一种高效的数学模型,同时还有初始(边界)条件。递推算法分为顺序递推(从已知条件出发,逐步推算出问题结果的方法)和逆序递推(从已知的结果出发,用迭代表达式逐步推算出问题的开始条件)两种。
示例:斐波那契数列问题(也称黄金分割数列或“兔子数列”),顺推法,P135
5
大学计算机-计算思维的视角© 2014-2020 Powered by Jollyseen
问题分析:该数列是指这样一个数列,1,1,2,3,5,8,13,21,34,55,89,144,233,377, 610,987,1597,2584,4181,6765,10946,……,该数列从第三项开始,每一项都等于前两项之和。已知f1=f2=1,递推关系为 fn= fn﹣1+ f n﹣2(n∈N*且n>2,N*即所有正整数,n取任何自然数1,2,3,4等)
算法设计及其方法
4、递归法( Recursion):一个概念、函数或数据结构,如果在其定义或说明中又直接地或间接地使用(调用)了其本身,称它们是递归的或者递归定义的
这里主要讨论问题求解过程的递归,递归法是一种逆推法。在计算机语言程序中,一个过程或函数直接或间接调用自己,称为递归调用,是常用的递归问题解决机制
一个递归模型由递归出口和递归体组成:前者负责确定递归到何时(需满足条件)结束,通常到了最小问题并有明确解(值),后者确定递归求解的递推关系(式)
递归思想:把一个直接求解困难的“大问题”转化为一个或几个“小问题”,但要保证转化后的“小问题”与“大问题”具有求解过程的相似性(递归体即刻画这种相似性,并严格确定了转化模式),从而使大问题逐步化小直到遇到递归的出口即最小问题有明确的值或可以很容易计算得到值,然后,再返回