• <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>

            XGuru's Blog

            技術,是一種態度。關注:高性能后端技術/服務器架構/C++/C/LAMP

               :: 首頁 :: 聯系 :: 聚合  :: 管理
              20 Posts :: 0 Stories :: 93 Comments :: 0 Trackbacks

            公告





            twitter / xoXGuru

            feedsky
            抓虾
            google reader
            鲜果
            QQ邮箱
            九点

            常用鏈接

            留言簿(12)

            搜索

            •  

            最新評論

            閱讀排行榜

            by Xguru

             又說階乘,這是老生常談了吧。想都不用想,一個遞歸輕松搞定!

            int factorial(int n)
            {
                
            if( n == 1)
                    
            return 1;
                
            return n * factorial(n-1);
            }

            或者你覺得遞歸效率沒有尾遞歸來的好 ,大筆一揮。

            long fact_iter(long product, long counter, long maxcount) 
            {      
              
            return (counter > maxcount) ? product : fact_iter(product*counter, counter+1, maxcount);
            }
                  

            long factorial(long n) 
            {
              
            return fact_iter(11, n);    
            }

             
                     或者你看過《代碼大全》上面說過:“如果為我工作的程序員用遞歸去計算階乘那么我寧愿換人。”
            使用遞歸求階乘速度緩慢,無法預測運行期間內存使用情況,難以理解。于是你把遞歸改成了循環語句。

            int factorial(int n)
            {
                
            int result = 1;
                
            for(int i = 2 ; i <= n; i++)
                
            {
                    result 
            = result * i;
                }

                
            return result;
            }
                      當你寫下這些代碼的時候,會不會覺得少了些什么?

                      在我的32位環境上測試一下,計算到33!的時候的溢出了,于是你會說,這是int的值太小了嘛,于是你換了個long double,測試一下,什么玩意嘛這是,數再大一點的話也不行了

                     
             那就改用鏈表或者數組表示吧,鏈表的速度就太慢了,用數組吧。

            int factorial2(int n,int a[])

                
            int carry;
                
            int digit = 1;
                a[
            0= 1;
                
            int temp;
                
            for(int i = 2; i <= n; ++i)
                
            {
                    
            for(int j = 1, carry = 0; j <= digit; ++j)    
                    
            {
                        temp 
            = a[j-1* i + carry;
                        a[j
            -1= temp % 10;
                        carry 
            = temp / 10;
                    }

                    
            while(carry) 
                    
            {
                        a[
            ++digit-1= carry % 10;
                        carry 
            /= 10;
                    }

                }

                
            return --digit;
            }

                    這個算法模擬手工計算的過程,將結果保存在a數組中,返回的是結果的位數

                   你在這個時候是不是感覺輕飄飄了呢?請暫時打住。

                    如果我要求一個
            10W以上大數的一個科學計數法的表達式呢?或者是問你,10W 級別上的N!左邊第三位的數字是多少?呃,這個是數學家的事了吧?振作精神,來挑戰自我吧!真正的程序員需要的就是這種追根究底的精神。
                    來試試數學分析方法,James Stirling這位蘇格蘭數學家,280多年前就給出了這個極限式子

                                                 

                   這個式子能用極快的速度求出n!的近似值,也可以使用它來無限接近準確結果。具體的介紹和證明過程在這里 或者 這里

            斯特靈級數公式



                  下面的代碼是求大數N!科學計數法表示

            struct bigNum 
            {
                   
            double n; //尾數
                   int    e; //指數
            }
            ;
            void factorial3(struct bigNum *p,int n)
            {
                   
            double logx,s,item;//s:級數的和  item:級數的每一項
                   int i;
                   logx 
            = n* log10((double)n/E);
                   p
            ->= (int)(logx);   p->n= pow(10.0, logx-p->e);
                   p
            ->*= sqrt( 2* PI* (double)n);
                   
            for (item=1.0,s=0.0,i=0;i<sizeof(a1)/sizeof(double);i++)
                   
            {
                          s 
            += item * a1[i];
                          item 
            /= (double)n;
                   }

                   p
            ->*=s;
            }

             

                  下面這個是階乘的對數的漸近展開式
                           

            void factorial3b(struct bigNum *p,int n)
            {
                
            double logR;
                
            double s,item;
                
            int i;
                logR
            =0.5*log(2.0*PI)+((double)n+0.5)*log(n)-(double)n;
                
                
            for (item=1/(double)n,s=0.0,i=0;i<sizeof(a2)/sizeof(double);i++)
                
            {
                    s
            += item * a2[i];
                    item 
            /= (double)(n)* (double)n; 
                }

                logR
            +=s;
                p
            ->= (int)( logR / log(10));//換底公式
                p->= pow(10.00, logR/log(10- p->e);
            }

                   要是求階層的位數也是特別簡單

            double getFactorialLength(int n)
            {
                
            return (n * log(double(n)) - n + 0.5 * log(2.0 * n * PI )) / log(10.0)+1;
            }

                   這個求出來的是位數的近似數,或者是改進一下,使用ceil函數來求出不小于給定實數的最小整數。

            int getFactorialLength(int n)
            {
                
            if( n == 1 )
                    
            return 1;
                
            else
                
            return (int)ceil((N*log(N)-N+log(2*N*PI)/2)/log(10));
            }


            到此,你會不由感嘆:計算機科學中最閃光,最精髓,最本質的東西還是數學



            芒德布羅集合的邊界
            最后用羅素的話結束這篇隨筆:
                   Mathematics, rightly viewed, possesses not only truth, but supreme beauty — a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show. The true spirit of delight, the exaltation, the sense of being more than Man, which is the touchstone of the highest excellence, is to be found in mathematics as surely as poetry.

             

            參考資料
            1.Tom M. Apostol.《數學分析, 微積分》(Mathematical Analysis)
            2.Steve McConnell.《代碼大全(第二版)》(CODE COMPLETE, Second Edition)
            3.http://en.wikipedia.org/wiki/Stirling_approximation#History

            4.
            http://mathworld.wolfram.com/StirlingsApproximation.html

            5.
            http://zh.straightworldbank.com/wiki/%E6%96%AF%E7%89%B9%E6%9E%97%E5%85%AC%E5%BC%8F

             

            posted on 2009-12-30 19:02 XGuru 閱讀(1903) 評論(4)  編輯 收藏 引用

            Feedback

            # re: 雜感系列之二--階乘算法雜感 2009-12-30 22:55 NighCrawler
            最后的那張分形幾何圖是軟件生成的?  回復  更多評論
              

            # re: 雜感系列之二--階乘算法雜感 2010-01-05 18:24 argmax
            Stirling公式只是一個近似,當n較大時才比較接近原始的結果。  回復  更多評論
              

            # re: 雜感系列之二--階乘算法雜感[未登錄] 2010-04-02 17:34 Mingle
            文章中的數學公式是如何書寫的?  回復  更多評論
              

            # re: 雜感系列之二--階乘算法雜感[未登錄] 2010-04-06 22:37 xguru
            @Mingle
            latex公式常用宏包 http://www.ctex.org/documents/packages/math/index.htm

            還有 word2007的公式生成也不錯呢
              回復  更多評論
              

            久久亚洲精精品中文字幕| 午夜视频久久久久一区 | 久久综合欧美成人| 久久精品草草草| 看全色黄大色大片免费久久久| 国内精品伊人久久久影院| 亚洲精品午夜国产VA久久成人| 精品久久香蕉国产线看观看亚洲 | 亚洲av日韩精品久久久久久a | 欧美一级久久久久久久大片| 欧美久久久久久精选9999| 亚洲AV无码久久精品色欲| 久久亚洲欧美日本精品| 欧美精品丝袜久久久中文字幕| 亚洲AV无码久久精品成人| 99久久伊人精品综合观看| 久久99精品久久久大学生| 97精品国产97久久久久久免费| 久久99精品国产麻豆宅宅| 久久99精品久久久久久水蜜桃| 亚洲人成伊人成综合网久久久| 91久久精品无码一区二区毛片| 精品国产99久久久久久麻豆| 久久久免费观成人影院| 精品久久777| 久久丫精品国产亚洲av| 久久久久久精品免费看SSS| 一级做a爰片久久毛片16| 99久久国产精品免费一区二区 | 日韩一区二区久久久久久| 久久亚洲国产最新网站| 成人亚洲欧美久久久久| 国产精品一区二区久久国产| 成人久久免费网站| 欧美日韩精品久久免费| 久久久久久久久久久免费精品| 国产欧美久久久精品| 99久久精品费精品国产一区二区 | 久久―日本道色综合久久| 日韩久久久久久中文人妻| 香蕉久久AⅤ一区二区三区|