动力节点旗下在线教育品牌  |  咨询热线:400-8080-105 学Java全栈,上蛙课网
首页 > 文章

基本算法思想总结

07-31 16:37 198浏览
举报 T字号
  • 大字
  • 中字
  • 小字

无论是在大学还是培训机构,无论是在java还是在C,算法始终贯彻其中,扮演着是不容忽视的角色。而算法的精髓就在于其思想,或者说是解题思路,一个清晰的解题思路,是解决问题的致胜法宝。本文就来总结一下一些基本的算法思想

首先,我们抛出心中的疑问:算法是什么?算法,即是按照一定的步骤,一步步去解决某个问题,解决问题的方法步骤称之为算法,例如数学中我们学过的做一个运算,解一个方程,等等,都需要有一个清晰的思路,一步步地去完成。当然这只是我们学习中的例子,生活中,我们结算工资也是要按一定的步骤,完成一个闭合的运算,得出结果。所以说算法是无处不在的。下面我们来介绍一下基本的算法思想:

  • 分治法

分治,分而治之。即将一个难以直接解决的大问题,划分成一些规模较小的可以解决的子问题,以便各个击破,分而治之。

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

1、平衡子问题:就是是各个子问题的规模大致相同

2、独立子问题:各子问题之间相互独立,如果不独立,还需要分解子问题。

上图很生动地再现了分治算法的化繁为简的思想,分治算法的思想往往应用于解决和计算步骤比较复杂的问题,通过将问题简化而逐步得到结果。

  • 动态规划法

动态规划法和分治法类似,它也是将大问题分解成子问题求解,不同的是,如果分解的子问题有很多是相同的,采用分治法相同的子问题会求解多次,是不是很影响效率;动态规划法呢,它会保存已解决的子问题的答案,再有相同的子问题直接用保存的答案就行了,节省了很多计算时间。

通过二叉树,我们注意到,F(n)是通过计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的,所以,可以设计一张表填入n+1个F(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

这些基本算法思想也是数据结构当中的重要组成部分,不仅仅为我们探究数据结构提供了清晰的思路,也为计算机语言的发展贡献了自己的力量。

0人推荐
共同学习,写下你的评论
0条评论
会java的猫
程序员会java的猫

5篇文章贡献21503字

作者相关文章更多>

推荐相关文章更多>

Java数据结构

HelloWorld10-31 08:24

浅谈MySQL中SQL优化的常用方法

军哥08-12 23:29

五分钟读懂UML类图

江湖人称小李白12-10 10:41

MyBatis开发框架的四大核心

IT逐梦者08-17 21:43

一次搞定continue,break和return

HelloWorld11-06 11:19

发评论

举报

0/150

取消