数值概率算法—计算定积分

在解决实际问题时，有时会用到所谓的概率算法。概率算法允许在执行过程中随机选择下一步的计算步骤，因此使用概率算法有时会大大降低复杂度，提高算法的效率，但有时候可能会得不到问题的全部答案。【1】

一、概率算法：

一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类:数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。【2】

二、计算定积分：

http://s2/mw690/002tibr0zy75mfwk7Che1&690

分析：

http://s9/mw690/002tibr0zy75mfA3bzaf8&690
http://s16/mw690/002tibr0zy75mfD9I87ef&690

 （2）使用sand()与srand()产生随机数，用系统时间作为产生随机数的种子，使的每次产生的随机数不一样。rand()0 意思是产生100内的随机数，rand()0/100.0 意思除以100.0，可得到双精度[0,1]内的随机数。具体SAND函数与SRAND函数的用法请参考：http://www.cnblogs.com/lenient/articles/1565376.html 博客园

(3)time函数time_实际就是长整形long int；用time_t表示更能准确表达所要定义的变量是什么，一看就知道是与时间有关的。具体time函数的用法请参考：

http://blog.csdn.net/wangluojisuan/article/details/7045592/ C博客

 三、程序实现：

#include

#include

#include

#include

double Darts(int n)

{

         double x,y;

         time_t t;

         int i,count = 0;

         srand((unsigned)time(&t));

         for(i = 0;i

           {

                x = rand()0/100.0;

                y = rand()0/100.0;

                if(y<=1 - pow(x,2))

                  count++;

           }

           return (double)count/(double)n;//强制转型

}

int main()

{

         int n,dartnum;

         double result;

         //printf("please input the accuracy:\n");

         //scanf("%d",&n);

         for(n = 10000;n

         //printf("the result is about\n");

         printf("dartnum = %d;result = %f\n",n,Darts(n));

}

四、运行结果：

第一次运行

http://s15/mw690/002tibr0zy75mfJS4ncee&690

第二次运行

http://s2/mw690/002tibr0zy75mfMrdDP21&690

五、结果分析：

http://s7/mw690/002tibr0zy75mfRvCXs76&690

①分析第一次的运行结果可以看出随着投点次数的增加，也就是运行结果的准确度增加；

②比较两次运行的情况，可以得到用系统时间作为产生随机数的种子，每次产生的随机数都不一样，导致最终结果不一样。

六、参考资料：

【1】《妙趣横生的算法-C语言的实现》  杨峰编著  清华大学出版社

【2】http://baike.baidu.com/link?url=IBVAOvuP7NHB3JOyFx5ZWYu7x9DXYrWEz80tpgUa_pnaIkOXRDqvqHEP_oY70h2bV0pllKFJKktH95CBF3XpEq 概率算法 百度百科

【3】《求解定积分的概率算法》 胡能发，邓永发  韩山师范学院 计算机工程与设计第28卷 第10期