写了个算24点的程序,感觉还凑合

Question

算法效率不高
主要就花了2小时,感觉比刚毕业时思路清晰了些,嘿嘿
不好的地方希望大家指教啦,说实话效率确实不咋的大致思路先取4张牌,然后全排列生成24种组合每次对其中的一种组合,[1,2,3,4]
1) 先计算1和2的加减乘除4种结果,再计算3和4的加减乘除,最后 计算12 和 342) 计算1和2,再计算12和3,再计算123和4记录下了所有的计算结果和过程遍历取得值为24的那些过程import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
class Detail {
    int value;
    String strValue;    public Detail() {
    }    public Detail(int value) {
        this.value = value;
        this.strValue = String.valueOf(value);
    }
}
public class C24 {
    /**
     * @param args
     */
    public static void main(String[] args) {
        C24 c24 = new C24();        c24.C24p();
    }    void C24p() {
        int[] srcCards = generateCards();
        boolean hasAnswer = false;        // int[] srcCards ={4,1,2,10};
        try {
            List<int[]> all = allPermutation(srcCards);
            List<Detail> results = new ArrayList<Detail>();            for (int[] cards : all) {
                List<Detail> oneCase = calEachCase(cards);
                results.addAll(oneCase);
            }            for (Detail detail : results) {
                if (detail.value == 24) {
                    hasAnswer = true;
                    System.out.println(detail.strValue);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.err.println(Arrays.toString(srcCards));
        }        if (!hasAnswer) {
            System.out.println("No Answer");
            System.out.println(Arrays.toString(srcCards));
        }
    }    int[] generateCards() {
        int[] rtn = new int[4];
        Random rand = new Random();        for (int i = 0; i < rtn.length; i++) {
            rtn[i] = rand.nextInt(10) + 1;
        }        return rtn;
    }    List<int[]> allPermutation(int[] cards) {
        List<int[]> rtn = new ArrayList<int[]>();
        int length = cards.length;        if (length == 1) {
            rtn.add(cards);            return rtn;
        }        for (int i = 0; i < length; i++) {
            int card = cards[i];
            int[] leftCards = removeOne(cards, i);
            List<int[]> newRtn = allPermutation(leftCards);            for (int[] js : newRtn) {
                int[] newCards = new int[length];
                newCards[0] = card;
                System.arraycopy(js, 0, newCards, 1, length - 1);
                rtn.add(newCards);
            }
        }        return rtn;
    }    int[] removeOne(int[] cards, int index) {
        int[] newCards = new int[cards.length - 1];
        int j = 0;        for (int i = 0; i < cards.length; i++) {
            if (index != i) {
                newCards[j] = cards[i];
                j++;
            }
        }        return newCards;
    }    List<Detail> calEachCase(int[] cards) {
        List<Detail> list = new ArrayList<Detail>();
        int x = cards[0];
        int y = cards[1];
        int z = cards[2];
        int u = cards[3];
        List<Detail> listA = cal(new Detail(x), new Detail(y));
        List<Detail> listB = cal(new Detail(z), new Detail(u));
        list.addAll(cal(listA, listB));        List<Detail> list1 = cal(new Detail(x), new Detail(y));
        List<Detail> list2 = cal(list1, new Detail(z));
        List<Detail> list3 = cal(list2, new Detail(u));
        list.addAll(list3);        return list;
    }    List<Detail> cal(Detail detail1, Detail detail2) {
        int x = detail1.value;
        int y = detail2.value;
        String strX = detail1.strValue;
        String strY = detail2.strValue;
        List<Detail> rtnList = new ArrayList<Detail>();
        Detail detail = null;
        detail = new Detail();
        detail.value = x + y;
        detail.strValue = "(" + strX + "+" + strY + ")";
        rtnList.add(detail);
        detail = new Detail();
        detail.value = x - y;
        detail.strValue = "(" + strX + "-" + strY + ")";
        rtnList.add(detail);
        detail = new Detail();
        detail.value = x * y;
        detail.strValue = "(" + strX + "*" + strY + ")";
        rtnList.add(detail);        if ((y != 0) && ((x % y) == 0)) {
            detail = new Detail();
            detail.value = x / y;
            detail.strValue = "(" + strX + "/" + strY + ")";
            rtnList.add(detail);
        }        return rtnList;
    }    List<Detail> cal(List<Detail> list, Detail detail) {
        List<Detail> rtnList = new ArrayList<Detail>();        for (Detail det : list) {
            rtnList.addAll(cal(det, detail));
        }        return rtnList;
    }    List<Detail> cal(List<Detail> list1, List<Detail> list2) {
        List<Detail> rtnList = new ArrayList<Detail>();        for (Detail detail1 : list1) {
            for (Detail detail2 : list2) {
                rtnList.addAll(cal(detail1, detail2));
            }
        }        return rtnList;
    }
}

Answer 1

我滴个神呐，I服了YOU。不过精神赞一个。^_^

Answer 2

package com;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
/**
 * value用于存放单个值,或者多值运算后的结果 <br>
 * strValue用于存放value取得的计算过程
 */
class Detail {
    int value;
    String strValue;    public Detail() {
    }    public Detail(int value) {
        this.value = value;
        this.strValue = String.valueOf(value);
    }
}
public class C24 {
    /**
     * @param args
     */
    public static void main(String[] args) {
        C24 c24 = new C24();
        c24.C24p();
    }    void C24p() {
        // 发牌
        int[] srcCards = generateCards();
        boolean hasAnswer = false;        // int[] srcCards ={4,1,2,10};
        try {
            // 全排列
            List<int[]> all = allPermutation(srcCards);
            List<Detail> results = new ArrayList<Detail>();            for (int[] cards : all) {
                // 从全排列的数组中,取出一组牌,进行计算
                List<Detail> oneCase = calEachCase(cards);
                // 记录计算结果
                results.addAll(oneCase);
            }            // 打印值为24的计算结果
            for (Detail detail : results) {
                if (detail.value == 24) {
                    hasAnswer = true;
                    System.out.println(detail.strValue);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.err.println(Arrays.toString(srcCards));
        }        if (!hasAnswer) {
            System.out.println("No Answer");
            System.out.println(Arrays.toString(srcCards));
        }
    }    /**
     * 随机生成四张牌
     *
     * @return
     */
    int[] generateCards() {
        int[] rtn = new int[4];
        Random rand = new Random();        for (int i = 0; i < rtn.length; i++) {
            rtn[i] = rand.nextInt(10) + 1;
        }        return rtn;
    }    /**
     * 递归算法对cards进行全排列<br>
     * 依次从cards中取出一张牌,再对剩余的做全排列
     *
     * @param cards
     * @return
     */
    List<int[]> allPermutation(int[] cards) {
        List<int[]> rtn = new ArrayList<int[]>();
        int length = cards.length;        if (length == 1) {
            rtn.add(cards);            return rtn;
        }        for (int i = 0; i < length; i++) {
            int card = cards[i];
            int[] leftCards = removeOne(cards, i);
            List<int[]> newRtn = allPermutation(leftCards);            for (int[] js : newRtn) {
                int[] newCards = new int[length];
                newCards[0] = card;
                System.arraycopy(js, 0, newCards, 1, length - 1);
                rtn.add(newCards);
            }
        }        return rtn;
    }    /**
     * 删除数组cards中,第index个元素,返回新数组
     *
     * @param cards
     * @param index
     * @return
     */
    int[] removeOne(int[] cards, int index) {
        int[] newCards = new int[cards.length - 1];
        int j = 0;        for (int i = 0; i < cards.length; i++) {
            if (index != i) {
                newCards[j] = cards[i];
                j++;
            }
        }        return newCards;
    }    /**
     * 对四张牌进行计算
     *
     * @param cards
     * @return
     */
    List<Detail> calEachCase(int[] cards) {
        List<Detail> list = new ArrayList<Detail>();
        int x = cards[0];
        int y = cards[1];
        int z = cards[2];
        int u = cards[3];        // 计算x与y的四则运算结果
        List<Detail> listA = cal(new Detail(x), new Detail(y));        // 计算z与u的四则运算结果
        List<Detail> listB = cal(new Detail(z), new Detail(u));
        // 计算xy与zu的四则运算结果,结果存放list
        list.addAll(cal(listA, listB));        // 计算x与y四则计算结果
        List<Detail> list1 = cal(new Detail(x), new Detail(y));        // 计算xy与z四则计算结果
        List<Detail> list2 = cal(list1, new Detail(z));        // 计算xyz与u四则计算结果
        List<Detail> list3 = cal(list2, new Detail(u));
        // 结果存放list
        list.addAll(list3);        return list;
    }    /**
     * 计算x与y的四则运算结果并记录过程,返回list
     *
     * @param detail1
     * @param detail2
     * @return
     */
    List<Detail> cal(Detail detail1, Detail detail2) {
        int x = detail1.value;
        int y = detail2.value;
        String strX = detail1.strValue;
        String strY = detail2.strValue;
        List<Detail> rtnList = new ArrayList<Detail>();
        Detail detail = null;
        detail = new Detail();
        detail.value = x + y;
        detail.strValue = "(" + strX + "+" + strY + ")";
        rtnList.add(detail);
        detail = new Detail();
        detail.value = x - y;
        detail.strValue = "(" + strX + "-" + strY + ")";
        rtnList.add(detail);
        detail = new Detail();
        detail.value = x * y;
        detail.strValue = "(" + strX + "*" + strY + ")";
        rtnList.add(detail);        if ((y != 0) && ((x % y) == 0)) {
            detail = new Detail();
            detail.value = x / y;
            detail.strValue = "(" + strX + "/" + strY + ")";
            rtnList.add(detail);
        }        return rtnList;
    }    /**
     * 用一组数与一个数做四则运算
     *
     * @param list
     * @param detail
     * @return
     */
    List<Detail> cal(List<Detail> list, Detail detail) {
        List<Detail> rtnList = new ArrayList<Detail>();        for (Detail det : list) {
            rtnList.addAll(cal(det, detail));
        }        return rtnList;
    }    /**
     * 一组数与另一组数做四则运算
     *
     * @param list1
     * @param list2
     * @return
     */
    List<Detail> cal(List<Detail> list1, List<Detail> list2) {
        List<Detail> rtnList = new ArrayList<Detail>();        for (Detail detail1 : list1) {
            for (Detail detail2 : list2) {
                rtnList.addAll(cal(detail1, detail2));
            }
        }        return rtnList;
    }
}