C++递归调用基础编程问题

Question

OpenJudge上的一道题，
遇到的问题是Wrong Answer，不知道是哪个地方考虑不周没想到。

---

具体题目：
在幼儿园中，老师安排小朋友做一个排队的游戏。首先老师精心的把数目相同的小男孩和小女孩编排在一个队列中，每个小孩按其在队列中的位置发给一个编号（编 号从0开始）。然后老师告诉小朋友们，站在前边的小男孩可以和他后边相邻的小女孩手拉手离开队列，剩余的小朋友重新站拢，再按前后相邻的小男孩小女孩手拉 手离开队列游戏，如此往复。由于教师精心的安排，恰好可以保证每两个小朋友都能手拉手离开队列，并且最后离开的两个小朋友是编号最小的和最大的两个小朋 友。（注：只有小男孩在前，小女孩在后，且他们两之间没有其他的小朋友，他们才能手拉手离开队列）。请根据老师的排队，按小女孩编号从小到大的顺序，给出 所有手拉手离开队列的小男孩和小女孩的编号对。

---

样例输入

((()(())())(()))

样例输出

2 3
5 6
4 7
8 9
1 10
12 13
11 14
0 15

我的代码：

#include<iostream>
using namespace std;

char judge(char c[]) {
    int i = 0 ;
    int j=0, k=0;
    char *sptr;
    sptr = c;

    while (sptr[i] != ')'&&i<101) {
        i++;
    }       
    c[i] = ' ';//此时输出的是遍历过来的第一个右括号，改为空格
    k = i;//存放该右括号位置

    while (sptr[i] != '(') {
        i--;
    }
    c[i] = ' ';//此时输出的是从获取的右括号起倒数过来的第一个左括号，改为空格
    j = i;//存放该左括号位置


    cout << j << ' ' << k << endl;
    for (int y = 0; y <= k; y++) {//判断是否还有剩余
        if (c[y] != ' ') {
            break;
        }
        else {
            return 0;
        }
    }
    return judge(c);
}




int main() {
    char c[101];
    cin.getline(c, 101,'\n');
    judge(c);

    return 0;
}

Answer 1

這個問題用一個stack就好了:

#include <iostream>
#include <stack>

int judge (char *str)
{
	std::stack<int> mystack;
	int ind = 0;
	while(*str){
		if(*str == '(')
			mystack.push(ind);
		else{
			if(mystack.empty())
				return -1;
			cout << mystack.top() << ' ' << ind << endl;
			mystack.pop();
		}
		ind++;
	}
	return 0;
}

遞歸代碼, 見 @邊城狂人 的解釋:

int
judgeInt(const char *str, int cur, int *ind)
{
        int i = *ind;
        if (!*(str + i))
                return -1;
        if (*(str + i) == '(') {
                *ind += 1;
                judgeInt(str, i, ind);
                judgeInt(str, cur, ind);
        } else {
                printf("%d %d\n", cur, *ind);
                *ind += 1;
        }
        return 0;
}

int
judge(const char *str)
{
        int ind = 1;
        return judgeInt(str, 0, &ind);
}

Answer 2

如果用遞歸的思想來解決，應該是這樣

定義一個過程，叫配對，其步驟

• 取得一下個人的性別
• 如果性別與上一個人相同，對這個人進行重新配置（因為無法與上一個人配對，只能寄希望於下一個）
• 如果性別與上一個不同，配對輸出
• 繼續取下一個

用演算法表示

list = 所有人（按顺序）

match(first) => {
    next = list.next()

    // 主要是检查 list 是否取完值
    if (next is null) {
        print("{first} 没得配了")
        return
    }

    if (first.sex == next.sex) {
        // 性别一致，开始新的匹配
        match(next)

        // 人家配完走了，再尝试配这个人
        match(first)
    } else {
        // 配上了，走人
        print(first, next)

        // 后面的人还要继续配的
        newFirst = list.next()
        if (newFirst is null) {
            print("没得配了，全部配完")
        } else if (newFirst is 男) {
            match(newFirst)
        }
    }
}

初始呼叫（假設 list 一定不空）

match(list.next())

注意，不要小看了 list.next() 这个方法，它是管理指標移動的關鍵。另外，由於需要輸出序號，對資料和序號的保存也要特別注意

遞歸的呼叫方法不會用到很多循環，如果你喜歡用循環，可以採用棧的方式而不是用遞歸（即解遞歸，或者叫展開遞歸）

演算法希望你能看懂，然後自己寫程式碼試驗。如果試驗代碼有問題再拿出來，繼續幫你分析。

js6 程式碼

因為不想去配 C++ 的環境，所以用 js6 來寫，盡量注意靠近 C++ 語法了（除了用 Array.map() 那裡——那裡能明白意思就對了

如果你有iojs 的最新版本，直接儲存成檔案可以運行；如果是nodejs，可能在運行時候需要加一些參數…不過如果你有比較新的瀏覽器（Chrome，或IE11 之類），直接在瀏覽器的開發者視窗可以直接貼上運行。

javascript(function() {
    "use strict";

    var list = {
        data: (function(s) {
            // 定义一个 Item 类，用于保存数据和索引号
            class Item {
                constructor(v, i) {
                    this.value = v;
                    this.index = i;
                }

                // 检查是否可以和另一个 Item 对象配对（男女手拉手）
                isMatch(another) {
                    return this.value != another.value;
                }

                // 检查是否男孩（前面的男孩可以后边相邻的女孩，主动方）
                isFirstable() {
                    return this.value === "(";
                }

                toString() {
                    return this.value === "(" ? `${this.index}:${this.value}` : `${this.value}:${this.index}`;
                }
            };

            // 将输入拆分成数据，再构建一组对应的 Item 对象
            // 返回的是 Item[]
            return s.split("").map(function(v, i) {
                return new Item(v, i);
            });
        })("((()(())())(()))"),

        // 下一个 index
        index: 0,

        // 下一个是否男孩（主动方）
        isNextFirstable() {
            return this.data[this.index].isFirstable();
        },

        // 找到下一个人（同时移动索引号）
        next() {
            return this.data[this.index++];
        },

        // 是否已经找完所有人
        isEnd() {
            return this.index >= this.data.length;
        }
    };

    function match(left) {
        if (list.isEnd()) {
            console.log(`悲催的 ${left.toString()}`);
            return;
        }

        var next = list.next();

        if (left.isMatch(next)) {
            // 既然已经配上对了，祝福他们……
            console.log(`${left.toString()}--${next.toString()}`);

            // 如果找完了人就拉倒
            if (list.isEnd()) {
                console.log("完美匹配，没一个落下的");
                return;
            }

            // 如下一个是男孩，递归检查配对；女孩就算了，等着给男孩子拉手吧
            if (list.isNextFirstable()) {
                match(list.next());
            }
        } else {
            // left 与 next 不能配对的情况，这个 next 一定是个男孩
            // 因为是女孩就配上了嘛
            // 所以递归配这个新发现的男孩
            match(next);

            // 后面该配的都配完了再试试当前这个能配上不
            match(left);
        }
    }

    // 一切都从这里开始，从第 1 个人开始
    match(list.next());
})();

結果

2:(--):3
5:(--):6
4:(--):7
8:(--):9
1:(--):10
12:(--):13
11:(--):14
0:(--):15
完美匹配，没一个落下的