7

はっきりさせておきますが、これは宿題ではありません。私は自分の時間に CS を勉強しています。

最近、チャールズ・フィリップスの「論理的思考のための 50 のパズル」という本を購入しました。私はそのうちの 1 つを開始し、再帰を使用して問題を解決できることに気づきました。これが（言い換えられた）質問です：

各スペースに算術演算子 (+、-、​​÷、x) を挿入して、方程式を解きます。

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

再帰を使用してこの問題を解決するには、まず基本ケースを特定する必要があると私は理解しています。しかし、私はこれを行うのに問題があります。

私の質問は、可能な基本ケースとは何か、それを実装するにはどうすればよいですか? 再帰関数はどのように見えるでしょうか (引数、戻り値の型など)? （コードは役に立ちます）！

これは私がこれまでに持っているものです：ほとんど働いていると思います

実装については私の回答を参照してください

Nb私は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

これが私が最終的に実装したものですが、最初に問題の解決策を説明します。

  • 基本的なケース (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 に答える
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 に答える