Fork me on GitHub

PAT(甲级)渡劫(十三)-Hashing(25)


PAT(甲级)渡劫(十三)-Hashing(25)

题目大意:

题目要求用二次探测法(Quadratic probing)解决冲突

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstdio>

using namespace std;

int Hash[11024];

bool isprime(int n){
if(n == 1) return false;
for(int i = 2 ; i*i <= n ; i++){
if(n%i == 0) return false;
}
return true;
}

int main(){
//freopen("in.txt","r",stdin);
int msize,n;
scanf("%d %d",&msize,&n);
while(isprime(msize) == false) msize++;
while(n--){
int i,e;
scanf("%d",&e);
for(i = 0 ; i < msize ; i++){
if(!Hash[(e+i*i)%msize]){
Hash[(e+i*i)%msize] = e;
printf("%d",(e+i*i)%msize);
break;
}
}
if(i == msize) printf("-");
if(n != 0) printf(" ");
}
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%