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
完美匹配，没一个落下的