Codebar 程式酒吧

一座輕鬆學習程式的酒吧

0%

a229. 括號匹配問題

發表於 分類於 閱讀次數：

建議類題

a524. 手機之謎

解題思路

根據題意，我們要找出對於n個左括號和n個右括號來說，所有合法的，也就是說「任一點左括號數量皆大於等於右括號」的匹配組合。因為相信多數人和我一樣，沒辦法從題目敘述中找出規律，因此本題我們使用遞迴排除已經輸出的情況，列舉出所有的可能性。

想要了解什麼是遞迴，必須先知道有關函數的觀念。在a002. 簡易加法，我們曾經提過函式是一種可以執行特定功能的程式區塊。當我們呼叫函式時，電腦就會執行函式內的程式。那麼，如果我在函式內呼叫了這個函式本身，會發生什麼事情呢？因為每當電腦執行函式時，都會再次收到我們的函式呼叫，因此電腦將不斷重複執行這個函式。這就是遞迴，藉由在函式內呼叫函式本身，形成循環以重複執行程式。

以本題來說，假設我們今天有num組括號要匹配，可以想像成是有一個長度為 2 x num 的陣列，在這個陣列的每個項，我們都可以選擇要放左括號還是右括號。因此，我們宣告一個函式，讓他從第1項跑到第 2 x num 項。在討論每個項，或者說跑到每個節點時，我們都使用遞迴分別跑一次選擇左括號和右括號的情況，直到跑到最後一個節點，即跑完所有的匹配組合。

在確定所有可能的匹配組合都有被討論到後，接下來我們要為遞迴加上限制條件，將我們真正想要的匹配組合留下。首先，雖然我們在各個位子都有左括號和右括號兩種選擇，但因為括號是兩兩一組的，因此左括號和右括號的總數都不應超過num個，如果我們跑一跑發現左括號或右括號的總數超過num的話，就不用再跑下去了；再來，合法的匹配組合在任一點的左括號數量一定大於等於右括號，因此如果我們跑一跑發現左括號的數量小於右括號，代表這不是合法的匹配組合，也不用再跑下去了。如此一來，跑到最後的匹配組合，一定都是合法的，就可以放心輸出了！

注意事項

遞迴是一種重複執行程式的方法，概念是先宣告一個函式，藉由在函式內呼叫函式本身，讓程式不斷跑下去。和同樣是重複執行程式的迴圈不同的是，迴圈的每一次運行都是從頭開始，常用於重複執行指定的動作；而遞迴因為會返回距離最近的「節點」，可以跑過每個節點、每個選擇的所有可能性，完成具有「分支」的討論，進一步運用在深度優先演算法(DFS)上。因此，推薦大家在學習完函式與迴圈後，可以試著學習遞迴。

程式碼：C語言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
//宣告變數n，代表總共有幾組括號要匹配
//宣告變數num，令其值為2*n，代表總共有幾個位子要討論
int n, num;
//宣告一長度為30的陣列arr，代表可能的括號匹配組合
char arr[30];
//宣告回傳值為void型態（不回傳）的函式dfs，討論每一項的可能性
//宣告變數now，代表現在討論到第幾項，或者說跑到第幾個節點
//宣告變數left、right，分別代表現在左括號和右括號的數量
void dfs(int now, int left, int right) {
    //若左括號或右括號數量大於n，或是左括號數量小於右括號，皆為不合法的匹配組合，可以直接返回
    if(left > n || left < right)
        return;
    //若跑到第num個節點，而沒有被終止，代表這是合法的匹配組合，可以輸出
    /*在結尾補/0再輸出字串，比以for迴圈輸出字元陣列快*/
    if(now == num) {
        arr[num] = '\0'; 
        printf("%s\n", arr);
        return;
    }
    //若此節選擇的是左括號，將左括號數量加一後進入下一項的討論
    arr[now] = '('; 
    dfs(now+1, left+1, right); 
    //若此節選擇的是右括號，將右括號數量加一後進入下一項的討論
    arr[now] = ')';
    dfs(now+1, left, right+1);
}
//主函式
int main() {
    //使用EOF寫法讀取每次輸入的n值
    while(scanf("%d", &n) != EOF) {
        /*在這裡先把num算出來，每筆測資只需算一次，比每次遞迴時都將條件設為2*n快*/
        num = 2*n;
        //呼叫函式dfs，藉由遞迴跑過所有可能的括號匹配組合，再將合法的匹配組合輸出 
        dfs(0, 0, 0);
    }
    return 0;
}
相關文章