C++程式設計教學(五)-函式與遞迴

你有遇過雖然重複卻無法使用迴圈的時候嗎?如果沒有,請見以下範例。

stable_sort(dt,dt+n,[](int a,int b){
    int ctA=0,ctB=0;
    while(a>=1){
        if(a%2==1){
            ctA++;
        }
        a/=2;
    }
    while(b>=1){
        if(b%2==1){
            ctB++;
        }
        b/=2;
    }
    return ctA<ctB;
});

藍色部分是引用c++的函式庫,先不用理會。看看橘色部分。有兩個 while 迴圈,幾乎在做一樣的事情。這時怎麼改?這就要用到函數了!

int ct(int a){
    int ctA=0;
    while(a>=1){
        if(a%2==1){
            ctA++;
        }
        a/=2;
    }
}

stable_sort(dt,dt+n,[](int a,int b){
    int ctA=ct(a),ctB=ct(b);
    return ctA<ctB;
});

簡潔了許多,然而,看起來似乎只有一個變數阿!以下才是真正的教學。

函式 ( function ) 在程式設計中有著至關重要的地位。事實上函式的宣告與變數有幾分相似。請看以下範例。

int db(int a){
    return a*2;
}
//函數通式,注意傳入的參數可以有多個(不只兩個),但每個前面都要加入型態名稱
<回傳值變數型態> <函式名>(<要傳入的變數型態> <變數名>,<變數型態> <變數名>){
    <程式碼>
    return <變數>
}

而遞迴則是在函式中呼叫自己,來達成更進階的功能。以費式數列為例。
A1=1, A2=1, An=An-1+An-2 if(n>2) 寫作程式即為。

int f(int n){
    if(n==1){
        return 1;
    }else if(n==2){
        return 1;
    }else{
        return f(n-1)+f(n-2);
    }
}

這裡先講個大概,後續在 DP 還有更多技巧。
下回會說陣列~

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *