基本算法思想总结

无论是在大学还是培训机构，无论是在java还是在C，算法始终贯彻其中，起着不可忽视的作用。算法的本质在于它的思想，或解决问题的思想。一个清晰的解决问题的想法是解决问题的法宝。本文将总结一些算法的基本思想。

首先，我们提出了我们心中的问题：什么是算法？算法是按照一定的步骤一步一步地解决问题。解决问题的方法和步骤称为算法。例如，我们在数学中学到的操作、解决方程等都需要有一个清晰的想法，一步一步地完成。当然，这只是我们学习中的一个例子。在我们的生活中，我们还应该按照一定的步骤完成一个封闭的计算，并得到结果。所以算法无处不在。让我们介绍一下基本算法思想：

• 分治法

分治，分而治之。即将一个难以直接解决的大问题，分为一些小的可以解决的子问题，以便每一个都被打破，分而治之。

子问题的两个规则需要注意：

1、平衡子问题：每个子问题的规模大致相同

2、独立子问题：各子问题相互独立，如果不独立，还需要分解子问题。

上图生动地再现了分治算法的复杂性和简化性。分治算法的思想通常用于解决和计算步骤复杂的问题，并通过简化问题逐渐得到结果。

• 动态规划法

动态规划法与分治法相似。它还将大问题分解为子问题。不同的是，如果分解的许多子问题是相同的，分治法中使用相同的子问题会多次解决，这是否会影响效率；在动态规划法中，它将保存已解决的子问题的答案，然后使用保存的答案直接使用相同的子问题，节省大量的计算时间。

通过二叉树，我们注意到，F(n)它的两个重叠子问题是通过计算出来的 F(n-1)和F(n-2)表达的形式，所以可以设计一张表填充n+1F(n)值。通过下表可以发现，后一个数等于前两个数的和。(这就是著名的斐波那契数)

因此，动态规划法的运用可以概括为一个问题的性质：最佳子结构和重叠子问题。

• 贪心算法

贪婪算法的基本思想是找出整个小局部的最优解，并将所有这些局部最优解结合起来，形成整体最优解。因此，能够使用贪婪算法的问题必须满足以下两个性质：

1.通过局部最优解可以找到整体最优解；

2.一个整体可以分为多个部分，这些部分可以找到最佳解决方案。贪婪算法中的两个典型问题是活动安排和背包。

让我们举一个贴近我们生活的例子。现实中，我们用纸币现金在超市购买价值X元的货物至少要用多少张钞票？解决这个问题的想法很清楚。每一张大纸币都可以被几张小纸币所取代，所以如果你能使用大纸币，就不要使用小纸币，也就是说，尽量使用大纸币。代码实现如下：

#include

int main (){

const int RMB[]={100,50,20,10,5,1};

const int NUM=6; //6种金额

int x=628; //假设要付的钱数是628

int count=0; /////最终支付的货币张数

for(int i=0;i

int use=x/RMB[i]; ///需要RMB[i]的use张

count+=use; ///总增加use张张总额

x=x-RMB[i]*use; ///未付金额

}

printf("总共需要%d张"，count);

return 0;

}

很容易得出结果：i=11，即6张100元，一张20元，一张5元，三张1元

• 回溯算法

回溯法是一种探索和解决问题的方法。通过对问题的总结和分析，我们可以找到解决问题的线索，并沿着这条线索向前测试。如果测试成功，我们将得到解决方案；如果测试失败，逐渐撤退，改变其他路线，然后向前测试。

回溯法在解决问题的空间树中，根据深度优先策略，从根点搜索解决空间树。当算法搜索到解空间树的任何结点时，首先判断结点是否包含问题解。如果肯定不包括在内，跳过搜索以结点为根的子树，逐层追溯到祖先的结点；否则，进入子树，继续按照深度优先搜索策略进行搜索。回溯算法的思想是以深度优先的方式系统地搜索问题的解决方案，适用于解决组合数较大的问题。

用回溯法解决问题的步骤：

1.针对给出的问题，定义解决问题的空间。

2.确定易于搜索的解空间结构。

3.以深度优先的方式搜索解空间，并在搜索过程中使用剪枝函数避免无效搜索；如果回溯法对解空间进行深度优先搜索，则采用递归法实现回溯法。

• 枚举法

枚举算法可以说是这五种算法中最简单的一种。它依靠计算机强大的计算能力来耗尽每一种可能的情况，从而达到解决问题的目的。因此，枚举算法的效率相对较低，但它适用于一些没有明显规则可循的问题。

使用穷举算法时，需要明确问题的答案范围，以便在指定范围内搜索答案。指定范围后，循环句和条件判断句可以逐步验证候选答案的正确性，从而获得所需的正确答案。

我们可以通过经典的鸡兔同笼问题(一个笼子里关着几只鸡和几只兔子，从上面共有几只35个头；下面有94只脚。问笼子里鸡兔的数量是多少？)一窥枚举算法思想的全貌:

int chickenRabbit(int head,int foot,int *c,int *r){

int i,j;

int tag=0;//标志是否解决

for(i=0;i<=head;i++){//鸡数穷举

j=head-i;//兔子的数量

if(i*2+j*4==foot)判断{///是否符合条件

tag=1;

*c=i;

*r=j;

}

}

return tag;

}

int main()

{

int c,r;

if(chickenRabbit(35,94,&c,&r)==(1){///如果有解输出

printf("chickens=%d,rabbits=%d\n",c,r);

}else{//如果没有解决办法

printf("无解\n");

}

return 0;

}

该程序运行后，凭借计算机强大的计算能力，立即得出结果：

Chicken=23，Rabbit=12

这些基本算法思想也是如此数据结构它的重要组成部分不仅为我们探索数据结构提供了清晰的思路，也为计算机语言的发展做出了贡献。