ACM学习<二>

穷举算法思想：

一句话：就是从所有可能的情况，搜索出正确的答案。

步骤：

1.对于一种可能的情况，计算其结果。

2.判断结果是否满足，YES计算下一个，no继续步骤1，然后判断下个可能的情况。

实例：

孙子算经--鸡兔同笼：头35，脚94，几鸡几兔？

#include <iostream>                                                       //头文件

using namespace std;

int qiongju(int head, int foot , int *chicken,int *rabbit)     //穷举算法

{

     int re,i,j;

     re=;

     for(i=;i<=head;i++)                                             //循环

     {

          j=head-i;

          if(i*+j*==foot)                                             //判断，找到答案

          {

               re=;

               *chicken=i;

               *rabbit=j;

          }

     }

     return re;

}

int main()                                                                 //主函数

{

     int chicken,rabbit,head,foot;

     int re;

     cout<<"鸡兔同笼问题："<<endl;

     cout<<"输入头数：";

     cin >>head;

     cout<<"输入脚数：";

     cin >>foot;

     re =qiongju(head,foot,&chicken,&rabbit);                    //& 跟 qiongju（）里面的 * 是不是表示  引用？？

     if(re==)

     {

          cout<<"鸡有："<<chicken<<"只, 兔有"<<rabbit<<"只。" <<endl;

     }else

     {

          cout<<"无法求解！"<<endl;

     }

}

递推思想：

1.根据已知的结果和关系，求解中间的结果。

2.判断是否达到要求，如果没有达到，则继续根据已知的结果和关系求解中间结果。如果有的话，则表示寻找到一个正确的结果。

实例：斐波那契数列———兔子产子

#include <iostream>

using namespace std;

int fibonacci(int n)

{

     if(n== || n==)

     {

          return ;

     }

     else

     {

          return fibonacci(n-)+fibonacci(n-);//递归调用

     }

}

int main()

{

     int n,num;

     cout<<"斐波那契数列——兔子产子："<<endl;

     cout<<"请输入时间：";

     cin >> n;

     num=fibonacci(n);

     cout<<"经过"<<n<<"年，可以产子"<<num<<"对"<<endl;

}

递归思想：

递归算法，就是在程序中不断反复调用他自身的函数调用方式，这种函数也称为递归函数。

函数的递归调用用分两种情况：直接递归和间接递归。

直接递归：即在函数中调用函数本身。

间接递归：即间接地调用一个函数，如func_a调用了func_b，func_b又调用了func_a；间接递归用的不多。

优点:代码间接清晰，可读性更好。用递归比循环表死简洁精炼。特别人工智能，八皇后问题，汉诺塔等适合用递归

缺点:没有明显的减少代码规模和节省内存空间。递归比非递归运行速度要慢一些。附加函数增加了时间的开销（要执行一系列的压栈出栈）。二者递归层次太深还可能导致堆栈溢出。

实例：经典的阶乘

#include <iostream>

using namespace std;

long fact(int n); //函数的声明

int main()

{

     int i;

     cout<<"请输入要求阶乘的一个整数：";

     cin >>i;

     cout<<i<<"的阶乘结果为"<<fact(i)<<endl;

}

long fact(int n)

{

     if(n<=)

          return ;

     else

          return n*fact(n-);

}

分治算法思想：

基本思路：将一个计算复杂的问题分为规模较小，计算简单的小问题求解，然后综合各个小问题，得到最终问题的答案。

基本过程：

1.对于一个规模为N的问题若该问题可以容易的解决，那就直接解决。否则执行下面的步骤。

2.将该问题分解为M个规模较小的子问题，这些子问题五项多里，并且与原问题形式相同。

3.递归的解子问题。

4.然后，将各子问题的解合并得到原问题的解。

例子:

问题：一个袋子30个硬币，一个假的，假的较轻。如何分辨假币？

步骤：

1.首先为每个币编号，分成两份，放在天平上。

2.因为假币在轻的一方，继续将轻的重复上面的做法。

3.直到剩下2个，直接用天平找出。

#include <iostream>

using namespace std;

#define MAXNUM 4

int FalseCoin(int coin[],int low,int high)

{

     int i,sum1,sum2,sum3;

     int re;

     sum1=sum2=sum3=;

     if(low+==high)//最后一堆是两个的时候

     {

          if(coin[low]<coin[high])

          {

               re=low+;

               return re;

          }

          else

          {

               re=high+;

               return re;

          }

     }

     if((high-low+)%==)//n为偶数

     {

          for(i=low;i<=low+(high-low)/;i++)

          {

               sum1+=coin[i];//前半段和

          }

          for(i=low+(high-low)/+;i<=high;i++)

          {

               sum2+=coin[i];//后半段和

          }

          if(sum1>sum2)

          {

               re=FalseCoin(coin,low+(high-low)/+,high);

               return re;

          }

          else if(sum1<sum2)

          {

               re=FalseCoin(coin,low,low+(high-low)/);

               return re;

          }

          else

          {

          }

     }

     else    //n为奇数

     {

          for(i=low;i<=low+(high-low)/-;i++)

          {

               sum1+=coin[i];//前半段和

          }

          for(i=low+(high-low)/+;i<=high;i++)

          {

               sum2+=coin[i];//后半段和

          }

          sum3=coin[low+(high-low)/];

          if(sum1>sum2)

          {

               re=FalseCoin(coin,low+(high-low)/+,high);

               return re;

          }

          else if(sum1<sum2)

          {

               re=FalseCoin(coin,low,low+(high-low)/-);

               return re;

          }

          else

          {

          }

          if(sum1+sum3==sum2+sum3)

          {

               re=low+(high-low)/+;

               return re;

          }

     }

}

int main()

{

      int coin[MAXNUM];

       int i,n;

       int place;

       cout<<"分治法求假币问题！"<<endl;

       cout<<"请输入币的个数:";

      cin >>n;

      cout<<"请输入币真假的重量:";

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

      {

          cin >> coin[i];

           //scanf("%d",&coin[i]);

      }

      place =FalseCoin(coin,,n-);

      cout<<"位子实在上述的第"<<place<<"个是假的"<<endl;

}

概率算法思想：

1.将问题转化为相应的几何图形S，S的面积是容易计算的。问题往往是对应的集合图形的S1的面积，

2.然后向几何随机撒点。

3.统计S S1的点数，根据关系得出结果。

4.判断是否达到精度，否执行2步骤，是结束

4种形式：数值概率算法，蒙特卡罗算法，拉斯维加斯算法，舍伍德算法。

蒙特卡罗概率算法计算PI:

#include <iostream>

#include <time.h>

using namespace std;

double MontePI(int n)

{

     double PI;

     double x,y;

     int i , sum;

     sum = ;

     srand(time(NULL));

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

     {

          x=(double)rand()/RAND_MAX;

          y=(double)rand()/RAND_MAX;

          if(x*x+y*y<=)

               sum++;

     }

     PI=4.0*sum/n;

     return PI;

}

int main()

{

     int n;

     double PI;

     cout<<"蒙特卡罗概率算法 计算PI"<<endl;

     cout<<"输入撒点的数量：";

     cin >> n;

     PI=MontePI(n);

     cout<<PI<<endl;

}

巴特西

ACM学习<二>

最新文章

热门文章