在Java中实现递归

Question

为了清楚起见,这不是一个家庭作业,我在自己的时间学习CS!

我最近在Charles Phillips购买了一本名为"50个逻辑思维谜题"的书.我启动了其中一个,我发现我可以使用递归来解决问题.这是(转述)问题:

在每个空格中插入一个数学运算符(+, - ,÷,x)来求解等式:

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

我的理解是,为了使用递归来解决这个问题,我首先需要确定一个基本案例.但是,我在做这件事时遇到了麻烦.

所以我的问题是,什么是可能的基本情况,我应该如何开始实施呢？递归函数看起来像什么(参数,返回类型等)？(代码很有用)!

这就是我到目前为止:我认为几乎正在工作

请参阅我的答案以了解实施情况

Nb我正在使用Java

Answer 1

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

\n\n

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

\n\n

这是代码：

\n\n

class GapFill {\n\n    private static String numbers; //E.g. 6_5_4=15\n    private static String[] blank; //Array of operators to go in the blanks\n\n    //Where:\n    //p = plus\n    //m = minus\n    //d = divide\n    //t = times\n    private static String[] operators = {"p", "m", "d,", "t"};\n\n    public static void main(String[] args) {\n        numbers = args[0];\n        blank = new String[numbers.split("_").length - 1];\n        if(dfs(0)) { //If a solution was found\n            int count = 0;\n            while(numbers.indexOf("_")!=-1) {\n                int index = numbers.indexOf("_");\n                numbers = numbers.substring(0,index)+blank[count]+numbers.substring(index+1);\n                count++;\n            }\n            System.out.println(numbers);\n        }\n    }\n\n    private static boolean dfs(int i) {\n        if(i == blank.length) {  //base case: filled in all the blanks\n            return solveEquation();\n        }\n        for(String op : operators) {\n            blank[i] = op;\n            if(dfs(i + 1)) {\n                return true;\n            }\n        }\n        blank[i] = "_"; //restore to previous state\n        return false;\n    }\n\n    private static boolean solveEquation() {\n        String[] eachNumber = numbers.substring(0, numbers.indexOf("=")).split("_");\n        String finalResult = numbers.substring(numbers.indexOf("=")+1, numbers.length());\n        double currentResult = Double.parseDouble(eachNumber[0]);\n        for(int i=1;i<eachNumber.length;i++) {\n            String op = blank[i-1];\n            if(op==operators[0]) {\n                currentResult = currentResult + Integer.parseInt(eachNumber[i]);\n            } else if(op==operators[1]) {\n                currentResult = currentResult - Integer.parseInt(eachNumber[i]);\n            } else if(op==operators[2]) {\n                currentResult = currentResult / Integer.parseInt(eachNumber[i]);\n            } else if(op==operators[3]) {\n                currentResult = currentResult * Integer.parseInt(eachNumber[i]);\n            }\n        }\n        return (currentResult==Integer.parseInt(finalResult));\n    }\n\n}\n

\n\n

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

\n\n

使用“p、m、d、t”符号代替“+、-、\xc3\xb7、\xc3\x97”，因为终端不喜欢 \xc3\x97 或 \xc3\xb7

\n