抽签游戏

代码如下：

package com.chapterOne.exercise;

/**
 * Created by yangjianzhou on 2014/8/14 17:11.
 * TODO :玩游戏：将写有数字n的纸片放入口袋中，可以从口袋中抽取4次纸片，每次记下纸片上的
 * 数字后都将其放回口袋中，如果这四个数字的和是m，则赢，否则输，编写程序，判断当纸片上所写的数字
 * 是k1,k2,k3,k4,....kn，是否存在抽取4次和为m的方案。
 * 基本思路：四次抽到的数字依次为a,b,c,d,a+b+c+d=m
 * a+b=m-c-d,且a+b的值为一个数组中的值
 */
public class Lottery {
    public static final int[] ARR = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    public static final int M = 56;
    public static final int[] MIDDLE_ARR = new int[ARR.length * ARR.length];

    public static void main(String[] args) {
        fillMiddleArrWithArr(ARR , MIDDLE_ARR);
        quickSort(MIDDLE_ARR,0,MIDDLE_ARR.length-1);
        boolean bool = winGame(ARR,M,MIDDLE_ARR);
        System.out.println("win game : " + bool);
    }

    /**
     * 在数组middleArr中填入相应的值
     */
    public static void fillMiddleArrWithArr(int[] arr ,int[] middleArr) {
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                middleArr[index++] = arr[i] + arr[j];
            }
        }
    }

    /**
     * 对数组middleArr进行快速排序
     */
    public static void quickSort(int[] middleArr, int lowIndex, int highIndex) {
        int tempLowIndex = lowIndex;
        int tempHighIndex = highIndex;
        int tempLowValue = middleArr[tempLowIndex];
        while (tempLowIndex < tempHighIndex) {
            while (tempLowIndex < tempHighIndex && middleArr[tempHighIndex] > tempLowValue) {
                tempHighIndex--;
            }
            if (tempLowIndex < tempHighIndex) {
                int temp = middleArr[tempHighIndex];
                middleArr[tempHighIndex] = tempLowValue;
                middleArr[tempLowIndex] = temp;
                tempLowIndex++;
            }
            while (tempLowIndex < tempHighIndex && middleArr[tempLowIndex] < tempLowValue) {
                tempLowIndex++;
            }

            if (tempLowIndex < tempHighIndex) {
                int temp = middleArr[tempLowIndex];
                middleArr[tempLowIndex] = tempLowValue;
                middleArr[tempHighIndex] = temp;
                tempHighIndex--;
            }
            if (tempLowIndex > lowIndex) {
                quickSort(middleArr, lowIndex, tempHighIndex - 1);
            }
            if (tempHighIndex < highIndex) {
                quickSort(middleArr, tempLowIndex + 1, highIndex);
            }
        }
    }

    public static int binarySearch(int[] middleArr, int target, int startIndex, int endIndex) {
        if (startIndex <= endIndex) {
            int middleIndex = (startIndex + endIndex) / 2;
            if (target == middleArr[middleIndex]) {
                return middleIndex;
            } else if (target > middleArr[middleIndex]) {
                return binarySearch(middleArr, target, middleIndex + 1, endIndex);
            } else {
                return binarySearch(middleArr, target, startIndex, middleIndex - 1);
            }
        } else {
            return -1;
        }
    }

    public static boolean winGame(int[] arr, int m, int[] middleArr) {
        int index = -2;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
               index = binarySearch(middleArr, m - arr[i] - arr[j], 0, middleArr.length - 1);
            }
        }
        return index >0 ;
    }
}

运行结果如下：

win game : false