计算思维之问题求解思想.pptx

第六讲计算思维之问题求解思想,主题一探讨问题求解过程主题二相关知识的认识与了解主题三关于算法的理解主题四算法策略大搜罗主题五几个经典案例的算法实现,算法策略概述,算法策略（AlgorithmPolicy）就是在问题空间中搜索所有可能的解决问题的方法，直至选择一种有效的方法解决问题。策略是面向问题的，算法是面向实现的。问题空间（ProblemSpace）是问题解决者对一个问题所达到的全部认识状态，它是由问题解决者利用问题所包含的信息和已贮存的信息主动地构成的。,算法策略概述,问题空间会随着问题解决的进程而逐渐得到丰富和扩展。而且，在解决某一特定问题时，不同个体的问题空间可能是有差别的。一个问题解决者对问题的解决过程，就是穿越其问题空间搜索一条通往问题目标状态的路径。事实上，对大多数问题来说，可以通过多条路径来达到问题的解决。经典的算法策略主要包括：枚举算法、递推算法、递归算法、迭代算法、分治算法、贪心算法和回溯算法等。,主题四算法策略大搜罗,枚举算法递推算法递归算法迭代算法分治算法贪心算法回溯算法,枚举算法定义,算法定义枚举算法（ExhaustAlgorithm），又名穷举法，也称为暴力破解法，是一种针对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的约束条件，从而得到问题的解。,枚举算法特点,算法特点问题的答案是一个有穷的集合，即答案可以被一一列举出来；问题存在给定的约束条件，根据条件可以判断哪些答案符合要求，哪些答案不符合要求；算法存在循环运算，通常用循环结构遍历所有的有穷集合，从而实现问题的求解。算法优点：思路简单，无论是程序编写，还是调试都很方便。如果问题规模不是很大，在规定的时间与空间限制内能够求出解，那么枚举法是最直接简单的不二选择。算法缺点：运算量比较大，解题效率不高。如果枚举范围太大（一般以不超过2000000次为限），效率低的问题会在时间上难以承受。,枚举算法思路,算法思路一般用于决策类最优化问题，适合那些很难找到大、小规模之间的关系，也不易对问题进行分解的问题。算法思路就是对问题所有的解逐一尝试，从而找出问题的真正解。枚举算法一般按照如下三个步骤进行：第一步：确定解题范围，枚举出所有可能的题解；第二步：判断题解是否符合正解的条件；第三步：使可能解的范围降至最小，以便提高解题效率。,枚举算法案例,算法案例虽然枚举算法效率并不算高，但是适合于一些没有明显规律可循或者缺失足够数据依据的问题。【百钱买买百鸡问题】今有鸡翁一，值钱伍；鸡母一，值钱三；鸡鶵三，值钱一。凡百钱买鸡百只，问鸡翁、母、鶵各几何？使用不定方程求解“百钱买百鸡”的问题，其解题如下：设公鸡X只，母鸡Y只，小鸡Z只；则：X+Y+Z=100，5*X+3*Y+Z/3=100；由于鸡和钱的总数都是100，可以确定X、Y、Z的取值范围。X的取值范围为020（1005=20），Y的取值范围为033（100333），Z=100-X-Y；使用枚举算法解决这样的问题，只需通过两重循环遍历X、Y的所有可能组合值，并将每组X、Y、Z的值代入两个限制约束条件的方程中，如果满足条件即得到问题的解（可能存在多个符合约束条件的解）。,枚举算法案例,算法案例【破译密码问题】枚举算法也常用于密码的破译，即将密码进行逐个推算直到找出真正密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。在一些领域，为了提高密码的破译效率而专门为其制造的超级计算机也不在少数，例如IBM公司为美国军方制造的“飓风”就是很有代表性的一个特例。,主题四算法策略大搜罗,枚举算法递推算法递归算法迭代算法分治算法贪心算法回溯算法,递推算法定义,算法定义递推算法（RecurrenceAlgorithm）是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。,递推算法特点,算法特点由当前问题的逐步解决从而得到整个问题的解；问题的求解依赖于信息间本身的递推关系，每一步不需要决策参与到算法中，使用“步步为营”的方法，不断利用已有的数据信息推导出新的数据信息；问题以初始起点值为基础，用相同的运算规律，逐次重复运算，直至运算结束；这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。算法优点：思路简单，无论是程序编写，还是调试都很方便。运行效率不低。算法缺点：运算的过程值（如果选择数组结构的话）比较多，耗用空间量比较大，但如果选用简单变量通过迭代的方法处理数据之间的关系，可以节省对空间的耗用。,递推算法思路,算法思路递推的本质是按规律逐次推出（计算）下一步的结果，所以更多用于计算。递推是计算序列的一种常用算法。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。递推算法一般按照如下三个步骤进行：第一步：确定问题的数据信息之间存在着特定的递推关系，并用数学公式描述出来，如：给定一个数的序列H0,H1,Hn,若存在整数N0，使当NN0时,可以用等号（或大于号、小于号）将Hn与其前面的某些项Hi（0Y时，肯定存在着X=Q*Y+R的关系。其中：Q是X除以Y之后得到的商的整数部分，R是X除以Y之后得到的余数。辗转相除法是一个反复迭代执行，直到余数等于0停止的步骤，这实际上是一个循环结构。,迭代算法案例,算法案例【最大公约数问题】最经典的迭代算法是欧几里德的辗转相除算法，用于计算两个整数X，Y的最大公约数。求X和Y最大公约数G（X，Y）的步骤如下：用Y除X，得Q余R1(0R1）。若R1=0，则G（X，Y）=Y；若R10，则再用R1除Y，得Q余R2（0R2）。若R2=0，则G（X，Y）=R1，若R20，则继续用R2除R1，如此下去，直到能整除为止。其最后一个非零除数即为X和Y的最大公约数G（X，Y）。,迭代算法案例,算法案例【斐波那契数列问题】还有一个很典型的例子就是斐波那契（Fibonacci）数列。0、1、1、2、3、5、8、13、21、，即f(1)=1；f(2)=1；f(n)=f(n-1)+f(n-2)(当n2时)。在n2时，f(n)总可以由f(n-1)和f(n-2)得到，由旧值递推出新值，这是一个典型的迭代关系，所以我们可以考虑迭代算法。,主题四算法策略大搜罗,枚举算法递推算法递归算法迭代算法分治算法贪心算法回溯算法,分治算法定义,算法定义分治算法（DivideAndConquerAlgorithm）是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即为子问题的解的合并。,分治算法定义,算法定义任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。“分而治之”技巧是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）等。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,分治算法特点,算法特点当问题的规模缩小到一定的程度就可以容易地解决；当问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用问题分解出的子问题的解可以合并为问题的最终解；问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。,分治算法思路,算法思路分治一般用于较复杂的问题，但是这个问题必须可以逐步被分解为容易解决的独立的子问题，这些子问题解决后，进而将它们的解“合成”，就得到较大问题的解，最终合成为总问题的解。分治算法一般按照如下三个步骤进行：分解，将要解决的问题划分成若干规模较小的同类问题；求解，当子问题划分得足够小时，用较简单的方法解决；合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。,分治算法案例,算法案例【排查伪币问题】给你一个装有N枚硬币的袋子。N枚硬币中有一个是伪造的，并且那枚伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。对于这个问题比较直接的方法就是顺序查找法，两个一对进行比较，如果重量不同，轻者即为伪币；如果重量相同，则继续两个一对进行比较，这样可以最多通过N/2次比较来判断伪币的存在并找出这枚伪币。另外一种方法就是利用分而治之方法。假如把N枚硬币的问题看成一个大的问题。,分治算法案例,算法案例【排查伪币问题】第一步，把这一问题分成两个小问题。随机选择N/2枚硬币作为第一组称为A组，剩下的N/2枚硬币作为第二组称为B组。这样，就把N枚硬币的问题分成两个N/2硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。第三步，用第二步的结果得出原先N枚硬币问题的答案。若仅仅判断伪造硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这N枚硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。,分治算法案例,算法案例【排查伪币问题】首先设定把两枚或三枚硬币的情况作为不可再分的小问题。注意如果只有一枚硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一枚硬币分别与其他两枚硬币比较，最多比较两次就可以找到伪币。这样，N枚硬币的问题就被分为两个N/2枚硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。,