• <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>
            C++分析研究  
            C++
            日歷
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789
            統計
            • 隨筆 - 92
            • 文章 - 4
            • 評論 - 4
            • 引用 - 0

            導航

            常用鏈接

            留言簿

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

             

              有關階乘的算法,不外乎兩個方面:一是高精度計算;二是與數論相關。

              一。 高精度計算階乘

              這實際上是最沒有技術含量的問題,但是又會經常用到,所以還是得編寫,優化它的計算。

              首先看小于等于12的階乘計算(計算結果不會超出32位范圍):

              int factorial(int n) {

              if (n == 1 || n == 0)

              return 1;

              return factorial(n-1)*n;

              }

              這個遞歸程序簡單明了,非常直觀,然而一旦n > 12,則超過32位int型的范圍出現錯誤結果,所以上面這個遞歸程序僅適合n <= 12的階乘計算,為了計算較大n的階乘,需要將高精度乘法算法納入到階乘計算中來,高精度乘法過程可以如下簡單的描述:(其中A * B = C,A[0], B[0], C[0]分別存儲長度)

              for (i = 1; i <= A[0]; i++)

              for (j = 1; j <= B[0]; j++) {

              C[i+j-1] += A[i]*B[j]; // 當前i+j-1位對應項 + A[i] * B[j]

              C[i+j] += C[i+j-1]/10; // 它的后一位 + 它的商(進位)

              C[i+j-1] %= 10; // 它再取余即可

              }

              C[0] = A[0] + B[0];

              while (C[0] > 1 && C[C[0]] == 0) C[0]--; // 去頭0,獲得實際C的長度

              有了這個高精度乘法之后,計算階乘就可以簡單的迭代進行:

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

              將i轉換成字符數組;

              執行高精度乘法:將上一次結果乘上i

              }

              二。 與數論有關

              由于階乘到后面越來越大,巧妙的利用數論求得一些有趣的數字(數值)等成為階乘算法的設計點,下面給出幾道相關的問題與分析: www.liuhebao.com

              (1) 計算階乘末尾第一個非0數字:

              這是一個比較經典的問題,比較復雜的算法是利用一個艱難的數學公式,可惜我不會,從網上的資料學習中,整理出下面這個簡單易懂的算法:

              觀察n!,可以發現在乘的過程中,對于任意 n > 1,n!的末尾第一個非0數字都是偶數。我們只需保留最后一位非零數。當要乘的數中含有因數5時,我們可以把所有的因數5都當作8來乘。這是因為:

              …x2*5=…10(舍)或…60,最后一位非零數為6。而恰好2*8=16,末位為6。

              …x4*5=…70(舍)或…20,最后一位非零數為2。而恰好4*8=32,末位為2。

              …x6*5=…30(舍)或…80,最后一位非零數為8。而恰好6*8=48,末位為8。

              …x8*5=…90(舍)或…40,最后一位非零數為4。而恰好8*8=64,末位為4。

              (對于n > 1時,最后一位不會出現 1, 7, 3, 9,而永遠是2, 4, 6, 8的循環出現)

              因此,在迭代作乘法時,主要就是計算因子5的數量,同時可見因子5的個數以4為循環節(即只需要取它的數量對4取模)。那么對于不同情況下的因子5的數量,可以通過res[5][4] = {{0,0,0,0}, {2,6,8,4}, {4,2,6,8}, {6,8,4,2}, {8,4,2,6}}來得到,使用nonzero[i]表示i的階乘的最后一位,那么:

              如果t是偶數,則直接乘:nonzero[i] = (nonzero[i-1]*t)%10。

              否則nonzero[i] = res[((nonzero[i-1]*t)%10)/2][five];

              其中t是除掉所有因子5的結果,five為因子5數量對4的模。相關題目:

              http://acm.zju.edu.cn的第1222題。不過這一道題注意的是,它的輸入n并非只在32位int數值范圍內,而是有很大的長度,所以計算這道變態題目時,需要利用到高精度除法(n/=5)和高精度加法(cnt+=n)。

              (2)。 階乘末尾有多少個0

              分析發現,實際上形成末尾0,就是因子5的數量,而計算1~n之間包含一個因子i的個數的簡單算法就是:

              cnt = 0; while (n) { n /= i; cnt += n; }

              因此,直接將i換成5,就可以得到因子5的數量,也即n!末尾0的數量。

              (3)。 返回階乘左邊的第二個數字

              簡單算法:用實數乘,超過100就除以10,最后取個位即可。因為整數部分的個位就是階乘結果左邊的第二個數字。相關題目: www.yzyedu.com

              (4)。 判斷數值 m 是否可以整除 n!

              算法:使用素因子判斷法

              A. 首先直接輸出兩種特殊情況:

              m == 0 則 0肯定不會整除n!;

              n >= m 則 m肯定可以整除n!;

              B. 那么就只剩最后一種情況:m > n,我們從m的最小素因子取起,設素因子為i那么可以 求得m的素因子i的個數 nums1;再檢查閉區間 i ~ n 之間的數,一共包含多少個素因子i,就可以簡單的利用上面(2)中所介紹的數學公式進行計算得到nums2。如果nums2 < nums1,就表示1 ~ n中包含素因子的數量 < 除數m包含素因子i的數量,那么m必然不能整除n!,置ok = false。 www.yzjxsp.com

              C. 最后:如果 !ok or m > n or m == 0 則不能整除;否則可以整除

              (5)。數字N能否表示成若干個不相同的階乘的和:

              這里可以選擇的階乘為:0! ~ 9!,實際上這一題與數論無關,與搜索有關。相關題目:http://acm.zju.edu.cn 的2358題。

              分析,由于可供選擇的階乘數量較少,直接可以利用DFS搜索來做:

              A. 首先將0 ~ 9的階乘作一個表A[10];再設置一個可以組成“和”的數組ans[N]。

              B. 深度優先搜索方法:

              search(n) {

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

              sum += A[i]; //求和

              如果sum在ans數組中不存在,則將sum插入到ans[]數組中

              search(n+1);

              sum -= A[i]; //回溯

              }

              }

              C. 最后對于輸入n,就在ans數組中查找是否存在n,如果存在,則表示n可以表示成不同的階乘和,否則不行。

            posted on 2011-03-21 00:40 HAOSOLA 閱讀(328) 評論(0)  編輯 收藏 引用
             
            Copyright © HAOSOLA Powered by: 博客園 模板提供:滬江博客
            PK10開獎 PK10開獎
            亚洲欧美久久久久9999| 国内精品久久久久久99| 日韩AV毛片精品久久久| 一级a性色生活片久久无少妇一级婬片免费放 | 欧美与黑人午夜性猛交久久久 | 亚洲日本va午夜中文字幕久久| 欧美亚洲国产精品久久高清| 91久久精一区二区三区大全| 久久综合日本熟妇| 99精品国产在热久久无毒不卡| 久久天天日天天操综合伊人av| 99久久国产热无码精品免费 | 国产精品99久久精品| 漂亮人妻被中出中文字幕久久| 精品国产VA久久久久久久冰| 久久这里的只有是精品23| 99久久婷婷国产一区二区| 久久久久亚洲AV无码永不| 亚洲精品国产综合久久一线| 色综合久久88色综合天天| 日韩精品久久久久久免费| 日本精品久久久久影院日本| 亚洲成人精品久久| 激情伊人五月天久久综合| 色综合久久综合中文综合网| 国产精品久久久久久久久软件| 国产精品一区二区久久精品无码| 97久久综合精品久久久综合| 久久久精品国产sm调教网站 | 一本色道久久综合狠狠躁| 国产精品99久久久久久宅男小说| 久久精品国产72国产精福利| 成人精品一区二区久久| 91久久香蕉国产熟女线看| 91精品婷婷国产综合久久| 一本久久a久久精品综合夜夜| 久久青草国产精品一区| 中文字幕一区二区三区久久网站| 777米奇久久最新地址| 72种姿势欧美久久久久大黄蕉| 少妇精品久久久一区二区三区|