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

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

Ted Lee的土饅頭（To Mentor）工坊

FB2：http://gg.gg/TedLeeMicrobitFB/

URL2：http://gg.gg/TedLeeMicrobit/

Line：ted2016.kpvs
Email：Lct4246@gmail.com
FB1：http://gg.gg/TedLeeFB/

Blog：http://gg.gg/TedLeeBlog/
URL1：http://gg.gg/TedLeeURL/

May. 21, 2020

[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. 六種授權條款。