新社会人の備忘録。

備忘録ってさ、なんかロックじゃね?

テンパズルと計算誤差

新卒の私は現在会社でjavaの研修を受けている。
大学時代にC言語を習った時にも迷路だったりRPG風対戦シミュレーションを作ったりしていた私なので(?)、学習がてら10パズルという物を作成することにした。

10パズルとは、誰もが一度はやったことのある*1、4つの数字を四則演算を駆使して10にするゲームの事を指す。

テンパズル - Wikipedia

とりあえず、処理が一番簡単であると思われる、並び替えなし、負の数使用不可を採用。
wikiによると、10が作れる並びは全部で10000通り中5878通りらしい。
過去に5割くらいという情報を聞いていたので、特に驚きはしなかった。
とりあえずこの数字を目標にして、プログラムを作成してみる。


アルゴリズム、とかを考えている余裕はなかったので、とりあえず総当たり式にする。
計算順序の組み合わせは、
①(1+2)+(3+4) 
②{(1+2)+3}+4
③1+{(2+3)+4} 
④1+{2+(3+4)} 
⑤{1+(2+3)}+4 
の5通りなので(正確には6通りなのだが、①は前のかっこから計算しても後ろのかっこから計算しても同じなので省いた。プログラムでは処理だけ省いてif文は残した)、全てにおいて計算して10になればカウント、カウントが1以上あれば10が出来た組み合わせとして数えることにした。

計算の演算は(+,-,*,/)の4通りで行うため、3ヶ所全てでfor文を4回行い、引数によって計算方法を変えるメソッドを作成することで、全てのパターンにおける計算を可能にした。

以下ソースコード

class keisan {

    static int count = 0;
    int counta = 0;
    int[] suuzi = new int[4];
    String[] enzan = {"+", "-", "*", "/"}; //式表示用
    keisan(int a, int b, int c, int d){
         suuzi[0] = a;
        suuzi[1] = b;
        suuzi[2] = c;
        suuzi[3] = d;
    }
    void dousyutu(int i, int j, int k, int l) {
        double kai = 0;
        String siki = ""; //式表示用
        try {
            if(i==0){
                kai = sisoku(l, sisoku(k, sisoku(j, suuzi[0], suuzi[1]), suuzi[2]), suuzi[3]);
                siki = "(" + "(" + suuzi[0] + enzan[j] + suuzi[1]+ ")" + enzan[k] + suuzi[2] + ")" + enzan[l] + suuzi[3];
            } else if(i==1){
                kai = sisoku(k, sisoku(j, suuzi[0], suuzi[1]), sisoku(l, suuzi[2], suuzi[3]));
                siki = "(" + suuzi[0] +enzan[j] + suuzi[1] + ")" + enzan[k] + "(" + suuzi[2] + enzan[l] + suuzi[3] + ")";
            } else if(i==2){
                kai = sisoku(l, sisoku(j, suuzi[0] ,sisoku(k, suuzi[1], suuzi[2])), suuzi[3]);
                siki = "(" + suuzi[0] + enzan[j] + "(" + suuzi[1] + enzan[k]+ suuzi[2] + ")" + ")" + enzan[l] + suuzi[3];
            } else if(i==3){
            } else if(i==4){
                kai = sisoku(j, suuzi[0], sisoku(l, sisoku(k, suuzi[1], suuzi[2]), suuzi[3]));
                siki = suuzi[0] + enzan[j] + "(" + "(" + suuzi[1] + enzan[k] + suuzi[2] + ")"+ enzan[l] + suuzi[3] + ")";
            } else if(i==5){
                kai = sisoku(j, suuzi[0], sisoku(k, suuzi[1], sisoku(l, suuzi[2], suuzi[3])));
                siki = suuzi[0] + enzan[j] + "(" + suuzi[1] + enzan[k] + "(" + suuzi[2] + enzan[l] + suuzi[3] + ")" + ")";
            }
        } catch( Exception e ) { //0で割るときの例外
            kai = 0;
        }
        if(kai = 10.0){
            counta++;
        }
    }

    double sisoku(int mode, double a, double b){ //四則演算の選択用のメソッド
        double c = 0;
        if(mode == 0){
            c= a+b;
        } else if(mode == 1){
            c= a-b;
        } else if(mode == 2){
            c= a*b;
        } else if(mode == 3){
            c= a/b;
        }
        return c;
    }
    
    void countsyori(){
        if(counta >0){
            count++;
        }
    }
}

class tasu {
    public static void main(String[] args){
// 0000から9999までくりかえす
        for(int a = 0; a<10; a++){
            for(int b = 0; b<10; b++){
                for(int c = 0; c<10; c++){
                    for(int d = 0; d<10; d++){
// i:計算順序 j,k,l:四則演算選択
        keisan retu = new keisan(a,b,c,d);
        for(int i = 0; i<6; i++){
            for(int j = 0; j<4; j++){
                for(int k = 0; k<4; k++){
                    for(int l = 0; l<4; l++){
                        retu.dousyutu(i, j, k ,l);
                    }
                }
            }
        }
        retu.countsyori();
                    }
                }
            }
        }
        System.out.println(keisan.count);
    }
}

と、自分でも納得して書いたプログラムがこちらになるのだが、結果は以下。

>java tasu
5876

あれ、2つたりない。(実行結果見た時の率直な感想)

で、自分では理由が全く分からなかったので、検索して以下のサイトを拝見。

すると、誤差の話が出ていた。以下引用。

また、計算機の性質上、若干の誤差が生じることがあるので、1を9の3乗で割った数(=0.0013717421124828531...)より小さい数(0.001)の誤差を許すことにしました。

計算機の誤差で2個減ることってあるのか、と思いながらも、コードを修正する。
以下修正箇所のみ。

class keisan {
    final double tol = 0.001;
    void dousyutu(int i, int j, int k, int l) {
                //省略
        if((kai < 10.0 + tol)&&(kai > 10.0 - tol)){
            counta++;
            //System.out.println(siki);
        }
        if((kai < 10.0 + tol)&&(kai > 10.0 - tol)&&(kai != 10.0)){
            //System.out.println( siki + " = " + kai);
        }
    }
}
>java tasu
5878

できた。
どういうものが計算誤差で数えられてなかったのかを表示してみると、

2/(1-(4/5)) = 10.000000000000002
2/(2-(9/5)) = 10.000000000000002
2/((6/5)-1) = 10.000000000000002
((2/7)*5)*7 = 9.999999999999998
4/(2-(8/5)) = 10.000000000000002
4/((7/5)-1) = 10.000000000000002
(5*(2/7))*7 = 9.999999999999998
(5/3)/(1/6) = 10.000000000000002
6/((1/5)*3) = 9.999999999999998
6/(2-(7/5)) = 9.999999999999998
6/(3*(1/5)) = 9.999999999999998
6/((8/5)-1) = 9.999999999999998
7*((2/7)*5) = 9.999999999999998
7*(5*(2/7)) = 9.999999999999998

こういうものだった。
7で割るなど、明らかに計算誤差が出るだろうものもあるが、
中には割り切れなさそうな数では割ってないのに10にならないものもあって少し困惑気味。
なぜならないのか勉強すると、計算は2進数で行うため、2進数で無限小数になるものはこういう状況になるらしい。
業務の時にこういう見落としがあるとまずい。割り算には気を付けないといけない。

*1:といっても会社の同期の一人は知らなかったが