将写有数字k1,k2...kn的n个纸片放入口袋中，可以从口袋中去4次纸片，每次几下纸片上数字后将纸片再放回口袋。
如果四个数字的和是m，就输出true，否则就输出false。检查是否有输出true

1. package org.mungo.algorithm;
   
2. 
   
3. import java.util.Arrays;
   
4. 
   
5. /**
   
6. * 将写有数字k1,k2...kn的n个纸片放入口袋中，可以从口袋中去4次纸片，每次几下纸片上数字后将纸片再放回口袋。
   
7. * 如果四个数字的和是m，就输出true，否则就输出false。检查是否有输出true的可能性。
   
8. * @author Lily
   
9. *
   
10. */
    
11. public class Draw {
    
12. 
    
13.     /**
    
14.      * 1.穷举
    
15.      * n[a] + n[b] + n[c] + n[d] == m
    
16.      *
    
17.      * @param n
    
18.      * @param m
    
19.      * @return
    
20.      */
    
21.     private static boolean drawMethod(int[] n, int m) {
    
22.         boolean result = false;
    
23.         // 循环枚举所有可能
    
24. 
    
25.         for (int a = 0; a < n.length; a++) {
    
26.             for (int b = 0; b < n.length; b++) {
    
27.                 for (int c = 0; c < n.length; c++) {
    
28.                     for (int d = 0; d < n.length; d++) {
    
29.                         if (n[a] + n[b] + n[c] + n[d] == m) {
    
30.                             result = true;
    
31.                         }
    
32.                     }
    
33.                 }
    
34.             }
    
35.         }
    
36. 
    
37.         return result;
    
38.     }
    
39. 
    
40.     /**
    
41.      * 递归二分查找
    
42.      *
    
43.      * @param Array
    
44.      * @param low
    
45.      * @param high
    
46.      * @param key
    
47.      * @return
    
48.      */
    
49.     private static boolean binarySearch(int Array[], int low, int high, int key) {
    
50.         if (low <= high) {
    
51.             int mid = (low + high) / 2;
    
52.             if (key == Array[mid])
    
53.                 return true;
    
54.             else if (key < Array[mid])
    
55.                 // 移动low和high
    
56. 
    
57.                 return binarySearch(Array, low, mid - 1, key);
    
58.             else if (key > Array[mid])
    
59.                 return binarySearch(Array, mid + 1, high, key);
    
60.         }
    
61.         return false;
    
62.     }
    
63. 
    
64.     /**
    
65.      * 2.n[d]=m - n[a] - n[b] - n[c]
    
66.      *
    
67.      * @param n
    
68.      * @param m
    
69.      * @return
    
70.      */
    
71.     private static boolean drawMethod2(int[] n, int m) {
    
72.         boolean result = false;
    
73.         Arrays.sort(n); // 进行排序
    
74. 
    
75. 
    
76.         for (int a = 0; a < n.length; a++) {
    
77.             for (int b = 0; b < n.length; b++) {
    
78.                 for (int c = 0; c < n.length; c++) {
    
79.                     if (binarySearch(n, 0, n.length - 1, m - n[a] - n[b] - n[c])) {
    
80.                         result = true;
    
81.                     }
    
82.                 }
    
83.             }
    
84.         }
    
85. 
    
86.         return result;
    
87.     }
    
88. 
    
89.     /**
    
90.      * 3.n[c]+n[d]=m - n[a] - n[b]
    
91.      *
    
92.      * @param n
    
93.      * @param m
    
94.      * @return
    
95.      */
    
96.     private static boolean drawMethod3(int[] n, int m) {
    
97.         boolean result = false;
    
98.         int nn[] = new int[n.length*n.length] ;
    
99.         // 枚举n[c]+n[d]的和
    
100. 
     
101.         for (int c = 0; c < n.length; c++) {
     
102.             for (int d = 0; d < n.length; d++) {
     
103.                 nn[c * n.length + d] = n[c] + n[d];
     
104.             }
     
105.         }
     
106.         Arrays.sort(nn);
     
107.         for (int a = 0; a < n.length; a++) {
     
108.             for (int b = 0; b < n.length; b++) {
     
109.                 if (binarySearch(nn, 0, nn.length - 1, m - n[a] - n[b])) {
     
110.                     result = true;
     
111.                 }
     
112.             }
     
113.         }
     
114. 
     
115.         return result;
     
116.     }
     
117. 
     
118.     public static void main(String[] args) {
     
119.         int[] numbers = { 1, 3, 5 };
     
120.         System.out.println(drawMethod(numbers, 10));
     
121.         System.out.println(drawMethod2(numbers, 10));
     
122.         System.out.println(drawMethod3(numbers, 9));
     
123.     }
     
124. 
     
125. }

复制代码

的可能性。

循环原则上不能超过三个，要不然可读性非常差，还有循环得到想要的结果后就结束循环，提高效率