算法设计_算法设计与分析 - CSDN
精华内容
参与话题
  • 算法设计[中文版].pdf

    2020-07-24 23:32:43
    jon Kleinberg,Eva Tardos著;张立昂,屈婉玲译的算法设计算法设计中文入门版。我们上课时用的这本,,很不错
  • 算法设计经典算法

    千次阅读 2019-07-11 11:06:51
    一、贪婪算法 1、概述 贪婪法又称贪心算法,是当追求的目标是一个问题的最优解时,设法把对整个问题的求解工作分成若干步骤来完成,是寻找最优解问题的常用方法。 贪婪法的特点是一般可以快速得到满意的解,因为...

    一、贪婪算法

    1、概述

    贪婪法又称贪心算法,是当追求的目标是一个问题的最优解时,设法把对整个问题的求解工作分成若干步骤来完成,是寻找最优解问题的常用方法。

    贪婪法的特点是一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。如装箱问题和和着色问题都可以采用贪婪法来求解。

    2、问题实例

    现在根据实际问题来说明贪婪法的算法思想。

    装箱问题

    问题描述:装箱问题可简述如下:设有编号为0、1、…、n-1的n种物品,体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V,即对于0≤i<n,有0<vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。 
       若考察将n种物品的集合分划成n个或小于n个物品的所有子集,最优解就可以找到。但所有可能划分的总数太大。对适当大的n,找出所有可能的划分要花费的时间是无法承受的。为此,对装箱问题采用非常简单的近似算法,即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n件物品按它们的体积从大到小排序,然后按排序结果对物品重新编号即可。装箱算法简单描述如下: 
    {   输入箱子的容积; 
       输入物品种数n; 
       按体积从大到小顺序,输入各物品的体积; 
       预置已用箱子链为空; 
       预置已用箱子计数器box_count为0; 
       for (i=0;i<n;i++) 
       {   从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j; 
          if (已用箱子都不能再放物品i) 
          {   另用一个箱子,并将物品i放入该箱子; 
             box_count++; 
          } 
          else 
             将物品i放入箱子j; 
       } 

       上述算法能求出需要的箱子数box_count,并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解,设有6种物品,它们的体积分别为:60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。按上述算法计算,需三只箱子,各箱子所装物品分别为:第一只箱子装物品1、3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子,分别装物品1、4、5和2、3、6。 
     二、分治法

    1、概述

    分治法的基本思想是把一个规模较大的问题分成两个或者多个较小的和原问题相似的子问题,首先对子问题进行求解,然后再把各个子问题的解合并起来,得出整个问题的解。

    2、问题实例

    分治法的三个步骤:

    step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
    step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
    step3 合并:将各个子问题的解合并为原问题的解。

    实例:

    在一个未排序的数组中找到第k大元素,即排序后的第k大的数。

    分析:

    总是将要划界的数组段末尾的元素为划界元,将比其小的数交换至前,比其大的数交换至后,最后将划界元放在“中间位置”(左边小,右边大)。划界将数组分解成两个子数组(可能为空)。

    设数组下表从low开始,至high结束。
    1、 总是取要划界的数组末尾元素为划界元x,开始划界:

    a) 用j从low遍历到high-1(最后一个暂不处理),i=low-1,如果nums[j]比x小就将nums[++i]与nums[j]交换位置

    b) 遍历完后再次将nums[i+1]与nums[high]交换位置(处理最后一个元素);

    c) 返回划界元的位置i+1,下文称其为midpos

    这时的midpos位置的元素,此时就是整个数组中第N-midpos大的元素,我们所要做的就像二分法一样找到K=N-midpos的“中间位置”,即midpos=N-K

    2、 如果midpos==n-k,那么返回该值,这就是第k大的数。
    3、 如果midpos>n-k,那么第k大的数在左半数组
    4、 如果midpos<n-k,那么第k大的数在右半数组

    三、回溯法

    1、概念

    回溯法也称试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按照某种顺序之一枚举和检验。回溯法的基本思想是采用深度优先策略,一步一步向前试探的方法,当某一步有多种选择时,可以先任意选择一种,继续向前试探。一旦发现到达某步后无法再前进,说明上一步做的选择有问题,就后退到上一步重新选择(这就称为回溯)。回溯法的特点是可以避免穷举式的盲目搜索,从而可能减少问题求解的搜索时间。如迷宫问题和八皇后问题都可以采用回溯方法来设计求解算法。
    2、问题实例

    回溯法的一般步骤:

    (1)针对所给问题,确定问题的解空间:首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

    (2)确定结点的扩展搜索规则

    (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

    八皇后问题
    问题描述:八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

    转化规则:其实八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。令一个一维数组a[n]保存所得解,其中a[i] 表示把第i个皇后放在第i行的列数(注意i的值都是从0开始计算的),下面就八皇后问题的约束条件。
    (1)因为所有的皇后都不能放在同一列,因此任意两个a[0].....a[7]的值不能存在相同的两个值。
    (2)所有的皇后都不能在对角线上,那么该如何检测两个皇后是否在同一个对角线上?我们将棋盘的方格成一个二维数组,如下:


    假设有两个皇后被放置在(i,j)和(k,l)的位置上,明显,当且仅当|i-k|=|j-l| 时,两个皇后才在同一条对角线上。

    四、动态规划法

    1、概述

    动态规划与分治法相似,都是把一个大问题分解为若干较小的子问题,通过求解子问题而得到原问题的解.不同的是分治法每次分解的子问题数目较少,子问题之间界限清楚,处理的过程通常是自顶向下进行;而动态规划法分解子问题可能较多,而且子问题相互包含,为了重用已经计算的结果,要把计算的中间结果保存起来,动态规划法通常是自底向上进行。

     2、问题实例

    动态规划的思路是通过寻找最优子结构同时记录最优结构,从而将复杂的大问题转化为小问题的求解过程。解决动态规划类问题,分为两步:1.确定状态,2.根据状态列状态转移方程

    例题:背包问题1

    在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]。

    首先寻找状态,确定将什么作为状态,记录状态,有背包和物品,物品有放和不放两种状态,放置的时候可能会对应各种容量,当前的容量下可以放置进的最多的物品取决于上一个物品放置时在该状态下所能够达到的最大状态和当前物品的的大小,这样我们在最后,就可以得到每种容量下,所能放置的物品的最大数量。

    背包问题2:

    给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大?

    考虑到价值问题,状态不发生变化,只是对于状态我们所记录的内容方式变化,我们现在记录的是其价值,而不是其放置的物品的大小。

     五、分支限界法

    1、概述

    分枝界限法(Branch and Bound)与回溯法相似,也是一种在全部问题解的空间中进行系统搜索的方法。所不同的是,回溯法使用深度优先策略,而分支界限法可以采用广度优先策略。与此同时,分支界限法在搜索过程中,还利用最优解属性的上下界来控制搜索的分支,剪去不必再花时间搜索的部分,从而提高搜索的效率。
    2、算法

    算法基本思想如下:

    1)以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树
    2)分支限界法中,每一个活结点只有一次机会成为扩展结点,活结点一旦成为扩展结点,就一次性产生其所有儿子结点,其中导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中
    3)然后从活结点表中取下一结点成为当前扩展结点
    4)重复上述结点扩展过程,直至到找到所需的解或活结点表为空时为止

    分支限界法与回溯法的区别:

    1)求解目标不同 
            回溯法的求解目标是找出解空间树中满足约束条件的所有解
            分支限界法的求解目标则是尽快找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解
            分支限界法通常用于解决离散值的最优化问题
    2)搜索方式不同 
            回溯法以深度优先的方式(遍历结点)搜索解空间树
            分支限界法以广度优先或最小耗费优先的方式搜索解空间树
    3)对扩展结点的扩展方式不同 
            分支限界法中,每一个活结点只有一次机会成为扩展结点
            活结点一旦成为扩展结点,就一次性产生其所有儿子结点
    4)存储空间的要求不同 
            分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大

    参考:

    https://blog.csdn.net/K346K346/article/details/50774803

    https://blog.csdn.net/jia_xiaoxin/article/details/2750880

    https://blog.csdn.net/EbowTang/article/details/51218500

    https://segmentfault.com/a/1190000004498566

    https://blog.csdn.net/u010089444/article/details/74331907

    展开全文
  • 算法设计之五大常用算法设计方法总结

    万次阅读 多人点赞 2014-10-03 10:04:33
    算法设计之五大常用算法设计方法总结 一、【分治法】  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的...

    算法设计之五大常用算法设计方法总结

    一、【分治法】
     在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……等。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。
    分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之
    分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法
    如果原问题可分割成k(1<k≤n)个子问题, 且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用"递归技术"提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解,这自然导致递归过程的产生。"分治"与"递归"像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法
    分治法所能解决的问题一般具有以下几个特征:
    1) 该问题的规模缩小到一定的程度就可以容易地解决
    2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。(前提)
    3) 利用该问题分解出的子问题的解可以合并为该问题的解;(最关键的一点)
    4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题
    上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。
    分治法的基本步骤
    分治法在每一层递归上都有三个步骤:
    1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
    2)解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
    3)合并:将各个子问题的解合并为原问题的解。
    它的一般的算法设计模式如下:
    Divide-and-Conquer(P)
    if |P|≤n0 {
           then return(ADHOC(P))
    }else{
             将P继续分解为较小的子问题 P1 ,P2 ,...,Pk
         for i←1 to k
         do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
         T ← MERGE(y1,y2,...,yk) △ 合并子问题
    }
    return(T)
    其中|P|表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法,用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。
    分治法的应用:1.递归与HANOI塔问题; 2.二分法求方程近似解    3. 用C++实现合并排序   4.求最大值和最小值的分治算法
    分治法的复杂性分析
    一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有: 
        
    通过迭代法求得方程的解: 
    
    
    递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的,从而当mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)。
    二、【动态规划法】
    最优化原理
    1951年美国数学家R.Bellman等人,根据一类多阶段问题的特点,把“多阶段决策”问题变换为一系列互相联系的“单阶段问题然后逐个加以解决。而且一些静态模型,只要人为地引进“时间”因素,分成时段,就可以转化成多阶段的动态模型,用动态规划方法去处理。与此同时,他提出了解决这类问题的“最优化原理”(Principle of optimality):“一个过程的最优决策具有这样的性质:即无论其初始状态和初始决策如何,其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优策略”。简言之,一个最优策略的子策略,对于它的初态和终态而言也必是最优的。这个“最优化原理”如果用数学化一点的语言来描述的话,就是:假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是最优的。
    最优化原理是动态规划的基础,任何一个问题,如果失去了这个最优化原理的支持,就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件:
    (1) 问题中的状态必须满足最优化原理;
    (2) 问题中的状态必须满足无后效性。
    所谓的无后效性是指:“下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前的状态是对以往决策的总结”。
    问题求解模式
    动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。
    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
    图1 动态规划决策过程示意图
    (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
    (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
    (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两段各状态之间的关系来确定决策。
    (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。
    动态规划法的应用:1.动态规划求0/1背包问题      2.最长公共子串问题的实现 3. 用动态规划实现导弹拦截      4.最大化投资回报问题的实现
    算法实现
    动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。使用动态规划求解问题,最重要的就是确定动态规划三要素:问题的阶段,每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。下面分别以求解最大化投资回报问题和最长公共子序列问题为例阐述用动态规划算法求解问题的一般思路。
    三、【贪心算法】
    所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
    贪心算法的基本思路如下:
    1.建立数学模型来描述问题。
    2.把求解的问题分成若干个子问题。
    3.对每一子问题求解,得到子问题的局部最优解。
    4.把子问题的解局部最优解合成原来解问题的一个解。
    实现该算法的过程:
    从问题的某一初始解出发;
    while 能朝给定总目标前进一步 do
    求出可行解的一个解元素;
    由所有解元素组合成问题的一个可行解;
    下面是一个可以使用贪心算法解的题目,贪心解的确不错,可惜不是最优解:
    例题分析:
    [背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
    要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
    物品:  A   B   C   D   E    F   G
    重量: 35  30  60  50  40  10  25
    价值: 10  40  30  50  35  40  30
    分析:
    目标函数: ∑pi最大
    约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)
    (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
    (2)每次挑选所占重量最小的物品装入是否能得到最优解?
    (3)每次选取单位重量价值最大的物品,成为解本题的策略。
    值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。可惜的是,它需要证明后才能真正运用到题目的算法中。
    一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
    对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:
        (1)贪心策略:选取价值最大者。反例:
        W=30
        物品:A B C
        重量:28 12 12
        价值:30 20 20
        根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。
        (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。
        (3)贪心策略:选取单位重量价值最大的物品。反例:
        W=30
        物品:A B C
        重量:28 20 10
        价值:28 20 10
    根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。
    贪心算法应用:1.最小生成树之Prim算法  2. 最小生成树之kruskal算法
    3. 贪心算法在背包中的应用 4.汽车加油问题之贪心算法
    四、【回溯法】
    回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
    1、回溯法的一般描述
    可用回溯法求解的问题P,通常要能表达为:对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)∣xi∈Si ,i=1,2,…,n},给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域,且 |Si| 有限,i=1,2,…,n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
    解问题P的最朴素的方法就是枚举法,即对E中的所有n元组逐一地检测其是否满足D的全部约束,若满足,则为问题P的一个解。但显然,其计算量是相当大的。
    我们发现,对于许多问题,所给定的约束集D具有完备性,即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束意味着j(j<i)元组(x1,x2,…,xj)一定也满足D中仅涉及到x1,x2,…,xj的所有约束,i=1,2,…,n。换句话说,只要存在0≤j≤n-1,使得(x1,x2,…,xj)违反D中仅涉及到x1,x2,…,xj的约束之一,则以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)一定也违反D中仅涉及到x1,x2,…,xi的一个约束,n≥i>j。因此,对于约束集D具有完备性的问题P,一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束,就可以肯定,以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解,因而就不必去搜索它们、检测它们。回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。
    回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树,它可以这样构造:设Si中的元素可排成xi(1) ,xi(2) ,…,xi(mi-1) ,|Si| =mi,i=1,2,…,n。从根开始,让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边,按从左到右的次序,分别带权xi+1(1) ,xi+1(2) ,…,xi+1(mi) ,i=0,1,2,…,n-1。照这种构造方式,E中的一个n元组(x1,x2,…,xn)对应于T中的一个叶子结点,T的根到这个叶子结点的路径上依次的n条边的权分别为x1,x2,…,xn,反之亦然。另外,对于任意的0≤i≤n-1,E中n元组(x1,x2,…,xn)的一个前缀I元组(x1,x2,…,xi)对应于T中的一个非叶子结点,T的根到这个非叶子结点的路径上依次的I条边的权分别为x1,x2,…,xi,反之亦然。特别,E中的任意一个n元组的空前缀(),对应于T的根。
    因而,在E中寻找问题P的一个解等价于在T中搜索一个叶子结点,要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1,x2,…,xn满足约束集D的全部约束。在T中搜索所要求的叶子结点,很自然的一种方式是从根出发,按深度优先的策略逐步深入,即依次搜索满足约束条件的前缀1元组(x1i)、前缀2元组(x1,x2)、…,前缀I元组(x1,x2,…,xi),…,直到i=n为止。
    在回溯法中,上述引入的树被称为问题P的状态空间树;树T上任意一个结点被称为问题P的状态结点;树T上的任意一个叶子结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点,它对应于问题P的一个解.
    用回溯法解题的一般步骤:
    (1)针对所给问题,定义问题的解空间;
    (2)确定易于搜索的解空间结构;
    (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
    回溯法应用:1.回溯法之数的划分               2.回溯法求解 运动员最佳配对问题 
    3.回溯法解决汽车加油次数最少问题 4. 用回溯法找出n个自然数中取r个数的全排列
    五、【分支限界法】
    基本思想 :分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。 
    在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。 此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
    常见的两种分支限界法:
    (1)队列式(FIFO)分支限界法
    按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。 
    (2)优先队列式分支限界法
    按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
    分支限界法与回溯法的不同:
    (1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。 
    (2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
    解空间树的动态搜索
    (1)回溯求解0/1背包问题,虽剪枝减少了搜索空间,但整个搜索按深度优先机械进行,是盲目搜索(不可预测本结点以下的结点进行的如何)。
    (2)回溯求解TSP也是盲目的(虽有目标函数,也只有找到一个可行解后才有意义)
    (3)分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界[down, up];然后按照广度优先策略遍历问题的解空间树,在某一分支上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值(对最小化问题,估算结点的down,对最大化问题,估算结点的up)。如果某孩子结点的目标函数值超出目标函数的界,则将其丢弃(从此结点生成的解不会比目前已得的更好),否则入待处理表。
    分支限界法的设计思路
    设求解最大化问题,解向量为X=(x1,…,xn),xi的取值范围为Si,|Si|=ri。在使用分支限界搜索问题的解空间树时,先根据限界函数估算目标函数的界[down, up],然后从根结点出发,扩展根结点的r1个孩子结点,从而构成分量x1的r1种可能的取值方式。
    对这r1个孩子结点分别估算可能的目标函数bound(x1),其含义:以该结点为根的子树所有可能的取值不大于bound(x1),即:
    bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)
    若某孩子结点的目标函数值超出目标函数的下界,则将该孩子结点丢弃;否则,将该孩子结点保存在待处理结点表PT中。
    再取PT表中目标函数极大值结点作为扩展的根结点,重复上述。
    直到一个叶子结点时的可行解X=(x1,…,xn),及目标函数值bound(x1,…,xn)。
    分支限界法应用:1.分支限界法之装载问题       2. 分支限界法之布线问题 
    3. 分支限界法之0 1背包问题 4. 分支限界法之旅行售货员问题
    整理参考:http://c.chinaitlab.com/special/algorithm/Index.html 
    展开全文
  • 算法设计》是近年来关于算法设计和分析的不可多得的优秀教材。《算法设计》围绕算法设计技术组织素材,对每种算法技术选择了多个典型范例进行分析。《算法设计》将直观性与严谨性完美地结合起来。每章从实际问题...
  • 算法设计 算法设计 算法设计 算法设计 算法设计 算法设计 算法设计
  • 算法设计

    2019-06-22 11:24:00
    分治算法能解决问题的特征: –问题规模缩小到一定的程度可以容易地解决 –问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质 –利用该问题分解出的子问题的解可以合并为该问题的解 –该问题所...
    方法 试用情况
    分治法 各子问题独立
    动态规划 各子问题重叠
    贪心

    1.分治

    分治算法能解决问题的特征:
    –问题规模缩小到一定的程度可以容易地解决
    –问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
    –利用该问题分解出的子问题的解可以合并为该问题的解
    –该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题

    解题步骤:
    – 划分阶段的时间复杂性
    • 划分问题为a个子问题。
    • 每个子问题大小为n/b。
    • 划分时间可直接得到=D(n)
    – 递归求解阶段的时间复杂性
    • 递归调用
    • 求解时间= aT(n/b)
    – 合并阶段的时间复杂性
    • 时间可以直接得到=C(n)

    复杂度:
    • T(n)=(1) if n<c
    • T(n)=aT(n/b)+D(n)+C(n) if nc

    2.动态规划

    • 分治技术的问题
    – 子问题是相互独立的
    – 如果子问题不是相互独立的,分治方法将重复计算公共子问题,效率很低

    • 动态规划算法特点
    – 把原始问题划分成一系列子问题
    – 求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时直接存取,不重复计
    算,节省计算时间
    – 自底向上地计算

    使用Dynamic Programming的条件:
    – Optimal substructure(优化子结构)
    • 一个问题的优化解包含了子问题的优化解
    – Subteties(重叠子问题)
    • 在问题的求解过程中,很多子问题的解将被多次使用

    例1:
    最长公共子序列LCS
    在这里插入图片描述
    例2:
    矩阵链乘
    优化子结构:
    A1n=A1kAk+1n,则在A1n的优化顺序中,对应于子问题A1k的解必须是A1-k的优化解,对应于子问题Ak+1n的解必须是Ak+1n的优化解
    m[i, i] = 计算Ai  i 的最小乘法数= 0
    m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj
    其中, pi-1pkpj是计算AikAk+1j所需乘法数,
    Ai k和Ak+1  j分别是pi-1pk和pkpj矩阵.
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    时间复杂度(n3)空间(n2)

    3.贪心

    贪心选择性:一个全局最优解可以通过局部最优得到。
    即存在一个最优解是以贪心选择开始的。

    优化子结构:一个最优解包括期子问题的最优解。
    即一个n的最优解分解成第一步的贪心选择,和n-1的子问题,这个n-1的子问题也是最优的。

    最后要说明,第一步的贪心选择和n-1的子问题可以合并成一个全局最优解。

    展开全文
  • 实现与提高算法设计能力的一般方法

    可以毫无讳言的说:算法能力是进入名企和获得高薪的最重要的能力。有一个著名的等式就是:程序设计语言 + 算法 = 软件。因此程序员要想提高自己的编程能力,写出优秀的软件,必须具备扎实的编程语言应用能力,灵活的算法设计能力,此外还应具备丰富的某个专业领域技能和经验(这一点对于非应届的朋友来说,非常重要。如果你之前没有搜索引擎开发经验,那么很少有搜索公司对你的简历感兴趣;如果你没有过安全软件开发,系统内核开发经验,那么也很少有安全公司对你的简历感兴趣),但归根结底还是算法设计。算法设计是计算机软件设计与开发的核心。编程语言与开发领域可以变化,你可以今天用C,明天用Java,你也可以今天做Web开发,明天做底层安全开发,但是算法设计以及数据结构却是相通的。

     

    实际上,从笔者多年的开发经验来讲,笔者总结出了这么一个等式:程序 = 算法(包括数据结构)+ API调用 + “Hello world” + 字符串处理 + 内存管理(部分语言如java,python等无内存管理)。其中算法是程序的核心和灵魂。API是程序调用开发库中的接口,用来实现特定的功能和任务。一个程序不可能不调用API来完成功能。无论学哪个方面的编程,我们都可以从最简单的“Hello world”开始,学习它的开发环境搭建,程序结构框架,调试以及编译执行。剩下就是可能的大量字符串的处理和内存的操作,其中字符串处理会占程序代码中至少10%以上,这也是为什么很多企业(包括微软)会特别喜欢考查与字符串相关的算法题。

    算法说白了,就是指程序员的编程能力,它是IT新手最需要训练和提高的地方,算法问题也是IT面试中的最具挑战性的问题,这直接反应了程序员的基本素质,因此答不好算法问题(一般就是在纸上或者黑板上甚至上机写代码解决问题),一般很难通过面试,那么离名企和高薪就会很遥远。为了有效提高大家的算法能力(也就是编程能力),麦洛克菲在长期的算法教学中不断积累了宝贵的教学经验,获得了满意的教学效果,不少同学算法得到了明显的提高,反映写程序不再吃力。

    现在麦洛克菲将这些经验公开,为程序员朋友提供了如下9点经验总结,供程序员朋友们参考:

    1,确定函数名字与原型


    一旦拿到有关算法的问题,那么就应该分析问题,找到对应的输入输出,从而确定出算法的函数原型。我们写算法,其实就是写一个或者若干个普通的函数(而不是main函数)。因此,需要分析出,应该传什么参数给函数(作为输入参数),函数处理完后,应该把什么数据作为结果返回(作为输出参数)。最后还要给函数取一个符合算法意义的名字,名字最好用英语表示,如果用拼音,会显得特别山寨的感觉。函数的命名方式与变量的命名方式都有相关的约定,比如匈牙利命名法,Linux命名法或者驼峰命名法等。

    比如,有这么一个典型的算法问题:将一个字符串逆置,比如:”hello world”-->”dlrow olleh”

    对于这道题,我们分析之后,应该知道,输入是一个普通的字符串,输出是将这个字符串逆置之后的字符串,因此,可以确定函数的原型:

    void reverse_str(char *str);//str既是输入,也是输出
    {

    }
    或者
    void reverse_str(char *str, size_t len)//str既是输入又是输出,len是字符串的长度
    {

    }

    很多初学者在这里容易犯的错误包括:只对字符串“hello world”进行了逆置而忽视了算法解决的是通用的一般性问题,或者把相关的代码直接写在了main()函数里。

    此外,就是需要有模块化的思想。一个函数只单独完成一个单一的功能,函数的代码行数一般很少超过100行,加上注释不会超过300行。 因此,要把那些频繁使用而功能又比较单一的代码放在一个独立的函数里。不要在一个函数里完成N个功能,这不利于调试和维护,也和模块化是相背离的。

    2,严进宽出


    确定好了函数的原型之后,紧接着在完成这个函数的功能一开始的地方,就需要严格判断函数输入参数的合法性,我们称之为:严进宽出。具体点说,就是要判断函数参数中的指针是否为NULL,函数参数中缓存的长度是否在合理范围。这一点非常的重要。

    比如同样对于第1点里的函数原型,那么我们就需要作出如下的判断:

    void reverse_str(char *str, size_t len)
    {
        /*首先判断str指针是否为NULL或者len是否为0和1,这些都是特殊情况或者非法输入,因此要严格检查,严进宽出。*/
        if(str== NULL || *str=='\0'|| len==0 || len==1)
        {
            return;
        }
        //程序如果执行到这里,那么参数检测就完成了并合法了。因此可以继续完成相应的功能了。
        ......
    }

    严进宽出是写程序的一个非常好的习惯,可以避免程序在运行中出错,甚至避免各种严重漏洞的产生。比如曾经十分严重的SSL协议中的心脏流血漏洞,就是因为服务端程序在处理的时候,没有验证来自客户端对应的缓存长度的有效性,而造成了该漏洞的产生。

    3,边界考虑


    边界考虑就是要考虑程序中各种各样的特殊情况,而不是只考虑其中的一种情况。我们在写算法的时候,经常会忘记多种情况的周全考虑,而忽略了很多特殊的情况,对程序的健壮性带来影响。

    1.边界条件是指软件计划的操作界限所在的边缘条件。数据类型:数值、字符、位置、数量、速度、地址、尺寸等,都会包含确定的边界。应考虑的特征:第一个/最后一个、开始/完成、空/满、最慢/最快、相邻/最远、最小值/最大值、超过/在内、最短/最长、最早/最迟、最高/最低。这些都是可能出现的边界条件。边界条件测试通常是对最大值简单加1或者很小的数和对最小值减少1或者很小的数,例如:

    l         第一个减1/最后一个加1;

    l         开始减1/完成加1;

    l         空了再减/满了再加;

    l         慢上加慢/快上加快;

    l         最大数加1/最小数减1;

    l         最小值减1/最大值加1;

    l         刚好超过/刚好在内;

    l         短了再短/长了再长;

    l         早了更早/晚了更晚;

    l         最高加1/最低减1。

    另一些该注意的输入:默认,空白,空值,零值和无;非法,错误,不正确和垃圾数据。根据边界来选择等价分配中包含的数据。然而,仅仅测试边界线上的数据点往往不够充分。提出边界条件时,一定要测试临近边界的合法数据,即测试最后一个可能合法的数据,以及刚超过边界的非法数据。

    2.默认值测试(默认、空白、空值、零值和无)

    好的软件会处理这种情况,常用的方法:一是将输入内容默认为合法边界内的最小值,或者合法区间内某个合理值;二是返回错误提示信息。

    这些值在软件中通常需要进行特殊处理。因此应当建立单独的等价区间。在这种默认下,如果用户输入0或-1作为非法值,就可以执行不同的软件处理过程。

    3.破坏测试(非法、错误、不正确和垃圾数据)

    数据测试的这一类型是失败测试的对象。这类测试没有实际规则,只是设法破坏软件。不按软件的要求行事,发挥创造力吧。

     

    举一个例子:实现C库中的memmove函数。

     

    很多程序员可能会很快写出如下程序:

     

    void memcpy(void *pDst,const void *pSrc, size_t size)

    {

        assert(pDst != NULL);

        assert(pSrc != NULL);

        char *pstrSrc= (char *)pSrc ;  

        char *pstrDst = (char *)pDst ;

        /* 从起始部正向拷贝 */

        while(size--)   

            *pstrDst++ = *pstrSrc++;

    }

    但是,这里忽略了一个很重要的情况就是:pDst和pSrc指定的内存有可能是重叠的。如果按照这样拷贝的话,那么如果

                                                     (pSrc<pDst) && ((char*)pSrc+size > pDst)

    那么,按照上面的程序代码拷贝,将会把pSrc尾巴部分的数据覆盖污染了。

    因此,必须清楚的考虑pSrc和pDst二者之间的关系,采取不同的算法,实际上,pSrc和pDst的位置关系有如下图4种情况,其中第2种情况,需要特殊处理。

    如上图的位置关系所示,在第2种位置中,也就是当(pSrc<pDst) && ((char*)pSrc+size > pDst)时,从前往后拷会有问题。必须从后往前面拷贝:

    void memcpy(void *pDst,const void *pSrc, size_t size)

    {

        assert(pDst != NULL);

        assert(pSrc != NULL);

        /* pSrc与pDst共享同一块内存区域 */

        if((pSrc<pDst) && ((char*)pSrc+size > pDst))

        {  

            char *pstrSrc= (char *)pSrc + size -1;  

            char *pstrDst = (char *)pDst + size -1;

            / * 从尾部逆向拷贝 */

            while(size--)   

                *pstrDst -- = *pstrSrc--;

        }

        else

        {  

            char *pstrSrc= (char *)pSrc ;  

            char *pstrDst = (char *)pDst ;

            /* 从起始部正向拷贝 */

            while(size--)   

            *pstrDst++ = *pstrSrc++;

        }

    }


    4,出错处理


    出错处理,是指当代码在执行过程中,如果发生了异常或者错误,就必须要处理,否则程序就无法继续执行了,如果强制继续执行,往往可能会导致程序或者系统崩溃。

    比如我们在打开文件的时候,如果文件不存在或者打开失败了;在分配内存的时候,返回内存为NULL,这些情况都需要及时处理。一般处理程序错误或者异常的方法有goto err或者try_except等方式。

    出错处理的方式方式很多,也很灵活。只要不遗漏对错误的处理就行。现在介绍两种错误处理方式:

    1)  goto error方式

    语句goto是大家不大喜欢使用的,也是程序设计专家建议不要使用的一句话。因此goto语句似乎就要退出历史的舞台。但幸好它找到了一个用武之地,那就是用goto error方式来处理出错。下面是一个例子:

     

    NTSTATUS QueryObjectName(HANDLE h)

    {

         int                    ret;

         NTSTATUS      st;

         char                *str = "Hello, how are u?";

         char                *pstr = (char *)malloc(256);

     

         if (pstr == NULL)

         {

             printf("No more memory\n");

             goto Error;

         }

         int len = strlen(str)>255?255:strlen(str);

         strncpy(pstr, str, len);

         pstr[len+1] = '\0';

     

         char *namebuf = (char *)malloc(1024);

         if (buf == NULL)

         {

             printf("No more memory\n");

             goto Error;

         }

         st = NtQueryObject(h, FileNameInformation, namebuf, ret, NULL);

         if (!NT_SUCCESS(st))

         {

             printf("No more memory\n");

             goto Error;

         }

         ...

    Error:

         if (buf)

         {

              free(buf);

         }

         if (pstr)

         {

              free(pstr);

         }

         return st;

    }

     

    goto error方式把错误进行了集中处理,防止了在分支复杂的程序中错误情况的遗漏。

    2)  SHE:__try__leave__exception方式

    SEH( structured exception handling ),即结构化异常处理方式,它是Windows系统独有的异常处理模型,主要由try-except语句来完成,与标准的try-catch相似。C++异常处理模型使用catch关键字来定义异常处理模块,而SEH是采用except关键字来定义;catch关键字后面像接受一个函数参数一样,可以是各种类型的异常数据对象,except关键字则不同,它后面跟的是一个表达式。

     

    NTSTATUS QueryObjectName(HANDLE h)

    {

         int           ret;

         NTSTATUS      st;

         __try

         {

         char          *str = "Hello, how are u?";

         char          *pstr = (char *)malloc(256);

     

         if (pstr == NULL)

         {

             printf("No more memory\n");

             __leave;

         }

         int len = strlen(str)>256?256:strlen(str);

         strncpy(pstr, str, len);

         pstr[strlen(str)] = '\0';

     

         char *namebuf = (char *)malloc(1024);

         if (buf == NULL)

         {

             printf("No more memory\n");

             __leave;

         }

         st = NtQueryObject(h, FileNameInformation, namebuf, ret, NULL);

         if (!NT_SUCCESS(st))

         {

             printf("NtQueryObject failed\n");   

             __leave;

         }

         }

         __except(EXCEPTION_EXECUTE_HANDLER)

         {

             //获得异常代码

             st = GetExceptionCode();

         }

         if (buf)

         {

             free(buf);

         }

         if (pstr)

         {

             free(pstr);

         }

         return st;

    }



    5,性能优化(时间复杂度,空间复杂度)


    大家有时候去参加面试,自我感觉良好,面试官出的算法题,自己感觉也做出来了,也做对了,可为什么面试结束后,迟迟等不来Offer呢?那就很可能是因为你的算法题虽然做出来了,但不是最优的。

    总的来说,衡量算法的优劣有2种标准:时间复杂度和空间复杂度。简单的来说,所谓时间复杂度,就是嵌套的循环越少越好,比如一层循环优于二层循环,面试中一般很少有三层循环的算法;而所谓空间复杂度,就是尽量不要调用malloc或者new来分配额外的内存。复杂度可以用O()来表示,它们之间的效率关系为:
                                         O(1)>O(n)>O(nlogn)>O(n²)>O(2^n)

    对于第1点中的字符串逆置的问题,有如下2种解决方法:

    //算法1:直接基于str所在内存进行逆置

    void reverse_str(char* str, size_t len)

    {

           if (NULL == str || '\0' == *str || 0==len || 1==len)

           {

                  return;

           }

           char *p1=str;

           char *p2=str+len-1;

           while(p1<p2)

           {

                  char c = *p1;

                  *p1 = *p2;

                  *p2 = c;

                  p1++;

                  p2--;

           }

    }

    //算法2,分配一个额外的内存,把字符串从后往前拷贝到内存中

    char *reverse_str(char* str, size_t len)

    {

           if (NULL == str || '\0' == *str || 0==len || 1==len)

           {

                  return;

           }

           char *buf=malloc(len+1);

            char *p2=str +len-1;

            char *p1=buf;

            if(buff == NULL)

            {

                return NULL;

            }

            memset(buf, 0,len+1);

         

           while(len--)

           {

                  *p1++=*p2--;

           }

           return buf;

    }

    2种解法都能够完成把字符串逆置的任务。但是,第二种算法,额外分配了内存(复杂度为O(n)),空间复杂度上第一种占据了优势。

    空间复杂度很好理解。而时间复杂度,想要容易的写出O(n)或者O(1)的算法,就需要仔细思考问题和设计算法了,并且还应该学习一些常见的算法技巧。比如:2个指针跑步,比如hash算法,比如递归等,详见下面的方法总结。

    思考题:用尽量高效的方法(比如O(1))来删除单向非循环链表中的某个结点。
    原型:bool delete_node(node *&head, node *p)

    6,循环的掌握


    一个再复杂的算法程序,都是由循环,条件,顺序三种语句构成的(switch语句也可以转化为条件语句)。而这三种语句中,循环语句的使用是其中的关键。循环语句用来遍历和操作对应的数据结构。前几节中,几乎每个算法都用到了循环语句。以循环语句为核心,循环语句把其他语句联系起来。因此,算法中,最重要的地方就是对循环的熟练掌握与使用。

     

    下面把常用的各种数据结构的循环语句列出,方便大家在编程的时候使用:

    1.数组

     

    for (int i = 0; i < n; i++)

    {

         printf(“%d\n”, a[i]);

    }

     

    2.字符串

     

    while (*str !=’\0’)

    {

         str++;

    }

     

    3.链表

     

    while (p)

    {

         p = p->next;

    }

     

    4.栈空/栈满/队空/队满

     

    while(栈非空)

    {

         出栈;

         操作出栈元素

    }

     

    5.指针大小比较

     

    while (pStart < pEnd)

    {

         pStart++;

    }

     

    6.数为正

     

    while (size--)

    {

    }

    do

    {

    }while(size--)

     

    7.反复循环直到条件成熟

     

    while(1)

    {

         if (something is true)

             break;

    }

     

    熟练各种循环语句的写法,为实现各种复杂的算法奠定了基础。因此,要在各种循环语句上下功夫,达到熟练书写,灵活运用的程度。


    7,递归的应用


    对于一些复杂的算法问题,还可以通过递归的思想来解决。有的问题,用传统的方法来解决,显得很复杂。这个时候,可以考虑是不是可以用递归来解决。因为用递归的思想解决问题,既简单,又清晰,往往让看似复杂的问题得到简单解决的可能。

     

    笔者曾经在面试微软的时候遇到考官考查了一道树的结点和它的兄弟之间的关系问题。开始我试着用队列结合树的遍历去解决这个问题,但是发现如果那样去解决会显得很麻烦,最后能否行得通也还是一个问题。而当时面试官也提醒我,一旦确定了思路,就不能再改变。于是我发现原来的想法显得很复杂,还有可能陷入死胡同。

     

    于是我决定放弃原来的思路,重新分析问题。经过我的重新分析,结合以往的经验,对于树的问题,几乎都可以考虑用递归的方法去实现,笔者按照递归的方法,首先分析了这个问题最简单的情况(即递归的出口),然后再对复杂的情况利用递归方法调用它自身。思路越来越清晰,我便开始动手写在纸上写起代码来。没过多久,代码就完成了,并交给了面试官。面试官看完代码后,很满意的点点头。问题最终得到圆满的解决。

     

    题目:用一条语句,不声明临时变量,实现strlen来计算一个字符串的长度。

    如strlen(“hello world”)=11

    size_t  strlen (const char * str )//常规方法

    {

            const char *eos = str;

            while( *eos++ ) ;

            return( eos - str - 1 );

    }

     

    size_t strlen(const char *str)//递归方法

    {

           return (str==NULL || *str==’\0’)?0:1+strlen(str+1);

    }

     

     

    题目:将一个字符串逆置。

    比如:”hello world”-->”dlrow olleh”

    void reverse_str(char* str, unsigned int len)//常规方法

    {

           if (NULL == str)

           {

                  return;

           }

           char *p1=str;

           char *p2=str+len-1;

           while(p1<p2)

           {

                  char c = *p1;

                  *p1 = *p2;

                  *p2 = c;

                  p1++;

                  p2--;

           }

    }

     

    void reverse_str(char *str, size_t len)//递归方法

    {

           if(len==0 || len==1 || str == NULL || *str=='\0')

           {

                  return;

           }

     

           char tmp = str[0];

           str[0]=str[len-1];

           str[len-1]=tmp;

     

           reverse_str(str+1, len-2);

     

    }

    递归算法的关键是找到递归的出口和递归公式。

    8,2个指针跑步


    2个指针跑步法,是麦洛克菲在算法教学过程中总结的一个很好的编程方法。就是在算法实现过程中,我们可以定义2个指针,一前一后,或者相向而行,同时遍历对应的数据结构(如数组,链表,字符串等),在遍历过程中解决对应的问题。在大量的名企面试题中,都可以使用该方法来解决并降低算法的复杂度。下面的例子详细的描述了这个方法的使用方法:

    题目1:计算一个链表的中间节点。

     

    思路:定义2个指针,一个跑2步,一个跑1步,当跑2步的到链表终点,跑1步的正好到达中间结点

    node * find_list_middle_node(node * list)

    {

        if(list == NULL || list->next == NULL)

        {

               return list;

        }

        node *p1 = list;

        node *p2 = list;

        while(p1&&p2&&p2->next)

        {

               p1=p1->next;

            p2=p2->next->next;

        }

        if(p2->next==NULL || p2==NULL)

           return p1;

    }

     

    题目2:判断一个单向链表是否存在循环。

     

    思路:定义2个指针,一个指针跑一步,一个指针跑2步;如果2个指针相遇,就存在循环,否则不存在循环。

    int find_loop(node *head)

    {

           node *p = NULL;

           node *q = NULL;

           if (head == NULL)

                  return 0;

       

           p = head;

           q = head->next;

           while (p!=NULL &&

                   q!=NULL&&q->next!=NULL&&p!=q)

        {

                  p = p->next;

                  q = q->next->next

           }

           if (p==q)

                  return 1;

           else

                  return 0;

    }

     

    题目3:从一个字符串中删除某一个特定的字符。

    如:”hello world”,’o’-->”hell wrld”

    思路:定义2个指针,一个是读指针,一个是写指针。读指针从头到尾扫描字符串,遇到不需要删除的字符,传递给写指针保存对应的字符,如果遇到要删除的字符直接忽略。

    char* del_char(char *str,char ch)

    {

            char *p1=str,*p2=str;

            if(NULL==str)

            {

                    return NULL;

            }

            while(*p2!='\0')

            {

                    if(*p2!=ch)

                    {

                            *p1++=*p2++;

                    }

                    else

                    {

                            p2++;

                    }

            }

            *p1='\0';

            return str;

    }

    思考题目1:将一个字符串按照单词顺序逆置,如hello this world-->world this hello

    思考题目2:将一个IP地址字符串转化为32位整数。如255.255.255.255-->0xffffffff

    思考题3:找出一个单向非循环链表中,倒数第M个结点


    9. Hash算法


    Hash算法一般是用一个hash数组来记录一个key对应的有无或者统计对应的个数,用key作为hash数组的下标,而下标对应的值用来表示该key的存在与否以及统计对应的个数。

    例1:请编写一个高效率的函数来找出字符串中的第一个无重复字符。例如,"total"中的第一个无重复字符上一"o"

    char find_first_single_char(const char *str)

    {

         int tmp[256]={0};//hash数组

         char *s= (char *)str;

         while(*s!='\0')

         {

              tmp[*s]++;

              s++;

         }

         s=(char*)str;

         while(*s!='\0')

         {

              if(tmp[*s]==1)

              {

                   return *s;

              }

              s++;

         }

         return '\0';

    }
    例2:找出一系列整数(都小于65536)中存在的重复数字。

    #define  MAXMUM   65536

    void find_repeated_number(int a[], in n)

    {

         int tmp[MAXMUM];//hash数组

         int i;

     

         for (i = 0; i < MAXMUM; i++)

         {

              tmp[i] = 0;

         }

         for (i = 0; i < n; i ++)

         {

              tmp[a[i]]++;

         }

         for (i = 0; i < MAXMUM; i++)

         {

              if (tmp[i]>1)

                   printf(“%d:%d”, i, tmp[i]);

         }

    }


    展开全文
  • 常见的算法设计方法

    千次阅读 2019-08-03 09:43:53
    然而,作为探寻问题求解思路的基本思想和方法,对于任何算法设计都是有用的。 1 穷举法 穷举法亦称作枚举法。它的基本思想是,首先根据求解问题的部分条件确定答案的大致范围,即列举出解的所有可能的情况;然后在...
  • 五大算法设计思想

    万次阅读 多人点赞 2018-05-15 08:53:03
    分治法 概念: 将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 思想策略: 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解...
  • 算法设计与分析(第2版)屈婉玲 刘田 张立昂 王捍贫编著 第一章课后习题答案 图片:
  • 概述 本系列博文将会向大家... C#算法设计之知识储备 C#算法设计排序篇 C#算法设计排序篇之前言 C#算法设计排序篇之01-冒泡排序(附带动画演示程序) C#算法设计排序篇之02-快速排序(附带动画演示程序) ...
  • (王晓东算法设计与分析)答案及解析
  • 需要算法设计与分析屈婉玲课后习题答案,希望哪位大神帮帮忙!大恩不言谢
  • 算法设计与分析(屈婉玲)pdf

    千次阅读 2019-07-13 15:43:49
    下载地址:网盘下载算法设计与分析本教材为计算机科学技术专业核心课程“算法设计与分析”教材。《算法设计与分析》以算法设计技术和分析方法为主线来组织各知识单元,主要内容包括基础知识、分治策略、动态规划、...
  • ACM书籍推荐

    万次阅读 2010-05-27 20:06:00
    入门三本:《数据结构与算法》(傅清祥,王晓东编著,我所见过的最好的算法教材)程序设计导引及在线实践 作者: 李文新ACM程序设计培训教程 吴昊基础提高:算法艺术与信息学竞赛 第二版 刘汝佳算法设计与分析 ...
  • 程序员为什么要学算法

    万次阅读 多人点赞 2019-01-16 12:20:21
    “程序员必须会算法 ?” 程序员对算法通常怀有复杂情感,算法很重要是共识,但是否每个程序员都必须学算法是主要的分歧点。 很多人觉得像人工智能、数据搜索与挖掘这样高薪的工作才用得上算法,觉得算法深不可测。...
  • 算法设计与分析(第2版)屈婉玲 刘田 张立昂 王捍贫编著 第二章课后习题答案
  • 算法分析与基础 第三版 潘彦译

    千次阅读 2018-12-29 11:00:52
    百度网盘链接:https://pan.baidu.com/s/1wt5I-KBDf1tdCQwv5RdrMw 提取码:0ai7
  • 全球人工智能:专注为AI开发者提供全球最新AI技术动态和社群交流。用户来源包括:北大、清华、中科院、复旦、麻省理工、卡内基梅隆、斯坦福、...我们都知道对于软件而言,最为经典的定义就是程序=算法+数据结构,算...
  • #include using namespace std; typedef int Status; typedef int elemtype; #define OK 1 #define ERROR 0 typedef struct LNode { elemtype data; struct LNode *next;...void CreateList_L
1 2 3 4 5 ... 20
收藏数 962,362
精华内容 384,944
关键字:

算法设计