算24

給出4個小于10個正整數，你可以使用加減乘除4種運算以及括
号把這4個數連接配接起來得到一個表達式。現在的問題是，是否存在一種方式使得得到的表達式的結果等于24。
    這裡加減乘除以及括号的運算結果和運算的優先級跟我們平常
的定義一緻（這裡的除法定義是實數除法）。
    比如，對于5，5，5，1，我們知道5 * (5 – 1 / 5) = 24，因
此可以得到24。又比如，對于1，1，4，2，我們怎麼都不能得
到24。
輸入
    輸入資料包括多行，每行給出一組測試資料，包括4個小于10個正整
數。最後一組測試資料中包括4個0，表示輸入的結束，這組資料不用處理。
輸出
    對于每一組測試資料，輸出一行，如果可以得到24，輸出“YES”；
否則，輸出“NO”。
樣例輸入
5 5 5 1
1 1 4 2
0 0 0 0
樣例輸出
YES
NO           

複制

解題思路：

n個數算24，必有兩個數要先算。這兩個數算的結果，和剩餘n-2個數，就構成了n-1個數求24的問題。枚舉先算的兩個數，以及這兩個數的運算方式。n為1時，若等于24則輸出true，反之輸出false。

注意：浮點數比較是否相等，不能用 == 。要與24作差小于10^-6則可視為相等。

代碼如下：

import java.util.Scanner;

public class Main {
    public static boolean IsZero(double a){
        return Math.abs(a) <= 0.000001;
    }

    public static boolean count24(double[] num ,int n){
        if ( n == 1){
            if ( IsZero(num[0]-24)){
                return true;
            }else{
                return false;
            }
        }
        double[] a = new double[5];
        for ( int i = 0 ; i < n-1 ;i++){
            for ( int j = i+1 ; j < n ; j++){
                int m = 0;
                for ( int k = 0 ; k < n ; k++){
                    if ( k != i && k != j){
                        a[m++] = num[k];
                    }
                }
                a[m] = num[i] + num[j];
                if (count24(a, m+1)){
                    return true;
                }
                a[m] = num[i] - num[j];
                if (count24(a, m+1)){
                    return true;
                }
                a[m] = num[j] - num[i];
                if (count24(a, m+1)){
                    return true;
                }
                a[m] = num[i] * num[j];
                if (count24(a, m+1)){
                    return true;
                }
                if ( !IsZero(num[j])){
                    a[m] = num[i] / num[j];
                    if (count24(a, m+1)){
                        return true;
                    }
                }
                if ( !IsZero(num[i])){
                    a[m] = num[j] / num[i];
                    if (count24(a, m+1)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        double[] num = new double[5];
        while(true){
            for ( int i = 0 ; i < 4 ; i++){
                num[i] = in.nextDouble();
            }
            if ( num[0] == 0){
                break;
            }
            if ( count24(num, 4)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
        in.close();
    }

}           

複制