分治思想找24

easyhaohao

原文:

http://hi.baidu.com/cesul/blog/item/998796880ba02899a5c2720b.html

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Iterator;import java.util.Set;public class Find24 {private static double threshold = 1E-6;private static Double [] number = new Double[4];private static String [] result = new String[4];static Set<String> set = new HashSet<String>();public static void main(String[] args) throws Exception{   //获取输入   System.out.println("请输入数字：（输入一个空一行）");   BufferedReader bf;   for (int i = 0; i < 4; i++) {    bf = new BufferedReader(new InputStreamReader(System.in));    result = bf.readLine();    number = Double.valueOf(result);   }   System.out.println("你输入的数字是：" + result[0]+ ", " + result[1]+ ", " + result[2]+ ", " + result[3]);     Recurse_find(4);     //用一个去除重复的HashSet统计结果并输出   Iterator<String> it=set.iterator();   while(it.hasNext()){    System.out.println(it.next());   }   System.out.println("共有" + set.size() + "条参考结果。");   }private static void Recurse_find(int n) {   if (n == 1) {    if( Math.abs(number[0] - 24) < threshold ){     set.add(result[0].substring(1, result[0].length()-1) + " = 24"); //符合加入HashSet    }else{    }   }     for (int i = 0; i < n; i++)    {    for (int j = i+1; j < n; j++)     {         double a, b;      String expa, expb;     a = number;     b = number[j];     number[j] = number[n-1];         expa = result;     expb = result[j];     result[j] = result[n-1];         result = "(" + expa + "+" + expb + ")";     number = a+b;     Recurse_find(n-1);         result = "(" + expa + "-" + expb + ")";     number = a-b;     Recurse_find(n-1);     result = "(" + expb + "-" + expa + ")";     number = b-a;     Recurse_find(n-1);       result = "(" + expa + "*" + expb + ")";     number = a*b;     Recurse_find(n-1);         if(b != 0){      result = "(" + expa + "/" + expb + ")";      number = a/b;      Recurse_find(n-1);      }         if (a != 0) {      result = "(" + expb + "/" + expa + ")";      number = b/a;      Recurse_find(n-1);      }         number = a;     number[j] = b;     result = expa;     result[j] = expb;    }   }}}