《程序挑战设计》算法解法以及笔记—

question:

　　your friend suggest playing a game :

　　（你的朋友建议来玩一个游戏）

　　There are some paper with number int the pocket,you can obtain the paper four times in the packet,and put it back after record the number on paper every time.If the sum of these four number is 'm' ,That means you win,otherwise your friend win.But you have challenged some time,and never won just once.So you get very angry and destory the pocket ,intend to check whether you can win.

　　（口袋里有一些带数字的纸片，你可以从中拿四次纸片，每次拿之后再放回。如果这些数字的和为m，你就赢了，否则就是你的朋友赢，但是实际上你挑战了很多次，一次都没有赢过，所以你怒不可遏的撕破了口袋，想检查一下你究竟有没有赢的可能）

　　Please compile a program to judge while the number on paper are "k1,k2,.....,kn" are there a scheme that make the sum of four number you choose is 'm'.If it is existing ,printf yes ,otherwise printf"no"

　　（请编写一个程序来判断当这些纸片上的数字是“k1,k2,k3……kn”的时候，有没有可能有四个数字的和为m，如果有，则输出yes，否则输出no）

　　Worst solution is there;

　　(最坏的解决方法——暴搜，复杂度O(n^4)）

class solution{
    void Judge(int[] number,int m){
　　　　for(int i=0;i<number;i++){
　　　　　　for(int j=0;j<number;j++){
　　　　　　　　for(int k=0;k<number;k++){　　　　
                           for(int n=0;n<number.length;n++){
    　    　                  if(temp[i]+temp[j]+temp[k]+temp[n]==m){
                                    System.out.print("yes");
                                }
                           }
          　        }
　　　　    }
　　　  }
           System.out.print("no");
　　}       
}

　　the solution after optimizing:

　　（优化后的解）

proceeding of optimizing:

obviously,if we want to find a solution,we should find a condition that make a+b+c+d=m,

so ,we can change the euqation to "a+b=m-(c+d)" because m is known for us

and we can get the code is this:

（优化过程：本来是要找a+b+c+d=m，判断当四个数字的和为m的时候退出循环）

优化：将a+b+c+d=m变为a+b=m-(c+d)——因为m是已知的

代码如下：

 1 public class solution{
 2     private static int m=24;
 3     private static int[] test =  {5,6,7,8,9,1,23,6,12};
 4     private static int[] test01 = new int[test.length*test.length];
 5  
 6     public static boolean find(){
 7         for(int i=0;i<test.length;i++){
 8             for(int j=0;j<test.length;j++){          
 9                 if(binary(m-(test[i]+test[j]))){
10                     return false;
11                 }
12             }
13         }
14         return false;
15     }      
16         
17     public static boolean binary(int x){
18         int l=0,r=test01.length;
19         while(r-1>=1){
20             int i = (l+r)/2;
21             if(x==test01[i]){
22                 return true;
23             }else if(x>test01[i]){
24                 l = i+1;
25             }else{
26                 r = i;
27             }
28         }
29         return false;
30     }
31      
32     public static void fort(){
33         for(int i=0,count=0;i<test.length;i++){
34             for(int j=0;j<test.length;j++,count++){
35                 test01[count] = test[i]+test[j];
36             }
37         }
38         for(int i=0;i<test01.length;i++){
39             for(int j=0;j<test01.length-i;j++){
40                 if(test01[i]>test01[j]){  
41                     int temp = test01[j];
42                     test01[j] = test01[i];
43                     test01[i] = temp;
44                 }
45             }
46         } 
47     }
48     
49     public static void main(String[] args){
50         fort();
51         System.out.println("是否有四个数字使得和为m————"+m);
52         System.out.println(find());
53     }
54 }

the complexity of algorithm after optimizing is O(n^2*logn)

(优化后的算法复杂度为O(n^2*logn))

summary：

in this algorithm,I have used "binary_serach" to optimizd

(小结：在这个算法中，用的是“二分法”来优化)

《程序挑战设计》算法解法以及笔记——抽签

推荐阅读