五种基本算法思想介绍
更新时间 2021-07-20 16:45:41    浏览 0   

TIP

本文主要是介绍 五种基本算法思想介绍 。

# 五种基本算法思想

# 1.穷举算法思想

穷 举 算 法 (ExhaustiveA ttack method)是 最 简 单 的 一 种 算 法 ,其依赖于计算机的强大计算能力来 穷 尽 每 一 种 可 能 的 情 况 ,从 而 达 到 求 解 问 题 的 目 的 。穷 举 算 法 效 率 并 不 高 ,但是适应于一 些没有明 显 规 律 可 循 的 场 合。

# 基本算法思想

穷举算法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下:

  • (1)对于一种可能的情况,计算其结果。
  • (2) 判断结果是否满足要求,如果不满足则执行第(1 ) 步来搜索下一个可能的情况;如果满足要求,则表示寻找到一个正确的答案。

【注意】在使用穷举算法时,需要明确问题的答案的范围,这样才可以在指定范围内搜索答案。指定范围之后,就可以使用循环语句和条件判断语句逐步验证候选答案的正确性,从而得到需要的正确答案。

# 经典例子《孙子算经》【鸡兔同笼问题】

今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何? (在一个笼子里关着若干只鸡和若干只兔,从上面数共有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;
}

输出:chickens=23 rabbits=12

# 2.递推算法思想

递推算法是非常常用的算法思想,在数学计算等场合有着广泛的应用。递推算法适合有明显公式规律的场合。

# 基本算法思想

递推算法是一种理性思维模式的代表,根据已有的数据和关系,逐步推导而得到结果。递推算法的执行过程如下:

  • (1) 根据已知结果和关系,求解中间结果。
  • (2)判定是否达到要求,如果没有达到,则继续根据已知结果和关系求解中间结果。如果满足要求,则表示寻找到一个正确的答案。

【注意】递推算法需要用户知道答案和问题之间的逻辑关系。在许多数学问题中,都有明确的计算公式可以遵循,因此可以采用递推算法来实现。

# 经典例子 斐波那契《算盘书》【兔子产仔问题】

如果一对两个月大的兔子以后每一个月都可以生一对小兔子,而一对新生的兔子出生两个月后才可以生小兔子。也就是说,1 月份出生,3 月份才可产仔。那么假定一年内没有产生兔子死亡事件,那 么 1年后共有多少对兔子呢?

【规律分析】

  • 第一个月:a(1)=1对兔子;
  • 第二个月:a(2)=1对兔子;
  • 第三个月:a(3)=1+1=2 对兔子;
  • 第四个月:a(4)=1+2=3 对兔子;
  • 第五个月:a(5)=2+3=5 对兔子;
  • ……
  • 第n个月:a(n)=a(n-1)+a(n-2)对兔子;
int Fibonacci(int n)
{
int tl,t2;
if (n==1||n==2)//第1、2个月都只有1对兔子
{
return 1;
}else{//采用递归
tl=Fibonacci(n-1);
t2=Fibonacci(n-2);
return tl+t2;//计算第n个月的兔子对数
}
}
int main()
{
   int n=12;
   printf("%d个月后兔子对数:%d\n",n,Fibonacci(n));
    return 0;
}

输出:12个月后兔子对数: 144

# 3.递归算法思想

递归算法是非常常用的算法思想。使用递归算法,往往可以简化代码编写,提高程序的可读性。但是,不合适的递归会导致程序的执行效率变低。

# 基本算法思想

  • 递归算法就是在程序中不断反复调用自身来达到求解问题的方法。这里的重点是调用自身,这就要求待求解的问题能够分解为相同问题的一个子问题。这样 ,通过多次递归调用,便可以完成求解。
  • 递归调用是一个函数在它的函数体内调用它自身的函数调用方式,这种函数也称为“递归函数”。在递归函数中,主调函数又是被调函数。执行递归函数将反复调用其自身,每调用一次就进入新的一层。 函数的递归调用分两种情况:直接递归和间接递归。 • 直接递归:即在函数中调用函数本身。 • 间接递归:即间接地调用一个函数,如出如func_a调 用 func_b, func_b 又调用func_a。间接递归用得不多。

【注意】编写递归函数时,必须使用if语句强制函数在未执行递归调用前返回。否则,在调用函数后,它永远不会返回,这是一个很容易犯的错误。

# 经典例子 【阶乘】

n!=n*(n-1)*(n-2)*……*2*11
long fact(int n){
if(n<=1)return 1;
else
    return n*fact(n-1);
}
int main()
{
   int n=11;
   printf("%d的阶乘是%d\n",n,fact(n));
    return 0;
}

输出:11的阶乘 39916800

# 4.分治算法思想

分治算法是一种化繁为简的算法思想。分治算法往往应用于计算步骤比较复杂的问题,通过将问题简化而逐步得到结果。

# 基本算法思想

分治算法的基本思想是将一个计算复杂的问题分为规模较小,计算简单的小问题求解,然后综合各个小问题,得到最终问题的答案。分治算法的执行过程如下:

  • (1)对于一个规模为N 的问题,若该问题可以容易地解决(比如说规模>^较小),则直接解决,否则执行下面的步骤。
  • (2)将该问题分解为” 个规模较小的子问题,这些子问题互相独立,并且原问题形式相同。
  • (3)递归地解子问题。
  • (4)然后,将各子问题的解合并得到原问题的解。

【注意】使用分治算法需要待求解问题能够化简为若干个小规模的相同问题,通过逐步划分,达到一个易于求解的阶段而直接进行求解。然后,程序中可以使用递归算法来进行求解。

# 经典例子 【寻找假币问题】

一个袋子里有30个硬币,其中一枚是假币,并且假币和真币一模- 样,肉眼很难分辨,目前只知道假币比真币重量轻一点。请问如何区分出假币?

int falseCoin(int coin[],int low,int high){
int i,sum1,sum2,sum3;
int re;
sum1=sum2=sum3=0;
//若只有两个硬币
if(low+1==high){
    if(coin[low]<coin[high]){//第一个硬币是假币
    re=low+1;
    return re;
}else{//第二个硬币是假币
re=high+1;
return re;
}
}
//硬币个数大于2
if((high-low+1)%2==0){//偶数个硬币
    for(i=low;i<=low+(high-low)/2;i++){//前半段重量
        sum1=sum1+coin[i];
    }
    for(i=low+(high-low)/2+1;i<=high;i++){//后半段重量
      sum2=sum2+coin[i];
    }
    if(sum1>sum2){//后半段轻,假币在后半段
        re=falseCoin(coin,low+(high-low)/2+1,high);
    return re;
    }else if(sum1<sum2){//前半段轻,假币在前半段
     re=falseCoin(coin,low,low+(high-low)/2);
    return re;
    }
}else{//奇数个硬币
for(i=low;i<=low+(high-low)/2-1;i++){//前半段重量
        sum1=sum1+coin[i];
    }
    for(i=low+(high-low)/2+1;i<=high;i++){//后半段重量
      sum2=sum2+coin[i];
    }
    sum3=coin[low+(high-low)/2];
    if(sum1>sum2){//后半段轻,假币在后半段
        re=falseCoin(coin,low+(high-low)/2+1,high);
    return re;
    }else if(sum1<sum2){//前半段轻,假币在前半段
     re=falseCoin(coin,low,low+(high-low)/2-1);
    return re;
    }
    if(sum1+sum3==sum2+sum3){//前半段+中间硬币和后半段+中间硬币重量相等,说明中间硬币是假币
        re=low+(high-low)/2+1;
        return  re;
    }

}
}
int main()
{
   int n=11,i;
   int a[n];
   for(i=0;i<n;i++){
    a[i]=2;
   }
   a[7]=1;//设置第八个为假币
  printf("假币是第%d个\n", falseCoin(a,0,n-1));
    return 0;
}

输出:假币是第8个

# 5.概率算法思想

概率算法依照概率统计的思路来求解问题,往往不能得到问题的精确解,但却在数值计算领域得到了广泛的应用。因为很多数学问题,往往没有或者很难计算解析解,这时便需要通过数值计算来求解近似值。

# 基本算法思想

概率算法执行的基本过程如下:

  • (1)将问题转化为相应的几何图形S, S 的面积是容易计算的,问题的结果往往对应几何图形中某一部分S1 的面积。
  • (2)然后,向几何图形中随机撒点。
  • (3)统计几何图形S 和 S1 中的点数。根 据 S 的面积和S1 面积的关系以及各图形中的点数来计算得到结果。
  • (4) 判断上述结果是否在需要的精度之内,如果未达到精度则执行步骤(2)。如果达到精度,则输出近似结果。

概率算法大致分为如下4 种形式。

  • 数值概率算法。
  • 蒙 特 卡 罗 (MonteCarlo)算法。
  • 拉 斯 维 加 斯 (Las Vegas)算法。
  • 舍 伍 德 (Sherwood)算法。

# 经典例子【蒙特卡罗PI概率算法问题】

在边长为1的正方形内,以1为半径画一个1/4圆。落入院内的概率为PI/4?

算法思想:在某面积范围内撒点足够多,落在固定区域的点的概率就会将近结果。

关键:均匀撒点、区域判断

double MontePI(int n){
double PI;
double x,y;
int i,sum;
sum=0;
srand(time(NULL));
for(i=1;i<n;i++){
    x=(double)rand()/RAND_MAX;//在0-1之间产生一个随机数x
     y=(double)rand()/RAND_MAX;//在0-1之间产生一个随机数y
    if((x*x+y*y)<=1){//判断点是否在圆内
        sum++;//计数
    }
}
    PI=4.0*sum/n;//计算PI
    return PI;
}

int main()
{
   int n=500000;
   double PI;

  printf("蒙特卡罗概率PI=%f\n", MontePI(n));
    return 0;
}

输出:蒙特卡罗概率PI=3.139152

# 参考文章

  • https://blog.csdn.net/qq_25740691/article/details/78894177
更新时间: 2021-07-20 16:45:41
  0
手机看
公众号
讨论
左栏
全屏
上一篇
下一篇
扫一扫 手机阅读
可分享给好友和朋友圈