--- ###### tags: `課程` ---  ---- Function Recursion === ## 課堂講義 https://reurl.cc/LdEQYa ## 寒假營隊IG連結 https://reurl.cc/2o2XzO  ---- ## 資研數學小教室！ $f(x,y) = 3 x^x - \frac{x}{\frac{1}{y}} + y + 2$ $f(x) = ax+b$ ---- → 函式就是一種 $f(x)$ 給定一些數字 就會返回一些數值 ---- 函式分為2種類型: 1. 內建函式 ex. max(), min(), sqrt() 2. 自訂函式 ex. int haha(), void lalala() --- ## 內建函式 ---- ```cpp= #include<函式庫名稱> 例如: #include<iostream> 就可以使用 cin>> cout<< #include<math.h> 就可以使用 sqrt ( x ) x的開根號值 pow (x, y) x 的 y 次方 #include<algorithm> 就可以使用 sort(arr, arr+n); #include<bits/stdc++.h> 萬用標頭檔 ``` ---- ## 常見內建函式 ---- ### 有回傳值函式 ```cpp= #include<bits/stdc++.h> using namespace std; int main() { int a, b; cout << sqrt(a) << endl; //開根號 cout << pow(a, b) << endl; //開次方 cout << __gcd(a, b) << endl; //最大公因數 cout << __lg(a) << endl; //log cout << max(a, b) << endl; //最大值 return 0; } ``` ---- ### 無回傳值函式 ```cpp= int main(){ memset(arr, 0, sizeof( arr )); //將陣列arr歸零 sort(arr, arr + n); //排序陣列 cout << upper_bound(arr, arr+n, x) - arr << endl; //搜尋數值x在排序後的陣列第幾個 return 0; } ``` ---- ## 主函式 main() ```cpp= #include<iostream> using namespace std; int main(){ ...... return 0; } ``` --- ## 自訂函式 ---- - 宣告位置：使用它之前 - 宣告方式 ```cpp= 回傳型態 函數名稱(引數型態 引數名稱1, ..., 引數型態 引數名稱n){ 要做的事情; return xxx;(如果有回傳值) } int times_num(int a, int b){ //有回傳值 int k = a * b; return k; } void say_hi(){ //無回傳值 cout << "hi" << endl; return; } ``` ---- ### 題目 設計一個 power() 的函式，計算ｘ的ｙ次方 input : 2 10 output : 1024 ---- ### 提示 power() 函式要使用for迴圈 計算ｘ的ｙ次方的值要設定初值＝1 ---- ### 解答 ```cpp= #include<iostream> using namespace std; float power(float x,float y){ float sum = 1; for(float i=0; i<y; i++) sum = sum * x; return sum; } int main(){ float a, b, ans = 0; cin >> a >> b; ans = power(a, b); cout << ans << endl; return 0; } ``` --- ### JoJo乘法表  ---- ```cpp= #include <bits/stdc++.h> using namespace std; int muti(int a, int b) { return a * b; } void print_n_to_9n(int n) { for (int i = 1; i < 10; i++) cout << setw(4) << muti(i, n); cout << endl; } void gogo() { for (int i = 1; i < 10; i++) print_n_to_9n(i); return; } int main() { gogo(); return 0; } ``` --- ## 常見錯誤範例 ---- ```cpp= void swap(int a, int b, int c){ int tmp = a; a = b; b = tmp; return a; } ``` ---- ### 修正 ```cpp= void swap(int a,int b){ int tmp = a; a = b; b = tmp; return; } ``` ---- ```cpp= int sum(int a, int b, int c){ int ans = a + b + c; return; } ``` ---- ### 修正 ```cpp= int sum(int a, int b, int c){ int ans = a + b + c; return ans; } ``` ---- ## 全域宣告 ```cpp= #include<iostream> using namespace std; int a, b; int sum(int c, int d){ return a+b; } int main(){ cin>>a>>b; cout<<sum(a, b); return 0; } ``` --- ## 遞迴 ---- ### 費氏數列 常常可以看到一個式子裡面帶有函數本身的東西 $f(x) = f(x-3) + 2$ $a_n = a_{n-1} + a_{n-2}$ 或是更複雜的函式等等 那這是時候就能用遞迴解決問題！ ---- 在費氏數列中 你可以想像$f(x)$是$a_x$ 所以要計算$f(x)$的時候 可以先行計算$f(x-1),f(x-2)$ 再把他們相加的數值 就會有答案 $→f(x) = f(x-1) + f(x-2)$ **注意邊界條件 $a_1 = a_2 = 1$** ---- ### code ```cpp= int fab(int a) { if (a == 1 || a == 2) return 1; else return fab(a - 1) + fab(a - 2); } int main() { int n; cin >> n; cout << fab(n) << endl; return 0; } ``` ---- ## 小試身手 給定$n$ 請輸出$n!$的值 input: 6 output: 720 ---- ### - 觀察後可以發現 - $x! = x \cdot (x-1)!$ - 所以設定$f(x) = x!$ - 也就會有$f(x) = x\cdot f(x-1)$ - 特別注意1! = 1 的邊界條件 ---- ```cpp= // fac(x)代表x階乘的值 int fac(int a){ if(a == 1) return 1; else return a * fac(a-1); } int main() { int n; cin>>n; cout << fac(n) << endl; return 0; } ``` --- ## 關於function ---- - 為什麼要學 function - 工作區段分明 - 遞迴 - 簡化程式碼 - 注意事項 - 注意邊界條件 - 回傳值型態 - 注意遞迴結束條件 --- ## 題目們 --- ## 給定x, y, n 代表 $a_n = x \cdot a_{n-1} + y \cdot a_{n-2}$ $a_1, a_2 = 1$ 求出$a_n$? ---- ### 跟前面費氏數列類似 設定$f(x)$是$a_x$的值 就會有$f(x) = x\cdot f(x-1) + y\cdot f(x-2)$ 這次要注意x, y是會使用到的數據 可以寫在函式引數裡面或是全域 ---- ### code ```cpp= int fun(int a, int x, int y) { if (a == 1 || a == 2) return 1; else return x * fun(a - 1, x, y) + y * fun(a - 2, x, y); } int32_t main() { int n, x, y; cin >> n >> x >> y; cout << fun(n, x, y) << endl; return 0; } ``` --- ## 找錢 ---- 給定n 請問能用多少種組合湊出n元 input: 13 output: 13 * 1 8 * 1 + 1 * 5 3 * 1 + 2 * 5 3 * 1 + 1 * 10 ---- ## code --- ## 猜猜我是誰 ```cpp= #include <iostream> int cnt, muti = 1; int32_t main() { return (cnt < 5 ? (muti *= ++cnt), main() : (std::cout << muti << '\n', 0)); } ```