changed 4 years ago  
Linked with GitHub

函式與遞迴

2021/10/22 電算社第五堂社課

函式

火龍果不會算術，他會把8 * 6 寫成 56 (?
為了避免以後他還是運算錯誤
你可以幫他寫一個可以算出
\(f(n)= n^2 + 2n -1\) 的程式嗎:D

或許你會這樣寫









#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)\)









#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;
}

是不是覺得很麻煩呢，
重複的東西一直寫到，
只是帶入的數字不一樣，
卻要重複寫一次類似的東西，
這時候就可以使用函式了喔。

名詞解釋

  • 引數：函式執行時需要輸入的參數
  • 回傳值：函式執行完後回傳給呼叫該函式的地方的值，該值的資料型態會被放在函式名字之前，但不一定每個函式都要有回傳值






// type 為回傳值的型態 ， name為函式名稱
type name(type1 name1, type2 name2, ... )
{
    //函式會做的事
    return a; // 回傳a，同時代表該函式的結束，a的型態為type
}

回到剛剛的題目












#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乘積














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：不回傳














void func(int n)
{
    cout << n; 
    return; //終止函式 （可以省略）
    // void代表return後面沒有回傳值
}

int main()
{
    int a;
    cin >> a;
    func(a);    
}

main也是函式







int main()
{
    // main本身也是函式，但它前面常用int
    return 0; //可以省略
    
}

在函式裡面作運算不會影響到函式外的數值，
儘管函式內的東西和main裡面有相同名稱。



















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並改值
或把變數開成全域變數















int plus(int a)
{
    a += 2;
    cout << a;
    return a;
}

int main()
{
   int a;
   cin >> a;
   a = plus(a);
   cout << a;
}

遞迴

遞迴就是重複執行的函數
有兩個部份：

  1. 結束╱繼續的條件
  2. 函數本身的執行內容

你知道費波納契數列嗎?
就是那個生一堆

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
的故事
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}\)

實作出來長這樣





















#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

















//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; 
}

















//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

























// 非遞迴版
#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;
}
























#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 費氏數列
ZeroJudge : a044 空間切割
ZeroJudge : e357 遞迴函數練習

Select a repo