【PAT】1078. Hashing (25)

2024-04-12 06:18

文章标签 25 pat hashing 1078

本文主要是介绍【PAT】1078. Hashing (25)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be “H(key) = key % TSize” where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.

Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

翻译：这次问题的任务很简单：将一组特定的正整数数列插入一个哈希表，和输出输入数字的位置。哈希的方式被定义为”H(key) = key % TSize”，TSize代表哈希表的最大范围。用二次探测（只计算正向）解决冲突。
注意表的大小最好为一个素数。如果用户给的最大范围不是prime，那么你必须将表的大小重定义为大于原本的大小的最小素数。

INPUT FORMAT

Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (<=104) and N (<=MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.

翻译：每个输入文件包含一组测试数据。对于每组输入数据，第一行包括两个正整数：MSize(<=10^4)和N(<=MSIze)，分别为用户定义的表的大小和输入数字的大小。接着第二行给出N个特定正整数。一行内所有的数字之间都用空格隔开。

OUTPUT FORMAT

For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-” instead.

对于每组输入数据，输出一行输入数字的对应位置（编号从0开始）。一行内所有数字之间用空格隔开，并且末尾不能有多余空格。万一该数字无法插入，则输入“-”替代。

Sample Input:

4 4
10 6 4 15

Sample Output:

0 1 4 -

解题思路

这道题首先先找到最接近MSize的素数，我选择的是素数表。然后题目规定只能用正向二次探测处理冲突。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define INF 99999999
using namespace std;
int MSize,N;
int Hash[10010];
int ans[10010],ccount=0;
bool Prime[20010];
int init(){memset(Prime,0,sizeof(Prime));for(int i=2;i<=2*MSize;i++){if(!Prime[i]&&i>=MSize)return i;if(!Prime[i])Prime[i]=true;for(int j=2*i;j<=2*MSize;j+=i){Prime[j]=true;}}return 1;
}
void insert(int a,int M){int exp=0;while(exp<=MSize){int temp=a+exp*exp;int t=temp%M;if(!Hash[t]){Hash[t]=1;ans[ccount++]=t;return ;}else exp++;}ans[ccount++]=-1;
}
int main(){scanf("%d%d",&MSize,&N);int a;int temp=init();for(int i=0;i<N;i++){scanf("%d",&a);insert(a,temp);}for(int i=0;i<N;i++){if(i)printf(" ");if(ans[i]>=0)printf("%d",ans[i]);else printf("-");}printf("\n");return 0;
}