抽签问题的思考(二分算法)

问题:
将写有数字的N个纸片放入口袋中,你可以从口袋中抽取4次纸片,每次记下纸片上的数字后都将其放回口袋中.如果这4个数字的和是M,就是你赢,否则就是你的朋友赢.

很容易就可以写出下边的代码:

 1 for(int a=0; a<n; a++){
 2     for(int b=0; b<n; b++){
 3         for(int c=0; c<n; c++){
 4             for(int d=0; d<n; d++){
 5                 if(k[a] + k[b] + k[c] + k[d]==m){
 6                     f = true;
 7                 }
 8             }
 9         }
10     }
11 }

上面是最初所记载的程序的循环部分.最内侧关于d的循环所做的事就是:

检查是否有d使得Ka+Kb+Kc+Kd=M

通过对式子移向,就能得到另一种表达方式:

检查是否有d使得Ka=M-Kb+Kc+Kd

就是检查数组K中所有元素,判断是否有M-Kb+Kc+Kd.

这样的快速查找,就要用到二分搜索的算法.

1.二分搜索与O(n³logn)

排序O(nlogn)时间

循环O(n³logn)时间

 1 int n,m,k[MAX];
 2 
 3 bool binary_search(int x){
 4     //x的存在范围是k[l],k[l+l]...k[r-l]
 5     int l=0,r=n;
 6     //反复操作直到存在范围为空
 7     while(r-l>=l){
 8         int i=(l+r)/2;
 9         if(k[i]==x) return true;//找到x
10         else if(k[i]<x)   l=i+1;
11         else r=i;
12     }
13     //没找到x
14     return false;
15 }
16 
17 viod solve(){
18     //为了找到二分查找需要先排序
19     sort(k,k+n);
20 
21     bool f=false;
22     for(int a=0; a<n; a++){
23         for(int b=0; b<n; b++){
24             for(int c=0;c<n; c++){
25                 //将最内则的循环替换成二分查找
26                 if(binary_search(m-k[a]-k[b]-k[c])){
27                     f=true;
28                 }
29             }
30         }
31     }
32     if(f)   puts("Yes");
33     else   puts("No");
34 }

排序O(n²logn)时间

循环O(n²logn)时间

 1 int n,m,k[MAX];
 2 int kk[MAX*MAX];
 3 
 4 bool binary_search(int x){
 5     //x的存在范围是kk[l],kk[l+l]...kk[r-l]
 6     int l=0,r=n*n;
 7     //反复操作直到存在范围为空
 8     while(r-l>=l){
 9         int i=(l+r)/2;
10         if(kk[i]==x) return true;//找到x
11         else if(kk[i]<x)   l=i+1;
12         else r=i;
13     }
14     //没找到x
15     return false;
16 }
17 
18 viod solve(){
19     //枚举k[c]+k[d]的和
20     for(int c=0; c<n; c++){
21         for(int d=0; d<n; d++){
22             kk[c*n+d]=k[c]+k[d];
23         }
24     }
25     //排序以便进行二分搜索
26     sort(kk,kk+n*n);
27 
28     bool f=false;
29     for(int a=0; a<n; a++){
30         for(int b=0; b<n; b++){
31             //将内则的两个循环替换成二分搜索
32             if(binary_search(m-k[a]-k[b])){
33                 f=true;
34             }
35         }
36     }
37     if(f)   puts("Yes");
38     else   puts("No");
39 }

本问题既需要二分搜索这一基础算法知识,也需要将四个数分成两两考虑的想象力.像这样从复杂度较高的算法出发,不断降低复杂度知道满足问题要求的过程,也是设计算法时常会经历的过程.

<<挑战程序设计竞赛>>读后感