本章内容來自《妙趣橫生的算法》 一書中。

在解決實際問題時，有時會用到所謂的概率算法。概率算法允許在執行過程中随機地選擇下一步的計算步驟，因此使用概率算法有時會大大地提高算法的效率，但有時也可能得不到問題的全部答案。

概率算法大緻分為四類：數值概率算法，蒙特卡洛(Monte Carlo)算法，拉斯維加斯(Las Vegas)算法，和舍伍德(Sherwood)算法。這裡隻介紹最為基礎的數值概率算法。

數值概率算法常應用于解決數值計算的問題。應用數值概率算法往往隻能得到問題的近似解，并且該近似解的精度一般随着計算時間的增加而不斷提高。因為在一些數值問題中，不可能也沒有必要計算出問題的精确解（例如：計算無理數π的取值等），因此，在解決一些數值計算的問題時，數值概率算法常能派上用場。

例子:設f(x)=1-x2，計算定積分：的值

分析：要計算的定積分值的幾何含義就是圖中陰影部分的面積。可以試想，如果随機地向圖中虛線與x，y坐标軸所圍成的正方形中投點，那麼根據幾何概率的知識可知，随機點落入陰影區域的概率即為陰影部分的面積與虛線與x，y坐标軸所圍成的正方形的面積之比。計算定積分。

#include "stdio.h" #include "math.h" #include "stdlib.h" #include "time.h" double Darts(int n) { double x,y; time_t t; int i,count = 0; srand((unsigned)time(&t)); for(i=0;i<n;i ) { x = rand()0/100.0; y = rand()0/100.0; if(y<=1 - pow(x,2)) count ; } return (double)count/(double)n; /*返回落入陰影區域的點數與總點數n的比值*/ } main() { int n; printf("Please input the accuracy\n") ; /*輸入精度，即投點數*/ scanf("%d",&n); printf("The result is about\n"); /*輸出計算結果*/ printf("%f\n",Darts(n)); getche(); }

運行結果：

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!