☆1078

 开放定址法中的平方探测法使用时是有条件的。对于本题,存在hash不满,但始终无法填入key的情况。

当  step >= msize 时,若还找不到空位,便不可能找到了。

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 bool isprime(int x){
 7     if(x<=1)return false;
 8     for(int i=2;i<=sqrt(x);i++){
 9         if(x%i==0)return false;
10     }
11     return true;
12 }
13 bool address[10010];
14 
15 int main()
16 {
17     int msize, n;
18     cin>>msize>>n;
19     if(isprime(msize)==false){
20         for(int i=msize+1;;i++){
21             if(isprime(i)){
22                 msize=i;
23                 break;
24             }
25         }
26     }
27 
28 
29     for(int i=0;i<n;i++){
30         int key;
31         cin>>key;
32         if(address[key%msize]==false){
33             address[key%msize]=true;
34             printf("%d",key%msize);
35         }
36         else{
37             //碰撞测试
38             int step=1;
39             while(step<msize){
40                 if(address[(key+step*step)%msize]==false){
41                     address[(key+step*step)%msize]=true;
42                     printf("%d",(key+step*step)%msize);
43                     break;
44                 }
45                 step++;
46             }
47             if(step==msize)printf("-");
48         }
49         if(i<n-1)printf(" ");
50     }
51 
52     return 0;
53 }

 

上一篇:PAT-B 1078 字符串压缩与解压【字符串】


下一篇:python爬虫 双色球数据更新