函式與遞迴 - HackMD

# 函式與遞迴 ## 2021/10/22 電算社第五堂社課 --- ## 函式 ---- 火龍果不會算術，他會把8 * 6 寫成 56 (? 為了避免以後他還是運算錯誤你可以幫他寫一個可以算出 $f(n)= n^2 + 2n -1$ 的程式嗎:D ---- 或許你會這樣寫 ```cpp= #include<iostream> using namespace std; int main(){ int n; cin >> n; cout << n * n + 2 * n - 1; return 0; } ``` ---- 但當你需要使用很多次怎麼辦呢例如我想要知道輸入兩個數字$n_1, n_2$ 然後算出$f(n_1) - f(n_2)$ ---- ```cpp= #include<iostream> using namespace std; int main(){ int n1, n2; cin >> n1 >> n2; cout << (n1 * n1 + 2 * n1 - 1) - (n2 * n2 + 2 * n2 - 1); return 0; } ``` ---- 是不是覺得很麻煩呢，重複的東西一直寫到，只是帶入的數字不一樣，卻要重複寫一次類似的東西，這時候就可以使用函式了喔。 ---- ### 名詞解釋 * 引數：函式執行時需要輸入的參數 * 回傳值：函式執行完後回傳給呼叫該函式的地方的值，該值的資料型態會被放在函式名字之前，但**不一定每個函式都要有回傳值** ```cpp= // type 為回傳值的型態， name為函式名稱 type name(type1 name1, type2 name2, ... ) { //函式會做的事 return a; // 回傳a，同時代表該函式的結束，a的型態為type } ``` ---- 回到剛剛的題目 ```cpp= #include<iostream> using namespace std; int f(int n){ return n * n + 2 * n - 1; } int main(){ int n1, n2; cin >> n1 >> n2; cout << f(n1) - f(n2); return 0; } ``` ---- ### 函式的功能當你有某個程式會重複使用到時，使用函式可以讓你的程式碼更簡潔。或是當你想把一個功能拉出主程式時會用到！ --- ## 寫法範例輸入a,b 回傳a,b乘積 ```cpp= int func(int n , int m) { // n1,m1為我在呼叫這個函式的時候，它的值分別為a , b // 中間用 , 隔開 return n * m; } int main() { int a , b; cin >> a << b; cout << f(a , b); } ``` ---- void：不回傳 ```cpp= void func(int n) { cout << n; return; //終止函式（可以省略） // void代表return後面沒有回傳值 } int main() { int a; cin >> a; func(a); } ``` ---- main也是函式 ```cpp= int main() { // main本身也是函式，但它前面常用int return 0; //可以省略 } ``` ---- 在函式裡面作運算不會影響到函式外的數值，儘管函式內的東西和main裡面有相同名稱。 ```cpp= void plus(int a) { a += 2; cout << a << " "; } int main() { int a; cin >> a; cout << plus(a); } /* 輸入2 ，輸出4 2 因為plus(a) 裡面的a只是把數值複製到函式所以a再函式作加減乘除，不會對main裡面的a有所影響如果要改變a，要把a return 並把main的a 改為plus(a) */ ``` ---- 如果要作改變要return並改值或把變數開成全域變數 ```cpp= int plus(int a) { a += 2; cout << a; return a; } int main() { int a; cin >> a; a = plus(a); cout << a; } ``` --- ## 遞迴遞迴就是重複執行的函數有兩個部份： 1. 結束╱繼續的條件 2. 函數本身的執行內容 ---- 你知道費波納契數列嗎? 就是那個生一堆:rabbit:的故事 1, 1, 2, 3, 5, 8, .... $a_{n-2}$, $a_{n-1}$, $a_n$ 你會得到一個關係式：$a_n = a_{n-1} + a_{n-2}$ ---- 你未來一定會遇到一個時候會有人要你寫出算費式數列第 $n$ 項的Code(像現在:D) 那你要怎麼寫哩? ---- 邏輯：我們知道第一項跟第二項是1 如果 $n$ 為 $1$ 或 $2$ ，就回傳 $1$ 其他的 $n$ 我們就一直利用 $a_n = a_{n-1} + a_{n-2}$ ---- 實作出來長這樣 ```cpp= #include<iostream> using namespace std; int Fibonacci(int n){ //n是要求第n項的意思 if(n == 1 || n == 2){ return 1; } else{ return Fibonacci(n-1) + Fibonacci(n-2); } } int main(){ int n; cin >> n; cout << Fibonacci(n) << endl; return 0; } //輸入：6 //輸出：8 ``` --- 之後你會遇到一些一樣需要遞迴的東西例如 Bottom_Up, Top_Down ---- 求費氏數列第i項，可以用迴圈或者是函式做遞迴。以函式寫法稱為top_down，以迴圈寫法稱為bottom_up。 ex 輸入：6╱輸出：8 ---- ```cpp= //top_down #include<iostream> using namespace std; int f(int n)//n是要求第n項的意思 { if(n == 1 || n == 2) return 1; else return f(n-1) + f(n-2); } int main() { int n; cin >> n; cout << f(n) << endl; } ``` ---- ```cpp= //botton_up #include<iostream> using namespace std; int main(){ int n; cin >> n; int f[n + 1]; //多一項，讓項數變成1 ~ n，較直觀 f[1] = f[2] = 1; for(int i = 3; i <= n; i++){ f[i] = (f[i ‐ 1] + f[i ‐ 2]); } cout << f[n]; } ``` --- ### 小練習 ---- 試試用函式和遞迴做做 3n+1 吧當某一個數是奇數，就對他乘以三再加一如果是偶數，就對他除以二如此循環，最終都能得到1 試著輸出進行的過程吧 ---- 輸入說明：輸入一個整數$n$ 輸出說明：輸出$3n+1$進行的過程，每個數字用一個空格隔開範例輸入：5 範例輸出：5 16 8 4 2 1 ---- 我是防雷頁:D ---- ```cpp= // 非遞迴版 #include<iostream> void N(int n){ while(n != 1){ if(n % 2 == 0){ n /= 2; cout << n << endl; } else{ n = 3 * n + 1; cout << n << endl; } } cout << n; return; } int main() { int n; cin >> n; N(n); return 0; } ``` ---- ```cpp= #include<iostream> using namespace std; void N(int n){ cout << n << ' '; if(n == 1){ return; } else{ if(n % 2 == 0){ N(n/2); } else{ N(3 * n + 1); } } return; } int main(){ int a; cin >> a; N(a); return 0; } ``` --- ### OJ練習 [GreenJudge : b022 費氏數列](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b022) [ZeroJudge : a044 空間切割](https://zerojudge.tw/ShowProblem?problemid=a044) [ZeroJudge : e357 遞迴函數練習](https://zerojudge.tw/ShowProblem?problemid=e357)