10

楽しいので、10 匹中 8 匹の猫がカウントダウン数パズルを解くことができる簡単なプログラムを作成することにしました。リンクはカウントダウン形式ですが、ルールは同じです。したがって、私のプログラムは、AxBxCxDxExF のすべての可能な組み合わせを単純に処理します。ここで、文字は数字で、「x」は +、-、/、および * です。これがそのコードです：

private void combineRecursive( int step, int[] numbers, int[] operations, int combination[]){
    if( step%2==0){//even steps are numbers
        for( int i=0; i<numbers.length; i++){
            combination[ step] = numbers[ i];
            if(step==10){//last step, all 6 numbers and 5 operations are placed
                int index = Solution.isSolutionCorrect( combination, targetSolution);
                if( index>=0){
                    solutionQueue.addLast( new Solution( combination, index));
                }
                return;
            }
            combineRecursive( step+1, removeIndex( i, numbers), operations, combination);
        }
    }else{//odd steps are operations
        for( int i=0; i<operations.length; i++){
            combination[ step] = operations[ i];
            combineRecursive( step+1, numbers, operations, combination);
        }
    }
}

そして、これが私が望んでいない組み合わせであるかどうかをテストするために使用するものです。

public static int isSolutionCorrect( int[] combination, int targetSolution){
    double result = combination[0];
    //just a test
    if( Arrays.equals( combination, new int[]{100,'*',7,'-',8,'*',3,'+',7,'+',50})){
        System.out.println( "found");
    }
    for( int i=1; i<combination.length; i++){
        if(i%2!=0){
            switch( (char)combination[i]){
                case '+': result+= combination[++i];break;
                case '-': result-= combination[++i];break;
                case '*': result*= combination[++i];break;
                case '/': result/= combination[++i];break;
            }
        }
        if( targetSolution==result){
            return i;
        }
    }       
    return targetSolution==result?0:-1;
}

前回のエピソードで、コードに問題があることがわかりました。これは、パズルの 1 つの解決策でした。

(10*7)-(8*(3+7))

この組み合わせ「10 * 7-8 * 3 + 7」（2回）を見つけたことに気付きましたが、左から右に操作を行って解決策を確認しているため、実際にはすべての答えが見つかりません。このようなソリューションのみをチェックします ((((10*7)-8)*3)+7)。そのため、組み合わせが見つかりましたが、正しい順序がありません。

問題は、(10*7)-(8*(3+7))、(10*7)-((8*3)+7)、または 10*( 7-8)*(3+7)? ただし、バランシング ノードとしての操作でバランス ツリーを使用できます。しかし、式を移動せずにすべての可能な組み合わせを通過する方法がわかりません。

(10*7)-(8*(3+7))
          -
     /        \
    *         *
  /   \      /  \
700   7     8    +
                / \
              7    3

(10*7)-((8*3)+7)
          -
     /        \
    *         +
  /   \      /  \
700   7     *    7
           / \
          8  3

10*(7-8)*(3+7)

                 *
           /           \
          *
     /        \         10
    -          +
  /   \      /  \
7     8     3    7

コードでこれを行うにはどうすればよいですか? 解決されたコードを探すのではなく、それを修正するためにパースペクティブを変更する必要があります。なぜ私はそれに困惑しているのか分かりません。

私について: コンピューター サイエンス 4 年目、プログラミングの新人でも初心者でもない (少なくとも信じたい ;))

4

1 に答える 1