C语言五大经典算法

分治法

 

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治

之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再

把子问题分成更小的子问题??直到最后子问题可以简单的直接求解，原

问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序

算法

(

快速排序

，归并排序

)

，傅立叶变换

(

快速傅立叶变换

)?? 

 

 

分治法简介

 

 

 

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。

问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，

对于

n

个元素的排序问题，当

n=1

时，不需任何计算。

  

 

 

n=2

时，

只要作一次比较即可排好序。

n=3

时只要作

3

次比较即可，

?。

  

 

 

而当

n

较大时，问题就不那么容易处理了。要想直接解决一个规模较

大的问题，有时是相当困难的。

  

 

 

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规

模较小的相同问题，以便各个击破，分而治之。

  

 

 

分治策略是：

对于一个规模为

n

的问题，

若该问题可以容易地解决

（比

如说规模

n

较小）则直接解决，否则将其分解为

k

个规模较小的子问题，

这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将

各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

  

 

 

如果原问题可分割成

k

个子问题，1<k≤n ，且这些子问题都可解并可

利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分

治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了

方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一

致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自

然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算

法设计之中，并由此产生许多高效算法。

  

 

 

分治法所能解决的问题一般具有以下几个特征：

  

 

 

1) 

该问题的规模缩小到一定的程度就可以容易地解决

  

 

 

2) 

该问题可以分解为若干个规模较小的相同问题，

即该问题具有最优

子结构性质。

  

 

 

3) 

利用该问题分解出的子问题的解可以合并为该问题的解；

  

 

 

4) 

该问题所分解出的各个子问题是相互独立的，

即子问题之间不包含

公共的子子问题。

  

 

 

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复

杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提

它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具

备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或

动态规划法

。第四条特征涉及到分治法的效率，如果各子问题是不独立的

则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用

分治法，但一般用动态规划法较好。

  

 

分治法的基本步骤

 

 

 

分治法在每一层递归上都有三个步骤：

  

 

 

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相

同的子问题；

  

 

 

解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个

子问题；

合并：将各个子问题的解合并为原问题的解。

 二、贪心算法
  （三）算法描述

 

 

 

贪心算法的基本思想

 

 

 

该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定

是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程

看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定

的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为

更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。

 

 

 

贪心算法的适用的问题

 

 

 

贪心算法适用的问题必须满足两个属性：

 

 

 

（１）

  

贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出

的选择，但不能依赖于以后的选择。

 

 

 

（２）

  

最优子结构：问题的整体最优解包含着它的子问题的最优解。

 

 

 

贪心算法的基本步骤

 

 

 

（１）

  

分解：将原问题分解为若干相互独立的阶段。
 

（２）

  

解决：对于每一个阶段求局部的最优解。

 

 

 

（３）

  

合并：将各个阶段的解合并为原问题的解。

 

 

 

[

问题分析

]

 

 

 

由于汽车是由始向终点方向开的

,

我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到

达终点又可以使我们加油次数最少。

 

 

 

提出问题是解决的开始

.

为了着手解决遇到的困难

,

取得最优方案。我们可以假设不到万不得已我们不

加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却

每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为

原问题的解得到我们原问题的求解。

 

 

 

加油站贪心算法设计（

C

）：

 

 

 

include<math.h> 

 

 

include<studio.h> 

 

 

int add(int b[ ],int m,int n) 

 

 

{ 

//

求一个从

m

到

n

的数列的和

 

 

 

int sb; 

 

 

for(int i=m;i<n;i++) sb+=b[i]; 

 

 

return sb; 

 

 

} 

 

 

int Tanxin(int a[n], int N) 

//a[n]

表示加油站的个数，

N

为加满油能行驶的最远距离

 

 

 

{ 

 

 

int b[n]; 

//

若在

a[i]

加油站加油，则

b[i]

为

1

，否则为

0 

 

 

int m=0; 

 

 

if(a[i]>N) return ERROR; 

//

如果某相邻的两个加油站间的距离大于

N

，则不能到达终点

 

 

 

if(add(a[i], 0, n)<N) 

 

 

{ //

如果这段距离小于

N

，则不需要加油

 

 

 

b[i]=0; 

 

 

return add(b[i],0,n); 

 

 

} 

 

 

if(a[i]==a[j]&&a[i]==N) 

 

 

{ //

如果每相邻的两个加油站间的距离都是

N

，则每个加油站都需要加油

 

 

 

b[i]=1; 

 

 

return add(b[i],0,n); 

 

 

} 

 

 

if(a[i]==a[j]&&a[i]<N) 

 

 

{ //

如果每相邻的两个加油站间的距离相等且都小于

N 

 

 

if( add(a[i],m,k) < N && add(a[i],m,k+1) > N ) 

 

 

{ 

 

 

b[k]=1; 

 

 

m+=k; 









 

 

} 

 

 

return add(b[i],0,n); 

 

 

} 

 

 

if(a[i]!=a[j]) 

 

 

{ //

如果每相邻的两个加油站间的距离不相等且都小于

N 

 

 

if( add(a[i],m,k) < N && add(a[i],m,k+1) > N ) 

 

 

{ 

 

 

b[k]=1; 

 

 

m+=k; 

 

 

} 

 

 

return add(b[i],0,n); 

 

 

} 

 

 

viod main( ) 

 

 

{ 

 

 

int a[ ]; 

 

 

scanf("%d",a); 

 

 

scanf("/n"); 

 

 

scanf("/d",&N); 

 

 

Tanxin(a[ ],0,n); 

 

 

} 

 

 

贪心算法正确性证明：

 

 

 

贪心选择性质

 

 

 

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的

一个整体最优解。该题设在加满油后可行驶的

N

千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比

Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，因为

m+N<n+N

，即在

B

点加

油可行驶的路程比在

A

点加油可行驶的路程要长

n-m

千米，

所以只要终点不在

B

、

C

之间且在

C

的右边的话，

根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少

满足贪心选择性质。

 3.、回溯算法
 回溯（backtracking）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。
     下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图(迷宫问题)或树(N皇后问题)。
      一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。

回溯方法的步骤如下：
     1) 定义一个解空间，它包含问题的解。
     2) 用适于搜索的方式组织该空间。
     3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。
 回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。
4、分置界限算法
   对比回溯法
1、回溯法的求解目标是找出解空间中满足约束条件的所有解，想必之下，分支限界法的求解目标则是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
2、另外还有一个非常大的不同点就是，回溯法以深度优先的方式搜索解空间，而分支界限法则以广度优先的方式或以最小耗费优先的方式搜索解空间。

分支限界法的搜索策略

在当前节点（扩展节点）处，先生成其所有的儿子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。

选择方法

1.队列式（FIFO）分支限界法

队列式分支限界法将活节点表组织成一个队列，并将队列的先进先出原则选取下一个节点为当前扩展节点。

2.优先队列式分支限界法

优先队列式分支限界法将活节点表组织成一个优先队列，并将优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如果选择这种选择方式，往往将数据排成最大堆或者最小堆来实现。

5、动态规划算法
   一、基本概念

    动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

二、基本思想与策略

    基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

    由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

    与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

 

--------------------------------------------------------------------------------


三、适用的情况

能采用动态规划求解的问题的一般要具有3个性质：

    (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

    (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

   （3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

 

--------------------------------------------------------------------------------

四、求解的基本步骤

     动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一 条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

    初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

                      图1 动态规划决策过程示意图

    (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

    (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

    (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

    (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

    一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

实际应用中可以按以下几个简化的步骤进行设计：

    （1）分析最优解的性质，并刻画其结构特征。

    （2）递归的定义最优解。

    （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值

    （4）根据计算最优值时得到的信息，构造问题的最优解
int fib(int n)
{
    if(n==0||n==1)
        return 1;
    return fib(n-1)+fib(n-2);
}