共计 2111 个字符，预计需要花费 6 分钟才能阅读完成。
题目粗心：
给出散列表长 MSize 和欲插入的元素，将这些元素按读入的程序插入散列表中，其中散列函数为 H(key)= key %MSize, 解决抵触采纳只往正向减少的次探查法(即二次方 探查法)。另外，如果题目给出的 MSize 不是素数，那么须要将 MSize 从新赋值为第一个比 MSize 大的素数再进行元素插入。
算法思路:
间接模仿 hash 映射的过程，首选对于输出的 MSize 如果不是素数就找到第一个比它大的素数，而后就对每一个输出的数据进行 hash 映射，应用 pos 记录映射的地位，如果 hashTable[pos]!= 0 阐明以后地位存在抵触，那么就应用二次方探测法进行 rehash，如果找到空位后退出循环，如果 rehash 的次数大于或者等于 hash 表的长度就表明没有适合的空位也退出循环。这里应用 step 记录以后存在 hash 抵触的时候 rehash 的次数。退出循环后判断 step 是否大于等于 MSize，如果是输入 ”-“, 否则输入 pos, 并且将 pos 对应地位设置为 num。最初留神输入空格。判断一个数字 N 是否为素数的办法如下：
办法一：
依据素数的定义可知，素数是指大于 1，且只能被 1 和它本身整除的自然数。1 不是素数。依据乘法的个性，可知若从 2 开始遍历到被判断数的平方根都没有找到能被整除的数，则这个数肯定为素数。对应代码如下：
bool isPrime(int N){if(N<=1) return false;
for (int i = 2; i <= sqrt(N * 1.0); ++i) {if(N%i==0) return false;
}
return true;
}办法二：
对于一个大于等于 5 的素数，其特点是总是等于 6x-1 和6x+1, 其中 x 是大于等于 1 的自然数. 那么依据这个特点, 失去的论断为,在 6 的倍数两边的数字不肯定是素数，然而不在 6 的倍数两边的数字肯定不是素数, 这样就能够优化下面的代码，思路就是首先特判小于 4 的数字，只有 2 和 3 才是素数，而后对于所有对 6 整除余数不为 1 和 5 的阐明不在 6 的倍数的两边，肯定不是素数，最初从 5 开始，步长为 6 进行遍历每一个在 6 两边的数字，对于能够对于 6 的倍数两边的数字能够整除的肯定不是素数。代码如下：
bool isPrime(int N){if(N<=3){return N>1;// 2 和 3 才是素数}
if(N%6!=1&&N%6!=5) return false;
for (int i = 5; i <= sqrt(N * 1.0); i+=6) {if(N%i==0||N%(i+2)==0) return false;
}
return true;
}对于 rehash 次数只须要 MSize 次的证实(思否的公式编辑存在 bug, 预览的时候没问题，在公布就有乱码了，上面是预览的截图)
留神点：
1、对于测试点 0 和 3 谬误的状况，能够认真看看是不是二次方探测的办法写错了，正确写法是 pos = (num+step*step)%MSize; 而不是pos = (pos+step*step)%MSize;
2、如果二次方探测始终没有找到空位，得应用 step 管制 rehash 的次数不超过 MSize，否则测试点 3 超时。
3、如果谬误的判断 1 也是素数的化，测试点 1 会出错。
提交后果：
AC 代码;
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
// 判断 N 是否为素数
//bool isPrime(int N){// if(N<=1) return false;
// for (int i = 2; i <= sqrt(N * 1.0); ++i) {// if(N%i==0) return false;
// }
// return true;
//}
bool isPrime(int N){if(N<=3){return N>1;// 2 和 3 才是素数}
// 不在 6 的倍数两边的数字肯定不是素数
if(N%6!=1&&N%6!=5) return false;
for (int i = 5; i <= sqrt(N * 1.0); i+=6) {if(N%i==0||N%(i+2)==0) return false;
}
return true;
}
int hashTable[100000] = {};// hash 表
int main(){
int MSize,N;// hash 表的大小和插入的数字个数
scanf("%d %d",&MSize,&N);
// 找到第一个大于等于 MSize 素数
while (true){if(isPrime(MSize)) break;
++MSize;
}
int num;// 输出的每一个数字
for (int i = 0; i < N; ++i) {scanf("%d",&num);
int pos = num%MSize;// 插入的地位
int step = 1;// 二次探方的步长
while (hashTable[pos]!=0&&step<MSize){
// 存在 hash 抵触
pos = (num+step*step)%MSize;
++step;
}
if(step>=MSize){
// 没有空位
printf("-");
} else {printf("%d",pos);
hashTable[pos] = num;
}
if(i<N-1) printf(" ");
}
return 0;
}
