2020年5月21日 星期四

[程式設計工法] C/ C++,麗山高中資科教甄109,專業檢定:求n!後面連續0個數

C/ C++,麗山高中資科教甄109,專業檢定:求n!後面連續0個數


FB2http://gg.gg/TedLeeMicrobitFB/
URL2http://gg.gg/TedLeeMicrobit/

Line:ted2016.kpvs
Email:Lct4246@gmail.com
FB1http://gg.gg/TedLeeFB/
Bloghttp://gg.gg/TedLeeBlog/
URL1http://gg.gg/TedLeeURL/

May. 21, 2020
88x31.png[1]

問題解決(Problem Solving之逻輯思維 =
心法: 程式設計哲思(Philosophical Thinking for Programming) +
技法:程式設計工法(Skills for Programming)

寫出一個function求出n!後面的連續"0"個數,(int n為此function的參數)
例如n=6, 6!=720 , 後面有1個連續的0,所以output為1。

    解析:
    • 直接run結果建立直觀:
    • Idea:直接用疊代(iteration)法[註]先玩看看n!的前幾個數字乘積:
      以下是用小算盤算出來的結果:
    1! = 1
    2! = 2
    3! = 6
    4! = 24
    5! =120
    6! = 720
    7! = 5,040
    8! = 40,320
    9! = 362,880
    10! = 3,628,800
    11! = 39,916,800
    12! = 479,001,600‬
    13! = 6,227,020,800
    14! = 87,178,291,200
    15! = 1,307,674,368,000

    它在第13!以後就出現了差異。所以直覺上本題不能用程式硬幹吧?
    因此,考慮用因式分解

    下列程式碼出自於這裡

    #include <iostream>
    using namespace std;

    int fact_tail_zero(int n) {
       int ret=0;
       
       while (n/=5) { //原問題転換成:能被5重覆除的次數
            cout << "   n = " << n << endl;
            cout << "      ret = " << ret << endl;
    ret+=n;
       }
       return ret;
    }

    int main(void) {
    int x;
        while(scanf("%d", &x)==1) //重覆玩
           printf("tail zero : %d\n", fact_tail_zero(x));
           
    return 0;
    }


    註:疊代法求n!:

    #include <ostream>t
    using namespace std;

    //produc = 1 * 2 * 3 * ... * j * ... * n
    //用i來掃過[1, n],邊掃邊加 
    int main(void) {
    unsigned int product = 1; //保存目前累乘和,1 * 2 * 3 * ... * k 
    int i = 0;   //下一個累乘值,1 * 2 * 3 * ... * k * i 
    for (i=1; i<41; i++) {
    product *= i;
    cout << i << "! = " << product << endl;
    }
    return 0;

    }

    参考資料
    1. 六種授權條款