模拟建设官方网站,移动互联网软件开发,电脑网页打不开怎么回事,网站上面的水印怎么做的【题目来源】https://www.acwing.com/problem/content/1566/【题目描述】 将一个由若干个不同正整数构成的整数序列插入到一个哈希表中#xff0c;然后输出输入数字的位置。 哈希函数定义为 H(key)key%TSize#xff0c;其中 TSize 是哈希表的最大大小。 利用只具有正增量的二…【题目来源】https://www.acwing.com/problem/content/1566/【题目描述】 将一个由若干个不同正整数构成的整数序列插入到一个哈希表中然后输出输入数字的位置。 哈希函数定义为 H(key)key%TSize其中 TSize 是哈希表的最大大小。 利用只具有正增量的二次探测法来解决冲突。 注意哈希表的大小最好是素数如果用户给出的最大大小不是素数则必须将表大小重新定义为大于用户给出的大小的最小素数。【输入格式】 第一行包含两个整数 MSize 和 N分别表示用户定义的表的大小以及输入数字的数量。 第二行包含 N 个不同的正整数数字之间用空格隔开。【输出格式】 在一行中输出每个输入数字的相应位置索引从 0 开始数字之间用空格隔开行尾不得有多余空格。 如果无法插入某个数字则输出 -。【数据范围】 1≤MSize≤10^4, 1≤N≤MSize, 输入数字均在 [1,10^5] 范围内。【输入样例】 4 4 10 6 4 15【输出样例】 0 1 4 -【算法分析】 本算法涉及多个细节分述如下** 散列表哈希表 散列表即哈希表是根据给定关键字Key来计算出该关键字在表中存储地址的数据结构。也就是说散列表建立了关键字与存储地址之间的一种直接映射关系。将关键字映射到表中记录的地址这加快了查找速度。 模拟实现散列表的代码详见https://blog.csdn.net/hnjzsyjyj/article/details/132179868** 二次探测法 本题陈述表示采用“只具有正增量的二次探测法”解决冲突。 所谓“只具有正增量的二次探测法”即 p(H(key)di*di) mod m 。其中 m 为哈希表长度 di 为增量序列 1^22^23^2…k^2k≤m-1 H(key) 为哈希函数常采用“除留余数法”构造即 H(key)key%p 。除留余数法方便编程实现。一般情况下常选 p 为小于哈希表长度 m 的最大质数。 求小于给定数的最大素数代码参见https://blog.csdn.net/hnjzsyjyj/article/details/127699346** 大于给定数的最小素数 由于本题有段陈述“哈希表的大小最好是素数如果用户给出的最大大小不是素数则必须将表大小重新定义为大于用户给出的大小的最小素数”所以需要判断给定的数 MSize 是否为素数若不是则需要求大于给定的数 MSize 的最小素数。 求大于给定数的最小素数的代码详见https://blog.csdn.net/hnjzsyjyj/article/details/132182788
#include bits/stdc.h
using namespace std;bool isPrime(int n) {if(n1) return false;for(int i2; isqrt(n); i) {if(n%i0) return false;}return true;
}int getPrime(int n) { //Get least prime bigger than nfor(int in1; ;i) {if(isPrime(i)) {return i;break;}}
}int main(){int n;cinn;coutgetPrime(n)endl;return 0;
}/*
in:100
out:101in:1000
out:1009
*/
【算法代码】
#include bits/stdc.h
using namespace std;const int maxn1e45;
int h[maxn];
int msize,n;bool isPrime(int x) {if(x1) return false;for(int i2; isqrt(x); i) {if(x%i0) return false;}return true;
}int getPrime(int x) { //Get least prime bigger than nfor(int ix1; ; i) {if(isPrime(i)) {return i;break;}}
}int find(int x) {int tx%msize;for(int k0; kmsize; k) { //二次探测法int p(tk*k)%msize;if(!h[p]) return p;}return -1;
}int main() {scanf(%d %d,msize,n);if(!isPrime(msize)) msizegetPrime(msize);for(int i0; in; i) {int x;scanf(%d,x);int tfind(x);if(t-1) printf(-);else {h[t]x;printf(%d,t);}if(i!n-1) printf( );}return 0;
}/*
in:
4 4
10 6 4 15out:
0 1 4 -
*/
【参考文献】https://blog.csdn.net/qq_43733499/article/details/120093683https://www.acwing.com/solution/content/55930/