7

需要说明的是，这不是家庭作业，我在自己的时间学习CS！

我最近购买了查尔斯·菲利普斯 (Charles Phillips) 写的一本名为“逻辑思维的 50 个谜题”的书。我启动了其中一个，我突然想到我可以使用递归来解决问题。这是（转述的）问题：

在每个空格中插入一个数学运算符（+、-、÷、x）来求解方程：

6 _ 3 _ 5 _ 7 _ 4 _ 8 = 13

我的理解是，为了使用递归解决这个问题，我首先需要确定一个基本情况。但是，我在这样做时遇到了麻烦。

所以我的问题是，什么是可能的基本案例，我应该如何开始实施它？递归函数会是什么样子（参数、返回类型等）？（代码很有帮助）！

这就是我到目前为止所拥有的：我认为几乎可以工作

请参阅我的答案以获取实施

注意我正在使用Java

4

4 回答 4

2

基本情况是所有空白都用运算符填充。您可以使用深度优先回溯搜索来解决此问题：

algorithm dfs(i):
    if i == num_blanks:  # base case: filled in all the blanks
        if equation_solved():
            return the operators you filled in
    else:
        for op in (+, -, ÷, ×):
            blank[i] = op
            if dfs(i + 1) returns a solution:
                return that solution
            blank[i] = _     # restore to previous state

这是一种搜索整个组合空间的递归方式。（我希望这不会破坏你的练习；我用伪代码编写了它，以便将实现留给你。）

于 2013-01-26T14:46:41.290 回答
2

我认为停止条件应该意味着满足等式：填写所有运算符，以及导致适当相等的操作。

我会将等式表示为解析树，叶子作为数字，父母作为运算符。树自然适合递归，因为它是一种分层数据结构。

做一个运算符假设，其中根操作是减号，右孩子是期望值 (13)，左孩子是左边。添加一个运算符，评估树，然后回溯，直到满足您的停止条件。

于 2013-01-26T14:48:58.623 回答
1

您可以将其视为决策树。

              6
        /    /    \    \
        +   -     *    /
        3                    Assuming you choose + for the first operator
/    /       \    \
+   -        *    /
5   5        5    5
    ^             ^
    6 + 3 - 5     6 + 3 / 5

然后，您可以使用图遍历算法（例如 DFS 或 BFS）来检查结果。两者都是自然递归的。

于 2013-01-26T15:44:53.790 回答
1

这是我最终得到的实现，但首先是对问题解决方案的解释：

  • 基本情况（如 larsmans 和 Jan Dvorak 所说）是所有“_”都用运算符（例如“+”）填充。
  • 该函数调用自身，每次都添加另一个参数，直到达到不正确的基本情况（例如“6+3+5+7+4-8=13”）或得到正确答案。
  • 如果基本情况不正确，那么我们会不断弹出级别，我们可以使用可以更改的运算符来达到某个级别。

这是代码：

class GapFill {

    private static String numbers; //E.g. 6_5_4=15
    private static String[] blank; //Array of operators to go in the blanks

    //Where:
    //p = plus
    //m = minus
    //d = divide
    //t = times
    private static String[] operators = {"p", "m", "d,", "t"};

    public static void main(String[] args) {
        numbers = args[0];
        blank = new String[numbers.split("_").length - 1];
        if(dfs(0)) { //If a solution was found
            int count = 0;
            while(numbers.indexOf("_")!=-1) {
                int index = numbers.indexOf("_");
                numbers = numbers.substring(0,index)+blank[count]+numbers.substring(index+1);
                count++;
            }
            System.out.println(numbers);
        }
    }

    private static boolean dfs(int i) {
        if(i == blank.length) {  //base case: filled in all the blanks
            return solveEquation();
        }
        for(String op : operators) {
            blank[i] = op;
            if(dfs(i + 1)) {
                return true;
            }
        }
        blank[i] = "_"; //restore to previous state
        return false;
    }

    private static boolean solveEquation() {
        String[] eachNumber = numbers.substring(0, numbers.indexOf("=")).split("_");
        String finalResult = numbers.substring(numbers.indexOf("=")+1, numbers.length());
        double currentResult = Double.parseDouble(eachNumber[0]);
        for(int i=1;i<eachNumber.length;i++) {
            String op = blank[i-1];
            if(op==operators[0]) {
                currentResult = currentResult + Integer.parseInt(eachNumber[i]);
            } else if(op==operators[1]) {
                currentResult = currentResult - Integer.parseInt(eachNumber[i]);
            } else if(op==operators[2]) {
                currentResult = currentResult / Integer.parseInt(eachNumber[i]);
            } else if(op==operators[3]) {
                currentResult = currentResult * Integer.parseInt(eachNumber[i]);
            }
        }
        return (currentResult==Integer.parseInt(finalResult));
    }

}

的输出java GapFill 6_3_5_7_4_8=13是6m3p5m7p4p8=13。

使用“p,m,d,t”符号代替“+,-,÷,×”，因为终端不喜欢 × 或 ÷

于 2013-01-26T16:22:03.577 回答