###### tags: `資訊科技概論` # 程式設計(使用C++) [銜接課程題單](https://hackmd.io/@cube/Hk1YqttAL) ## 零、評量方式 1. 上課基本練習 2. [SoloLearn C++ Tutorial (XP/4) ](https://www.sololearn.com/) :star: 本單元結束後1週登記成績。 :lollipop: 全部學完可拿到[證書](https://i.imgur.com/0yAAPlB.jpg) ,若拿到 2 張證書有小獎 。 3. [TOI線上練習賽](https://toi-reg.csie.ntnu.edu.tw/)(Bonus) - 上學期10、11、12月,下學期3、4、5月,最後一週。 - 星期一08:00 ~ 星期五20:00。 - 90分鐘。 - 教師代碼:12 - [證書](https://drive.google.com/open?id=1DcgDKn1R33kOPc_HazdIyQDgyYxSCPlZ)。 ## 一、基本使用 ### 1. 編輯軟體 + [Code::Blocks / codeblocks-17.12mingw-setup.exe](http://www.codeblocks.org/) + [Dev-C++](http://orwelldevcpp.blogspot.com/2015/04/dev-c-511-released.html) + Google文件 - 學習歷程檔案之課程學習成果 - [Code Block-Google Docs add-on](https://gsuite.google.com/marketplace/app/code_blocks/100740430168) + [HackMD-Markdown共筆平台](https://hackmd.io/) - 學習歷程檔案之課程學習成果 - [從無到有學習HackMD](https://www.youtube.com/watch?v=r5FOR-YU33c&t=1s) - [用Markdown做筆記](http://moocs.nccu.edu.tw/media/17832) - [Markdown教學](https://dotblogs.com.tw/chris_coding/2017/03/30/102046) - [表格生成器:Markdown Tables Generator](http://www.tablesgenerator.com/markdown_tables) - [功能介紹](https://hackmd.io/features-tw) + 學習歷程檔案之課程學習成果 - [大學選才與高中育才輔助系統](https://collego.ceec.edu.tw/) - 最後一週上課結束前如果認證完成,學期總成績加分。 - 上傳的PDF大小限制為2MB,圖片如果太大,可用小畫家將解析度調小。 - HackMD筆記可下載成HTML(選單/下載 / HTML),再以[PDF24 Tools](https://tools.pdf24.org/zh/)轉成PDF。如果要將PDF插入到Word中,可用同一網站將PDF轉圖像再插入。 ### 2. 變數型態 | 常用型態 | 意義 | 範圍 | |:-------|:---------- |:-------| | int | 整數 |-2147483648~2147483647|| | long long int | 長整數 |-2^63^ ~ 2^63^-1|| | float | 單精度浮點數(小數) |±1.5x10^−45^ ~ ±3.4x10^38^| | double | 雙精度浮點數(小數) |±5.0×10^−324^ ~ ±1.7×10^308^| | char | 字元 | 'A'| | string | 字串 | "Hello"| | bool | 布林 | true、false| ### 3. 變數宣告 ``` javascript int math=80; // 資料型態 變數名稱; double pi=3.14159265359; // 資料型態 變數名稱=初值; int sum,ave,rank; // 資料型態 變數名稱1,變數名稱2,變數名稱3...; ``` :::info EX_01:輸入三角形三邊長,以[海龍公式](http://www2.chsh.chc.edu.tw/bee/1050206/heron%20formula.pdf)求三角形面積。 :mega: 先輸出s看看是否正確。   (1) 先乘除後加減   (2) 整數除法、浮點數除法:5/2、5.0/2   (3) 資料型態轉換: a=4, b=5, c=6, s=7.5    ::: ``` javascript= #include <iostream> ....... // 含入 cmath 標頭檔,才可使用sqrt using namespace std; int main() { /* int a; int b; int c; cin >> a; cin >> b; cin >> c; cout << a; cout << b; cout << c; */ ........ // 宣告 a,b,c 三邊長變數為整數型態 double s, area; ........ // 以cout輸出提示字串 ........ // 以cin輸入邊長變數。cin >> a,b,c; 是錯誤的語法 ........ // 輸出a,b,c,看看輸入是否正確 s = ........ // 分子要加(),且把型態轉成double area = ........ // sqrt開根號,乘號不可以省略 cout << "三角形面積為 " << area << endl; // a=3,b=4,c=5,area=6 // a=4,b=5,c=6,area=9.92157 return 0; } ``` ## 二、運算子 ### 1. 算數運算子 | 算數運算子 | 意義 | 備註| |:-------- |:------ |:-------| | + | 加 | | | - | 減 | | | * | 乘 | | | / | 除 | | | % | 取餘數 | | | ++ | 遞增 | i++ 即 i=i+1| | \-\- | 遞減 | i\-\- 即 i=i-1| ``` javascript= int a=1,b; b=a++; // b=++a; cout << a << " " << b; /* b=a++; b=a; a++; b=++a; a++; b=a; */ ``` ### 2. 關係運算子 | 關係運算子 | 意義 | 備註| |:-------- |:------ |:-------| | == | 等於 | =是指派,==是判斷是否相等 | | != | 不等於 | | > | 大於 | | >= | 大於等於 | | < | 小於 | | <= | 小於等於 | ### 3. 邏輯運算子 | 邏輯運算子 | 意義 | 備註| |:-------- |:------ |:-------| | && | and | | \|\| | or | | ! | not | ## 三、條件式 ### 1. if 條件式語法 ``` javascript if(條件) { 條件「成立」時的程式碼 } ``` ### 2. if~else 語法: ``` javascript if(條件) { 條件「成立」時的程式碼 } else { 條件「不成立」時的程式碼 } ``` :mega: [常用運算子的優先順序](https://itw01.com/V2HWOE4.html) :mega: if()後不能加「;」 :mega: 養成縮排的好習慣:大括號 { } 內的程式碼以Tab鍵向右縮排,可以增加程式碼的可讀性,並方便除錯。 :::info EX_02:承EX_01,先判斷三邊長是否可以構成三角形。如果可以,求三角形面積;如果不行,輸出錯誤。 Tip:每邊長要大於0,且任兩邊之和要大於第三邊。 ::: ``` javascript= int main() { ........ // 宣告 a,b,c 三邊長變數為整數型態 double s, area; cout << "請輸入三邊長:"; cin >> a >> b >> c; if (a > 0 && ........ && a + b > c && ........) // if else 後不可加分號 { s = ........ area = ........ cout << "三角形面積為 " << area << endl; } else // 不用加分號 { cout << "不能構成三角形"; } // -1 5 5 // 1 3 1 return 0; } ``` ### 3. 巢狀 if 語法 ``` javascript if(條件1) { if(條件2) { 條件1「成立」,且條件2「成立」時的程式碼 } else { 條件1「成立」,且條件2「不成立」時的程式碼 } } else { 條件1「不成立」時程式碼 } ``` :mega: if或else的大括號{ }內,都可再增加條件式。 :::info EX_03:驗證登入帳號、密碼。 ::: ``` javascript= int main() { int a; cin >> a; cout << a+10; string b; cin >> b; cout << b; cout << b+10; cout << b+"10"; return 0; } ``` ``` javascript= int main() { string user,pwd; cout << "請輸入帳號:"; cin >> user; ........ // 讓使用者輸入密碼 ........ ........ // 如果帳號正確 而且 密碼正確 { cout << "Welcome"; } ........ // if 條件不成立 { cout << "帳號或密碼輸入錯誤"; } return 0; } ``` ``` javascript= int main() { string user,pwd; cout << "請輸入帳號:"; cin >> user; ........ // 讓使用者輸入密碼 ........ if (user=="admin" && ........) { cout << "Welcome"; } else { ........ // 不等於!= { cout << "帳號錯誤"; } ........ { cout << "密碼錯誤"; } } // Q:帳號、密碼都錯時會顯示?如何顯示帳號錯誤,密碼錯誤? return 0; } ``` ### 4. 多重選擇 if~else if~else 語法 ``` javascript if(條件1) { 條件1「成立」時程式碼區塊 } else if(條件2) { 條件1「不成立」,且條件2「成立」時的程式碼 } else if(條件3) { 條件1、2「不成立」,且條件3「成立」時的程式碼 } .... else { 上述條件都「不成立」時的程式碼 } ``` :mega: else if()可視需要增加。 :::info EX_04:將成績轉換成等級制。 80以上 A,70 ~ 80 B,60 ~ 70 C,60以下 D,其它「錯誤」。 ::: ``` javascript= int main() { int score; cout << "請輸入成績:"; cin >> score; if (score >= 80) { cout << "A"; } ........ // 70~80,70<=score<80 是錯誤的語法 { ........ } ........ // 60~70 { ........ } ........ // 0~60 { ........ } else { cout << "輸入錯誤!"; } return 0; } ``` ``` javascript= int main() { int score; cout << "請輸入成績:"; cin >> score; if ........ // 成績大於100 或者 小於0 { cout << "輸入錯誤!"; } else { if (score>=80) { cout << "A"; } ........ // 70~80 { ........ } ........ // 60~70 { ........ } ........ // 0~60 { ........ } } return 0; } ``` ## 四、迴圈 ### 1. for 迴圈語法 ``` javascript for(變數初值;條件判斷;改變量) { 程式碼 } ``` :::info EX_05_1:印出 10 個 "hello"。 :mega: 除錯練習 (1) 設中斷點 (2) Debug (F8) (3) Debugging windows/Watches (4) Next line (F7) (5) Stop debugger Q2:i=i+3,會印出幾個hello,最後 i 會顯示多少? ::: ``` javascript= int main() { int i; // 區域變數 vs. 區塊變數 for (int i=1;i<=10;i++) for (i=1;i<=10;i=i+1) // 讓 i 從 1~10。for()後面不可加分號 { cout << "hello "; } cout << i; // Q1:i 會顯示多少? } /* i=i+1 i+=1 i++ */ ``` :::info EX_05_2:計算 n! (先完成1+2+...+n) ::: ``` javascript= int main() { int n,sum=....; // sum 初值設為 0 cout << "請輸入n:"; cin >> n; for ........ // 讓 i 從 1~n { ........ // 每次迴圈 sum=sum+i } // 複合指定運算子 += cout << sum; return 0; } ``` ### 2. 巢狀迴圈語法 ``` javascript for(變數1初值;條件1判斷;改變量) { for(變數2初值;條件2判斷;改變量) { 程式碼 } } ``` :::info EX_06_1:印出n列的直角三角形。 ![](https://i.imgur.com/63Q74NC.png) ::: ``` javascript= int main() { int n; cout << "請輸入n:" ; cin >> n ; for ........ // 總共n列 { for ........ // 星號的數量和列編號有關 { cout << "*"; } ........ // 印完一列要換行 } return 0; } ``` :::info EX_06_2:調整EX_06_1,印出金字塔形狀。 ![](https://i.imgur.com/d3yV7nC.png) ::: ``` javascript== int main() { int n; cout << "請輸入n:"; cin >> n; for ........ // 總共n列 { for ........ // 每列印星號之前先印「空白」 { cout << " "; } for (int j=1;j<= .... ;j++) // 星號的數量和列編號有關(1,3,5,7,9...) { cout << "*"; } ........ // 印完一列要換行 } return 0; } ``` :::info EX_06_3:調整EX_06_2,加上樹幹變成聖誕樹。([等差數列第n項公式](https://www.liveism.com/live-concept.php?q=%E7%AD%89%E5%B7%AE%E6%95%B8%E5%88%97%E7%AC%ACn%E9%A0%85%E5%85%AC%E5%BC%8F%E7%9A%84%E6%8E%A8%E5%B0%8E)) ![](https://i.imgur.com/2ZotMoT.png) ::: :::info EX_06 (Bonus):3層聖誕樹。 ![](https://i.imgur.com/aHbSuMI.png) [:grimacing: 偷看解答](http://cs.cysh.cy.edu.tw/computer_concept_108/christmas_tree.html) ::: ### 3. while 迴圈語法 ``` javascript while(條件判斷) // 條件為「真」的時候繼續執行 { 程式碼 } ``` ``` javascript= for (int i=1;i<=5;i++) { cout << "hello "; } cout << endl; int i=1; while (i<=5) { cout << "hello "; i++; } ``` :::info EX_07:while 存錢買手機。 ::: ``` javascript= int main() { int i=1, ......... ; while ........ // 錢沒存夠 { cout << "請輸入第 " << i << " 個月的存款: "; cin >> money; ........ // 把 money 加到 sum ........ // i+1 } cout << "存了 " << .... << " 個月,總共 " << sum; return 0; } ``` ``` javascript break:強制跳出「整個」迴圈 continue:強制跳出「此次」 迴圈,繼續進入下一次圈 ``` :::info EX_08:sqrt()實作。 ::: ``` javascript= int main() { int n; bool sol=false; cin >> n; for ........ // 只需檢測到 n/2 { if ........ // 如果i的平方等於n { cout << i; ........ // sol 設為 true,表示找到根 ........ // 跳出迴圈 } } if ........ // 沒有解,! -> not { cout << "只能求完全平方數的平方根!"; } return 0; } Q:4不行? ``` :::info EX_08 除錯練習。 ::: <pre style="color:#f7f7f7;font-size:xx-small;"> #include <iostream> using namespace std; int main() { int n; bool sol=false; cin >> n; for(int i=1;i<=n/2;i++) { if(i*i=n) { cout << i; sol=true; break; } if(!sol) { cout << "只能求完全平方數的平方根!"; } } return 0; } </pre> :::info EX_09:sqrt()實作 (以二分搜尋法實作) :mega: (1) [printf](https://openhome.cc/Gossip/CGossip/PrintfScanf.html)     (2) [科學記號表示法](http://notepad.yehyeh.net/Content/CPP/CH01/03DataType/1.php) ::: ``` javascript= int main() { double n,lower,upper,mid; // Q2 cin >> n; lower = 1; upper = n; mid = n/2; // mid*mid!=n? 當mid*mid和n的誤差 > 10^-13(數學寫法)時,就繼續逼進。(mid^2-n要取絕對值,需含入標頭檔cmath) while ........ // 上下界限的差 > 10^-13,就繼續逼進 { mid = ........ // mid 為上下界限的中間 printf("%.13f\n",mid); // 把每次的mid都印出來看看,需含入標頭檔 cstdio // Q2 if ( mid*mid > n ) // 如果中間數的平方 > n,解在lower~mid間 ........ // 將上限調為 mid else if ........ // 如果中間數的平方 < n,解在mid~upper間 ........ // 將下限調為 mid else break; } printf("經過了 %d 次運算,根號 %f 為 %.13f\n", cnt,n,mid); return 0; } Q:新增一個整數變數cnt,記錄總共做了幾次運算得解。 ``` ### 4. do..while 迴圈語法 ``` javascript do { 程式碼 }while(條件判斷); // 條件為「真」的時候繼續執行 ``` :mega: do while()後要加分號! :::info EX_10:sqrt()實作 ([以牛頓法實作](http://mathcenter.ck.tp.edu.tw/Resources/Ctrl/ePaper/ePaperOpenFileX.ashx?autoKey=55)) ::: ``` javascript= int main() { double n, a, b; cin >> n; a = n; do { b = ........ // 挑出的第1個近似值a之後,作一切線,切線和x軸的交點為b ........ // 下一次以此次的b繼續求切線和x軸的交點 } while ........ // b*b!=n? 當b*b和n的誤差>1e-13時,就繼續逼進 cout << b; return 0; } Q:a,b簡化只用一個變數。 ``` ## 五、陣列 ### 1. 陣列宣告 ``` javascript int arr[5]; // 宣告一個大小為5的int陣列 arr[0]=80; // 陣列的索引值由0開始 arr[5]=90; // 索引值0~4 int arr[5] = { 1, 3, 5, 7, 9 }; // 宣告陣列時設定初值 int arr[5] = { 1 }; // arr[0]初值1,其餘預設為0 int arr[] = { 1, 3, 5, 7, 9 }; // 陣列大小依初值自動計算 int arr2D[4][2]; // 宣告二維陣列(多維陣列) int arr2D[4][2] = { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } }; Q:如何建立可以儲存班上期中考成績的2維陣列? // arr2D[r][c]表示第 r 列,第 c 欄的值(類似英文書寫習慣) ``` :::info EX_11:考試成績存放在陣列,找出最高分。 ::: ``` javascript= int main() { int a[5]={87,61,92,83,95},max=-1; // 最大值的初值為一個比陣列值都小的數值 for ........ // 從頭看一遍 { if ........ // 如果陣列第i個位子的值 > max { ........ // max 換成陣列的值 } } cout << "最高分為 " << max << endl; return 0; } Q:如何找出最低分? ``` :::info EX_12:[ZeroJudge c067: 00591 - Box of Bricks](https://zerojudge.tw/ShowProblem?problemid=c067)。 ::: ``` javascript= int main() { int n; cin >> n; int h[n],sum=0,ave,mov=0; for(int i=0;i<n;i++) { cin >> h[i]; } for ........ { ........ // 把所有的牆高加總 } ........           // 算出牆高平均 for ........ // 把所有的牆看一遍 { if ........ // 如果牆高 > 平均 { ........ // 將(此牆高-平均)加總 } } cout << "The minimum number of moves is " << mov << endl; } ``` :::info EX_13_1:大樂透電腦選號。 :mega: [亂數觀念](https://blog.gtwang.org/programming/c-cpp-rand-random-number-generation-tutorial-examples/) ::: ``` javascript= int main() { ........ // 宣告一個大小6的num陣列 srand(16); // 設定亂數種子。srand(time(NULL)); 需含入標頭檔 ctime for ........ // 陣列的索引值由0開始,所以i初值要設為0 { num[....] = rand()....; // 隨機產生1~49間的數,需含入標頭檔 cstdlib // Q:50~100 } for ........ // 印出陣列裏的亂數 { cout << num[....] << " "; } return 0; } ``` :::info EX_13_2:大樂透電腦選號(解決數字重覆的問題)。 ::: ``` javascript= int main() { int num[6]; // 宣告一個大小6的num陣列 int mark[50]={0}; // 標記陣列的初值=0。50個空間,陣列索引值為0~49 int t; srand(16); // 設定亂數種子。srand(time(NULL)); 需含入標頭檔 ctime for (int i=0;i<6;i++) // 陣列的索引值由0開始,所以i初值為0 { do { t = rand()%49+1; // 隨機產生1~49間的數,暫放於t } while(........); // 如果mark陣列第t個位子為1,代表亂數重覆,再產生另一個亂數 ........ // 將產生的不重覆亂數記錄在num陣列 ........ // 將mark陣列第t個位子的值設為1,表示產生過t這個數字 } for (int i=0;i<6;i++) // 印出陣列裏的亂數 { cout << num[i] << " "; } return 0; } Q1:產生亂數後,檢查此數字是否重覆,如果重覆再產生一次,下列程式碼想法有何漏洞? for(int i=0;i<6;i++) { t=rand()%49+1; for (int j=0;j<i;j++) if (t==num[j]) t=rand()%49+1; num[i]=t; } Q2:t=rand()%5+1會發生什麼狀況?(陣列除錯練習) ``` :::info EX_13_3:大樂透電腦選號(將數字排序顯示-[Bubble Sort](https://medium.com/@mingjunlu/understanding-bubble-sort-7aa4567986ae)) :mega: 其它排序演算法 (1) [插入排序法(Insertion Sort)(1)](https://jason-chen-1992.weebly.com/home/-insertion-shell-sort) [(2)](https://kopu.chat/2017/06/22/插入排序insertion-sort/)、[選擇排序(Selection Sort)](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff) (2) [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms) ::: ``` javascript= // 此段程式碼置於EX_13_2第18行的位置(產生亂數後排序) for ........ // 6個數字排序只需5個循環 { ........ // 每次比較索引值0 1、1 2、2 3、3 4、4 5的數字 { if (num[....] > num[....]) // 如果左邊比右邊大 { ........ // num[j]和num[j+1]交換 ........ ........ } } } Q:for 內圈寫完後(將最大值移至最右的位子),複製貼上5次,程式碼會正確嗎? ``` ### 2. 二維陣列 :::info EX_14:求學測總分、平均、名次。 ::: ``` javascript= int main() { int score[4][8] = {{12,13,15,10,12,0,0,0},{15,13,15,15,14,0,0,0},{14,14,12,15,13,0,0,0},{11,10,12,12,10,0,0,0}}; int sum; for ........ // 4個人,列 { ........ // 計算每人總分之前,sum 要先歸0 // int sum=0;(每次都宣告一個新的變數) vs. sum=0;(把公用的變數清空) for ........ // 5科,欄 { sum += score[....][....]; } score[....][5] = sum; score[....][....] = sum/5; } // 先印出來看看 cout << "座號\t國文\t英文\t數學\t自然\t社會\t總分\t平均\t名次\n"; for (int i=0;i<....;i++) // 4個人,列 { ........ // 先印出座號 for (int j=0;j<....;j++) // 5科+總分、平均、名次,8欄 { cout << score[....][....] << "\t"; } cout << endl; } return 0; } ``` :::info EX_14 (Bonus):多加一個欄位求名次。 Hint:類似bubble sort的寫法。若此位同學的總分<p位同學,名次為p+1。 ::: ``` javascript= for ........ // 對第i個人求名次 { int p=1; // 每個人先預設為第1名 for ........ // 計算成績大於第i個人的人數,從頭比較每個人的總分 { if (score[....][....] < score[....][....]) // 別人的成績>第i個人的成績,名次就多1名 { p++; } } ........ // 記錄第i個人的名次 } ``` ## 六、函式 ### 1. 自定函式宣告語法 ``` javascript 回傳值的型態 函式名稱(變數型態 參數1,變數型態 參數2,...) { 程式碼 return 回傳值或運算式; } ``` :::info EX_15:[ZeroJudge b112: 5. 高中運動會](https://zerojudge.tw/ShowProblem?problemid=b112)。 以輾轉相除法求兩數的最大公因數(寫成函式),並用之來求4數的最大公因數。 [輾轉相除法](http://www.mathland.idv.tw/fun/euclidean.htm) [短除法找三數的最大公因數(數學方法)](https://www.junyiacademy.org/junyi-math/m4n/m4nyb-/mjnfs7b/v/XK_gpcahyTE) ::: ``` javascript= int gcd(int a,int b) { int r; do { r = a % b; // r 為 a 除以 b 的餘數 ........ // 下一次的 a 為 ? ........ // 下一次的 b 為 ? } while ( ........ ); // 當 ? 不為 0 時繼續做 ........ // 回傳 a,b 的最大公因數,a? b? r? // g=gcd(12,16) 函式除錯(Step into) } int main() { cout << gcd(12,16) << endl; // 先檢查函式有沒有寫對,gcd(12,16)->4 int a=400,b=200,c=150,d=625,g; g=gcd(a,b); // g 為 a,b 的最大公因數 ........ // g 再和 c 求最大公因數 ........ // g 再和 d 求最大公因數 cout << g; // cout << gcd(gcd(gcd(a,b),c),d); return 0; } ``` :::info EX_16 (Bonus):寫一函式可以計算n!,並以之求 $C(n,k)=\frac{n!}{(n-k)! * k!}$,例如C(4,2)=6。 ```javascript= int f(int n) { ........ # 計算 n! } int main() { cout << f(5) << endl; // 先檢查函式有沒有寫對,5!->120 int n,k; cin >> n >> k; cout << ........ return 0; } ``` ::: ### 2. 傳值(call by value)、傳參考(call by reference) :::info EX_17:將排序時用到的兩數交換程式碼,寫成函式。 ::: ``` javascript= void swap(int ....a, int ....b) // void 表示沒有回傳值 { int t; ........ ........ ........ cout << "函式內:"<< a << " " << b << endl; } int main() { int a=1,b=2; cout << "交換前:" << a << " " << b << endl; swap(a,b); cout << "交換後:" << a << " " << b << endl; return 0; } ``` ### 3. 遞迴 :mega: 問題的答案,可從同類的子問題(規模更小)得到。 :mega: 在函式之中呼叫函式自己本身,要有終止條件,不然會無窮遞迴下去。 :::info EX_18:[95數學學測填充題G](http://cs.cysh.cy.edu.tw/computer_concept_108/高中數學遞迴.xps) 用黑、白兩種顏色的正方形地磚依照如下的規律拼成若干圖形: ![](https://i.imgur.com/PrDcedl.jpg) 拼第95個圖需用到幾塊白色地磚。(478) ::: :::info EX_18 (Bonus):求費式數列第n項。 [費式數列遞迴式](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97) ::: ``` javascript= int brick(int n) { if ........ // if後只有一行,可省略{} ........ else return brick(n-1)+5; } int fib(int n) { if (n == 0) // n==0時終止,回傳0。if後只有一行,可省略{} return 0; else if ........ // n==1時終止,回傳1 ........ else ........ // 遞迴呼叫 } int main() { int n; cin >> n; cout << brick(n) << endl; // 5->28 cout << fib(n) << endl; // 5->5 return 0; } ``` :::info EX_19:以遞迴改寫 EX_15 高中運動會中的gcd函式。 ::: ``` javascript= ........ // 函式宣告,名稱為gcd,參數a,b { if ........ return ........ else return ........ } int main() { cout << gcd(12,16) << endl; // 先檢查函式有沒有寫對,gcd(12,16)->4 int num[8] = {400, 200, 150, 625, 600, 100, 15, 20}; int g = gcd(num[0], num[1]); for ........ // 從num[2]開始,都和g求gcd g = gcd(g, ....); cout << g; // ans->5 return 0; } ``` :::info EX_20:以遞迴函式計算 n 層香檳塔,總共有幾個杯子。 遞迴式 : f(n)=1 ,if n==1     f(n)=? ,if n>1 ![](https://i.imgur.com/uniXdVh.jpg =100x) ::: ``` javascript= int f(int n) { ........ } int main() { int n; cin >> n; cout << f(n); // 平面 4->10 // 立體 4->20 return 0; } ``` :::info EX_20 (Bonus):計算 n 層「三角錐形」香檳塔,總共有幾個杯子。 ( 第1層1個、2->3、3->6、4->10、5->15、第n層->?個杯子 ) [2017的世界紀錄總共杯子數量為50116](https://kknews.cc/zh-tw/food/3j4y43y.html),疊了幾層? ![](https://i.imgur.com/Faj13v9.png =200x) :::