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

Just use a stack for this problem:

#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;
}

Recursive code, see @bordertownmadman’s explanation:

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

If you use recursive thinking to solve it, it should be like this

Define a process called pairing and its steps

• Get personal gender
• If the gender is the same as the previous person, reconfigure this person (because it cannot be paired with the previous person, you can only hope for the next one)
• If the gender is different from the previous person, pair output
• Continue to take down the next one

Represented by algorithm

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)
        }
    }
}

Initial call (assuming the list must not be empty)

match(list.next())

Note, don’t underestimate list.next() 这个方法, it is the key to managing pointer movement. In addition, since the serial number needs to be output, special attention should be paid to saving the data and serial number

The recursive calling method does not use many loops. If you like to use loops, you can use the stack method instead of recursion (that is, derecursion, or expansion recursion)

I hope you can understand the algorithm and then write your own code to test it. If there is a problem with the test code, take it out and continue to analyze it for you.

js6 code

Because I don’t want to configure a C++ environment, I use js6 to write it, and try to be close to the C++ syntax (except for using Array.map() there - you can understand the meaning there

If you have the latest version of iojs, you can save it directly to a file and run it; if it is nodejs, you may need to add some parameters when running... But if you have a newer browser (Chrome, or IE11, etc.), You can paste and run it directly in the developer window of the browser.

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());
})();

Results

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