简答题
偏难
#13154
整型关键字的平方探测法散列 本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key…
整型关键字的平方探测法散列
本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key % TSize,其中 TSize 是散列表的表长。要求用平方探测法(只增不减,即H(Key)+i2)解决冲突。
注意散列表的表长最好是个素数。如果输入给定的表长不是素数,你必须将表长重新定义为大于给定表长的最小素数。
时间限制:4000,内存限制:65536
输入
首先第一行给出两个正整数 MSize(≤ 10^4)和 N(≤ MSize),分别对应输入的表长和输入数字的个数。
随后第二行给出 N 个不重复的正整数,数字间以空格分隔。
输出
在一行中按照输入的顺序给出每个数字在散列表中的位置(下标从 0 开始)。如果某个数字无法插入,就在其位置上输出 -。输出间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
4 4 10 6 4 15
样例输出
0 1 4 -
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//该答案由AI生成
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(int num) {
if (num <= 1) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) return false;
}
return true;
}
int nextPrime(int n) {
if (n <= 1) return 2;
int prime = n;
bool found = false;
while (!found) {
prime++;
if (isPrime(prime)) found = true;
}
return prime;
}
int main() {
int MSize, N;
cin >> MSize >> N;
int TSize = MSize;
if (!isPrime(TSize)) {
TSize = nextPrime(MSize);
}
vector<int> hashTable(TSize, -1);
vector<string> results;
for (int idx = 0; idx < N; idx++) {
int key;
cin >> key;
bool inserted = false;
for (int i = 0; i < TSize; i++) {
int pos = (key % TSize + i * i) % TSize;
if (hashTable[pos] == -1) {
hashTable[pos] = key;
results.push_back(to_string(pos));
inserted = true;
break;
}
}
if (!inserted) {
results.push_back("-");
}
}
for (int i = 0; i < results.size(); i++) {
if (i > 0) cout << " ";
cout << results[i];
}
cout << endl;
return 0;
}</pre>
这道题暂未补解析。