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

Question

OpenJudge上的一道题， 遇到的问题是Wrong Answer，不知道是哪个地方考虑不周没想到。 具体题目： 在幼儿园中，老师安排小朋友做一个排队的游戏。首先老师精心的把数目相同的小男孩和小女孩编排在一个队列中，每...

PHP中文网 · Answer

Just use a stack for this problem:

#include 
#include 

int judge (char *str)
{
	std::stack 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
", cur, *ind);
                *ind += 1;
        }
        return 0;
}

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

大家讲道理 · Answer

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