• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 70  文章 - 160  trackbacks - 0

            公告:
            知識共享許可協議
            本博客采用知識共享署名 2.5 中國大陸許可協議進行許可。本博客版權歸作者所有,歡迎轉載,但未經作者同意不得隨機刪除文章任何內容,且在文章頁面明顯位置給出原文連接,否則保留追究法律責任的權利。 具體操作方式可參考此處。如您有任何疑問或者授權方面的協商,請給我留言。

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            搜索

            •  

            積分與排名

            • 積分 - 179366
            • 排名 - 147

            最新評論

            閱讀排行榜

            評論排行榜

            接著上一篇: 隨機化算法(1) — 隨機數

            在這章開篇推薦下chinazhangjie總結的隨機算法,因為咱兩看的是同一本書,所以大家也可以去參考下他的,總結的很不錯。

            http://www.cnblogs.com/chinazhangjie/archive/2010/11/11/1874924.html

            (順便再PS一下,小杰也是我論壇的C/C++問題求助板塊的版主,C/C++小牛)

            這一章我就把書中的一個例子舉出來了,感覺雖然很簡單,但是很有意思。

            用隨機投點法計算Pi值

            設有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設落入圓內的點數為k。由于所投入的點在正方形上均勻分布,因而所投入的點落入圓內的概率為(Pi*r*r)/(4*r*r)= Pi/4 。所以當n足夠大時,k與n之比就逼近這一概率。從而,PI 約等于 (4*k)/n.

            如下圖:

             

             因為代碼里用到了上一章《概率算法(1) — 隨機數》里的RandomNumber類,所以大家可以先把前一章看看。

            我把這個偽隨機類再貼一遍:

             const unsigned long maxshort = 65535L;

            const unsigned long multiplier = 1194211693L;
            const unsigned long adder = 12345L;
             
            class RandomNumber{
            private:
                
            // 當前種子
                unsigned long randSeed;
            public:
                
            // 構造函數,默認值0表示由系統自動產生種子
                RandomNumber(unsigned long s = 0);
                
            // 產生0 ~ n-1之間的隨機整數
                unsigned short Random(unsigned long n);
                
            // 產生[0, 1) 之間的隨機實數
                double fRandom();
            };
             
            // 產生種子
            RandomNumber::RandomNumber(unsigned long s)
            {
                
            if(s == 0)
                    randSeed 
            = time(0);    //用系統時間產生種子
                else
                    randSeed 
            = s;
            }
             
            // 產生0 ~ n-1 之間的隨機整數
            unsigned short RandomNumber::Random(unsigned long n)
            {
                randSeed 
            = multiplier * randSeed + adder;
                
            return (unsigned short)((randSeed >> 16% n);
            }
             
            // 產生[0, 1)之間的隨機實數
            double RandomNumber::fRandom()
            {
                
            return Random(maxshort) / double(maxshort);
            }

             主文件Main:

            /*
            * Author: Tanky woo
            * Blog:   www.WuTianQi.com
            * Date:   2010.12.8
            * 用隨機投點法計算Pi值
            * 代碼來至王曉東《計算機算法設計與分析》
            */
             
            #include 
            "RandomNumber.h"
            #include 
            <iostream>
            #include 
            <iomanip>
            #include 
            <time.h>
            using namespace std;
             
            double Darts(long n)
            {
                
            // 用隨機投點法計算Pi值
                static RandomNumber dart;
                
            long k = 0;
                
            for(long i=1; i<=n; ++i)
                {
                    
            double x = dart.fRandom();
                    
            double y = dart.fRandom();
                    
            // 在圓內
                    if((x*x+y*y) <= 1)
                        
            ++k;
                }
                
            return 4 * k / double(n);
            }
             
            int main()
            {
                
            // 當進行1,000次投點時
                cout << Darts(1000<< endl;
                
            // 當進行10,000次投點時
                cout << Darts(10000<< endl;
                
            // 當進行100,000次投點時
                cout << Darts(100000<< endl;
                
            // 當進行1,000,000次投點時
                cout << Darts(1000000<< endl;
                
            // 當進行10,000,000次投點時
                cout << Darts(10000000<< endl;
                
            // 當進行100,000,000次投點時
                cout << Darts(100000000<< endl;
                
            return 0;
             
            }

             

             通過代碼可以看出,隨機投點越多,則越接近與3.1415926…

            這個和拋硬幣時求硬幣正反面概率類似,實驗次數越多,則越接近于理論值。

            下一章是《隨機化算法(3) — 舍伍德(Sherwood)算法》

            Tanky Woo原創,歡迎轉載,轉載請附上鏈接,請不要私自刪除文章內任何關于本博客的鏈接。

            posted on 2010-12-12 11:51 Tanky Woo 閱讀(2480) 評論(1)  編輯 收藏 引用

            FeedBack:
            # re: 隨機化算法(2) — 數值概率算法 2010-12-16 08:37 tiny
            goodjob  回復  更多評論
              
            亚洲国产成人久久综合一 | 亚洲精品无码久久毛片| 欧美麻豆久久久久久中文| 久久频这里精品99香蕉久| 中文精品久久久久人妻不卡| 精品久久久久久无码专区| 久久久国产精品网站| 伊人久久亚洲综合影院| 亚洲AV无码1区2区久久| 久久精品二区| 韩国免费A级毛片久久| 欧美亚洲日本久久精品| 久久久精品2019免费观看| 欧美日韩成人精品久久久免费看| 无遮挡粉嫩小泬久久久久久久| 93精91精品国产综合久久香蕉| 久久婷婷五月综合成人D啪| 国产精品免费久久| 久久精品人人做人人妻人人玩| 久久高清一级毛片| 热99re久久国超精品首页| 亚洲精品乱码久久久久久自慰| 精品久久久久中文字| 国产精品青草久久久久婷婷| 久久精品青青草原伊人| 亚洲精品无码久久毛片| 久久午夜福利电影| 久久99精品国产麻豆不卡| 久久精品国产一区二区三区日韩| 99精品国产99久久久久久97 | 久久精品亚洲精品国产色婷| 中文字幕久久精品| 久久免费香蕉视频| 久久精品成人| 久久亚洲国产精品123区| 超级碰久久免费公开视频| 亚洲一区中文字幕久久| 99久久亚洲综合精品网站| 久久精品国产精品亜洲毛片| 国内精品久久久久久中文字幕| 国产—久久香蕉国产线看观看|