[PAT解题报告] Hashing
关于hash的模拟，不难。首先hash的size需要自己确定，找到不小于m的第一个质数就可以了，质数判断用暴力判断，从2到sqrt(m)枚举因数就可以。
hash探测x采用看一下x % m, (x + 1 ^ 2) % m, (x + 2 ^ 2) % m.... (x + (m
- 1) ^ 2) % m, 第一个没有使用的位置来保存x，如果全占满了，没地方存x，输出"-"。
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
bool mark[10004];
bool test(int x) {
if (x == 1) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
int main() {
int m,n;
scanf("%d%d",&m,&n);
for (;!test(m);++m)
;
for (int i = 0; i < n; ++i) {
int x;
scanf("%d",&x);
if (i) {
putchar(' ');
}
x %= m;
int j;
for (j = 0; j < m; ++j) {
int key = (x + j * j) % m;
if (!mark[key]) {
printf("%d",key);
mark[key] = true;
break;
}
}
if (j >= m) {
putchar('-');
}
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1078
查看30道真题和解析