2016年5月17日 星期二

給新手的C++教學 (上冊) - 9. 函式 (Function)

回到「給新手的C++教學 (上冊)」

上一章

依照慣例,在本章依然要給你一個題目,然後你就會發覺需要學習某種新技能,才能有效率的寫出可以解決問題的程式碼 (?)

給你一個正整數$n$,請求出第$n$個卡特蘭數
提示:
第$n$個卡特蘭數$=C^{2n}_{n}-C^{2n}_{n+1}$
其中$C^{a}_{b}=\frac{a!}{b!(a-b)!}$
其中「$x!$」念作「$x$階層」,$x!=1*2*3*...*x=\prod_{k=1}^{x}k$

當然,$n$不能太大,否則會發生溢位 (overflow) 的情況 (甚麼是溢位?)
所以$n$的範圍會在$1\sim 6$內

卡特蘭數列:1、2、5、14、42、132、......

你的程式答對前6項了嗎?

參考程式碼:

#include<cstdio>
int main()
{
    int n;
    scanf("%d",&n);
    int a=1,b=1,c=1;
    int i=1;
    while(i<=2*n)
    {
        a=a*i;
        i=i+1;
    }
    i=1;
    while(i<=n)
    {
        b=b*i;
        i=i+1;
    }
    i=1;
    while(i<=2*n-n)
    {
        c=c*i;
        i=i+1;
    }
    int first=a/(b*c);
    a=1,b=1,c=1,i=1;
    while(i<=2*n)
    {
        a=a*i;
        i=i+1;
    }
    i=1;
    while(i<=n-1)
    {
        b=b*i;
        i=i+1;
    }
    i=1;
    while(i<=2*n-(n-1))
    {
        c=c*i;
        i=i+1;
    }
    int second=a/(b*c);
    printf("%d\n",first-second);
    return 0;
}

程式碼中,變數a、b、c分別表示$C^{a}_{b}$中的$a!$、$b!$、$(a-b)!$

當輸入$n=6$時,程式輸出第6個卡特蘭數「132」了!
你可能會覺得:程式碼好冗長呀~
然後心裡想說:等一下一定會教一個更簡單的方法
咦?XD

沒錯!
接下來,本章會教你,怎麼利用「函式 (Function)」來化簡你的程式碼!



你在算數學題目時,有用過「函數」嗎?
當我們遇到類似$y=x^3+3x+32$之類的方程式
我們可以直接令$f(x)=x^3+3x+32$
這樣一來,要表示「當$x=a$的時候,$y$的值」,我們就可以直接帥氣的使用「$f(a)$」來代替「$a^3+3a+32$」了
你看你看~「寫出『$f(a)$』」比「寫出『$a^3+3a+32$』」還要方便省力多了!
可以想像,聰明的運用「函數」可以大幅簡化你的計算過程!

當然,程式方面,也可以使用一樣的方式來簡化你的程式碼,真是太棒了!
(其實,程式的「函式」就是數學的「函數」,英文名稱都是「Function」)
趕快來看看怎麼用吧~
假設你想把函式的名稱取作「function_name」,它可以根據一個指定的int變數「a」,算出一個答案

int function_name(int a)
{
    你的程式碼
    return 算出來的答案;
}

這樣一來,如果把上述的數學題目轉換成程式題目:
令$f(x)=x^3+3x+32$,輸入$a$,請輸出$f(a)$
你的程式碼可以這樣寫:

#include<cstdio>
int f(int x)
{
    return x*x*x+3*x+32;
}
int main()
{
    int a;
    scanf("%d",&a);
    printf("%d\n",f(a));
    return 0;
}

使用「函式」的動作,我們稱作「呼叫 (Call)」
當一個函式需要額外的資訊來進行運算,我們會需要傳遞資訊 (例如「f(a)」中的「a」) 給這個函式,這些被傳遞的資訊,我們稱作「引數 (Argument)」
函式算出來的東西我們稱作「回傳值 (Return value)」,也就是程式碼中「return」後面接的東西
執行含有「return」的程式碼的動作,我們稱作「回傳 (Return)」。這時候,這個函式會立即整個結束執行,並將「回傳值」傳遞給呼叫這個函式的地方 (例如「printf("%d\n",f(a));」中的「f(a)」)

相信你已經知道要怎麼利用「函式」來化簡卡特蘭數的程式碼了
聰明的你應該知道
我們的程式碼會需要反覆執行類似下面這個動作:

int a=1,i=1;
while(i<=n)
{
    a=a*i;
    i=i+1;
}
然後把算出來的a拿來做其他事 

也就是:對於一個指定的正整數$n$,算出$n!$的值

那麼,何不乾脆寫成一個函式?
我們來把「算出$n!$的函式」命名作「Level」吧!

於是,我們就可以把程式碼改寫成這樣:

#include<cstdio>
int Level(int n)
{
    int a=1,i=1;
    while(i<=n)
    {
        a=a*i;
        i=i+1;
    }
    return a;
}
int main()
{
    int n;
    scanf("%d",&n);
    int first=Level(2*n)/(Level(n)*Level(2*n-n));
    int second=Level(2*n)/(Level(n+1)*Level(2*n-(n+1)));
    printf("%d\n",first-second);
    return 0;
}

哇賽,程式碼真的變簡單很多耶!
我們甚至省略了宣告a、b、c三個變數的過程!(分別表示$C^{a}_{b}$中的$a!$、$b!$、$(a-b)!$)
趕快來寫寫看吧~

當輸入$n=6$時,程式依然是正確地輸出「132」!

如果你夠挑剔,你可能還會覺得「每次都要把$a!$、$b!$、$(a-b)!$拿去算出$C^{a}_{b}$」好麻煩呀
能不能弄一個函式專門用來算「$C^{a}_{b}$」呢?
當然可以!
我來示範給你看:

#include<cstdio>
int Level(int n)
{
    int a=1,i=1;
    while(i<=n)
    {
        a=a*i;
        i=i+1;
    }
    return a;
}
int C(int a,int b)
{
    return Level(a)/(Level(b)*Level(a-b));
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",C(2*n,n)-C(2*n,n+1));
    return 0;
}

你也來練習看看吧!
當輸入$n=6$時,程式仍然是正確地輸出「132」!
你可能會發現:「咦?從原古時代就出現的『int main()』和函式長得好像呀」
沒錯,「main」本身就是一個函式!
這個函式的功能就和我們自己創造的函式一模一樣
那麼,這個「main函式」甚麼時候會被用到呢?
就是程式開始執行的時候

電腦第一件事就是找出名稱為「main」的函式,並開始執行這個函式的內容
因此,程式碼中不能沒有名稱為「main」的函式,否則電腦會說你的程式碼寫錯了 (不信嗎?把「main函式」改成「mian函式」再按鍵盤上的「F11」看看)

那麼「main函式」會回傳一個「0」,代表甚麼意思呢?
為甚麼電腦總是會需要main函式回傳一個數字「0」呢?
其實,別無他意,回傳值為0代表「程式正常執行完畢」
當電腦發現某個程式的「main函式回傳值」不是0的時後
代表這個程式執行到一半就發生錯誤了!

我們讓程式執行「除以零」的動作,程式就出錯了
程式出錯的方式有很多種,每一種錯誤都會導致程式回傳特定的非零數字
當我們點選「關閉程式」之後,可以看到程式的回傳值 (僅限用Dev-C++寫出來的終端機程式)
例如這個「除以零」的錯誤會得到回傳值「3221225620」

會不會覺得程式越來越好玩了呢?
有沒有寫了一堆程式碼超長的程式呢?
趕快去利用「函式」來化簡它吧!

下一章

感謝:多多學弟
(版權所有 All copyright reserved)

9 則留言:

  1. 函式裡面麼塞陣列啊?(我是指把陣列當變數)

    回覆刪除
    回覆
    1. 嗨~
      直接舉個例子好了:
      #include<cstdio>
      int Sum(int n,int s[])
      {
          int answer=0;
          for(int i=0;i<n;i++)
          {
              answer=answer+s[i];
          }
          return answer;
      }
      int main()
      {
          int s[5];
          for(int i=0;i<5;i++)
          {
              s[i]=i;
          }
          printf("%d\n",Sum(5,s));
          return 0;
      }

      有不懂歡迎再問哦~^_^

      刪除
  2. 請問一下
    在算卡特蘭數時,為什麼到第7位以後就會溢位呢?
    明明第7位是429、第8位是1430,兩個數都沒有很大啊??

    回覆刪除
    回覆
    1. 因為卡特蘭數的第7項要計算14!(=87178291200),溢位囉~XD

      刪除
    2. 喔喔所以是過程中數字太大,而不是結果太大對吧XD
      那有沒有辦法算這些大數的功能呢

      刪除
  3. 想請問一下
    若程式最後沒有寫return 0
    會怎麼樣嗎??

    回覆刪除
    回覆
    1. 只能說,絕大部分情況下不會怎麼樣。但如果您的程式被另一個程式監控,您的程式執行結果(main函式的回傳值)就會影響到另一個程式的行為(通常0代表正常,非0代表有錯誤)。沒有加return 0好像它也會自動幫你return 0的樣子,不過在C語言就不會囉~而且不一定所有的C++編譯器都有依照規定設計(如自動return 0)

      總之
      加了return 0保證沒事
      不加,也可以,但潛在的風險請自行負責XD

      刪除
  4. 想問一下
    我寫了C幾取幾的程式
    main function裡面
    是要先cin a、b才能寫combination嗎?
    為什麼不行顛倒呢?

    #include <iostream>
    using namespace std;

    int Level(int n)
    {
        int i, level = 1;
        for (i = 1; i <= n; i++)
            level *= i;
        return level;
    }

    int main(int argc, char **argv)
    {
        int combination, a, b;

        cin >> a >> b;
        combination = (Level(a) / (Level(b) * Level(a-b)));
        cout << combination << endl;
    }

    回覆刪除
    回覆
    1. 這該怎麼解釋呢...XD
      要先設定好a、b的值,拿a、b來做計算的結果才是正確的呀~

      刪除

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原