[程式設計工法] 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. 六種授權條款。

[程式設計工法] C/ C++，a006: 一元二次方程式@0判

C/ C++，a006: 一元二次方程式@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/

Jun. 23, 2020

[1]

問題解決（Problem Solving）之逻輯思維 ＝

心法： 程式設計哲思（Philosophical Thinking for Programming） ＋

技法：程式設計工法（Skills for Programming）

求一元二次方程式 ax2+bx+c=0 的根。

---

解析：

• 直接run結果建立直觀：。
• Idea：依据判別式的三种情況，使用if判斷各條件成立下的相應公式解計算。
• sqrt()定義在math.h裡。

---

//http://siro.moe.edu.tw/teach/index.php?n=0&m=0&cmd=content&sb=3&v=3&p=437

#include <iostream>

#include <math.h>

using namespace std;

int main(void) {
int a=0, b=0, c=0;
float D=0;

cin>>a>>b>>c; 

D=b*b-4*a*c;

if (D>0) 
cout << "Two different roots x1=" << (-b+sqrt(D))/(2*a)  <<  " , "  << "x2=" << (-b-sqrt(D))/(2*a); //第一次作時打成2*a，忘了() 

if (D<0 span="">
cout << "No real root";

if (D==0)
cout << "Two same roots x=" << (-b+sqrt(D))/(2*a);

return 0;
}

---

参考資料：

1. 六種授權條款。

[程式設計工法] C/ C++，麗山高中資科教甄109，專業檢定：子字串

C++，麗山高中資科教甄109，專業檢定：子字串

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. 13, 2020

[1]

問題解決（Problem Solving）之逻輯思維 ＝

心法： 程式設計哲思（Philosophical Thinking for Programming） ＋

技法：程式設計工法（Skills for Programming）

子字串（substrings）　找出字串1中是否包含子字串2，子字串2的每個元素需依序出現在字串1中，例如：str1 = "AbcYmn"，str2 = "AY"，str1 Ê str2。

---

解析：

• 直接run結果建立直觀：。
• Idea：從小例子觀察出規律（regularity） Þ 把str2中的每個元素（i-loop）和str1比对（j-loop），当对到的次數和str2長度相等時（都有match到）就為尋獲。
• 此題包含迴圈控制（loop control）與search problem。

---

#include <iostream>
using namespace std;

int main(void) {
char str1[]={'A', 'b', 'c', 'Y', 'm', 'n'};
//char str2[]={'A', 'Y'};
char str2[]={'b', 'c', 'Y'};

int i=0, j=0;
int found=0;

for (i=0; i<3; i++) {
for (j=0; j<6; j++) { //把str2[]內的元素和str1[]相比
if (str2[i] == str1[j]) {
found++;
break;
}
}
}

if (found==3) {
cout << "Found.\n";
} else {
cout << "Not found.\n";
}
return 0;
}

---

参考資料：

1. 六種授權條款。

[程式設計工法] C/ C++，科園實中資科教甄109，B8

C/ C++，科園實中資科教甄109，B8

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.7, 2020

[1]

問題解決（Problem Solving）之逻輯思維 ＝

心法： 程式設計哲思（Philosophical Thinking for Programming） ＋

技法：程式設計工法（Skills for Programming）

8. 下列程式碼執行後的輸出結果為 （8）

---

解析：

• 直接run結果建立直觀：
  。
• 追蹤fib()的呼叫过程：

fib(3) = fib(2) + fib(1)

          = fib(1) + fib(0) + fib(1)

          = 1 + 1 + 1

          = 3

---

#include <iostream>
#include <iomanip>
using namespace std;

int fib(int n) {
cout << n;

if (n < 2)
return 1;
else
return fib(n-1) + fib(n-2);
}

int main() {
int result = fib(3);
cout << result << endl;

return 0;
}

---

参考資料：

1. 六種授權條款。

[程式設計工法] C/ C++，科園實中資科教甄109，B7

C/ C++，科園實中資科教甄109，B7

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.7, 2020

[1]

問題解決（Problem Solving）之逻輯思維 ＝

心法： 程式設計哲思（Philosophical Thinking for Programming） ＋

技法：程式設計工法（Skills for Programming）

7. 下列程式碼執行後的輸出結果為（7）

---

解析：

• 直接run結果建立直觀：
  。
• Linked list數目追蹤。
• 陣列內容變化：。
• 題意图解：。

---

#include <iostream>
#include <iomanip>
using namespace std;

#define ARY_LENGTH 10

void print_array(int fri[]) {
int i = 0;

cout <<fri[] = ";

for (i = 0; i < ARY_LENGTH; i++) {
cout << fri[i] << " ";
}

cout << endl;
}

void find(int fri[], int n) {
int group=0;
int i;

for (i = 0; i < n; ++i) { //整個陣列掃一輪
if (fri[i] != -1) { //開追完串列
++group; //串列數
int j = i;

while (fri[j] != -1) { //根据當前索引位置的陣列內容跳至那個item
int next = fri[j];
fri[j] = -1;
j = next;

print_array(fri);
}
}
}

cout << group << endl;
}

int main(void) {
int fri[10]={4, 7, 2, 9, 6, 0, 8, 1, 5, 3};

print_array(fri);
find(fri, 10);

return 0;
}

---

参考資料：

1. 六種授權條款。

[程式設計工法] C/ C++，科園實中資科教甄109，B6

C/ C++，科園實中資科教甄109，B6

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. 5, 2020

[1]

問題解決（Problem Solving）之逻輯思維 ＝

心法： 程式設計哲思（Philosophical Thinking for Programming） ＋

技法：程式設計工法（Skills for Programming）

下列程式碼執行後的輸出結果為 （6）

---

解析：

• 直接run結果建立直觀：。
• local variable vs. global varibale。

---

#include <iostream>

using namespace std;

void add(int a) {
int s=3;

for (; a>=0; --a) {
cout<<s;
s++;
cout<<s;
}
}

int main() {
cout<<s;

add(s);
cout<<s;

s=5;
cout<<s<<endl;

return 0;
}

---

参考資料：

1. 六種授權條款。

[程式設計工法] C/ C++，科園實中資科教甄109，A1&2

C/ C++，科園實中資科教甄109，A1&2

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. 5, 2020

[1]

問題解決（Problem Solving）之逻輯思維 ＝

心法： 程式設計哲思（Philosophical Thinking for Programming） ＋

技法：程式設計工法（Skills for Programming）

[題組] ：下面為某一程式執行的結果及其程式碼片段，請據此回答1、2 題。

1. 請問上方程式的空格（i）與（j）應分別填入？

  （A）d、b （B）d、a （C）b、a （D）b、d

2. 承上題，若將while 迴圈的判斷條件改為「d<=200」，則最後一個輸出的數字為何？

  （A）144 （B）200 （C）233 （D）程式出現錯誤無法輸出

---

解析：

1. 

A. 直接run結果建立直觀：，蛋，有沒4層相4？那個Fxxx序列（這題我應該拿分的啊！）

B.

1A：，

   d<-a b="" div="" nbsp="">

   a<-d a="" b="" div="">

   => d=d+b => 每次都加1。

1B：，

   d<-a b="" div="">

   a<=d=a+b

   b<-a a="" b="" div="">

   => d<-2 a="" b=""> 每次都乘2

1C：

   a<-b div="">

   b<-a div="">

   =>d<-a b="2（永遠a=b=1）"> 呈式永遠不會停

---

2

1若选A，則答案為201。

1若选B，則答案為256。

1若选D，則答案為233。

---

∴implement Fib #的algorithm為：

	a	b	d
n	1	2	3	4	5
Fib(n)	1	1	2	3	5
		a	b	d
n	1	2	3	4	5
Fib(n)	1	1	2	3	5

---

#include <iostream>

using namespace std;

int main() {

int a=1, b=1, d=0;

cout<<a<<endl;

cout<<b<<endl;

while (d<=200) {

d=a+b;

a=b;

b=d;

cout<<d<<endl;

}

return 0;

}

---

著名演算法要背！

---

参考資料：

1. 六種授權條款。