PTA甲级—常用技巧与算法

散列

1078 Hashing (25 分)

Quadratic probing (with positive increments only) is used to solve the collisions.

这句话说的是使用平方探测法来解决哈希冲突，Linear Probing（线性探测法）、Quadratic probing（平方探测法）这种专业术语在平常的学习中应当认真记忆而不是认为不重要，因为这句话一开始看不懂，想当然认不重要就略过了，那结果多半WA。

知道了解决办法之后，需要处理的一个问题就是我们如何知道插入失败？

假设$x<y$，由$h(k) + x^2 = h(k) + y^2 \quad (mod \ p)$得：

$$ x^2 = y^2 \quad(mod \ p)$$

$$ (x-y)(x+y) = 0 \quad(mod \ p)$$

由上述式子推导可发现$p$是一个循环节，如果从$0 \sim p-1$进行枚举仍然找不到位置的话即可认为插入失败

这道题要求的是$with \ positive \ increments \ only$，去掉这个限制条件后，以增量序列$1^2, -1^2, 2^2, -2^2 \dots, x^2, -x^2$且$x<=p/2$循环试探下一个存储地址即可，证明同上可得（tips:大与2/p的部分可以由p减去小于2/p的部分得到）

还需要注意的一个点：1不是素数，需要在isPrime函数中加以判断

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

#include <iostream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#define ll long long

#define inf 0x3f3f3f3f

#define pb push_back

#define pii pair<int,int>

using namespace std;

const int maxn = 1e6+100;

int p, n, tmp;

bool vis[maxn];

bool isPrime(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(){

    scanf("%d%d", &p, &n);

    while(!isPrime(p)) p++;

    while(n--){

        scanf("%d", &tmp);

        int x = tmp%p, y = x, inc = -1;

        while(inc<p&&vis[y]) inc++, y = (x+inc*inc)%p;

        if(inc!=p) printf("%d", y), vis[y] = 1;

        else printf("-");

        if(n) printf(" ");

    }

}

补充资料：

线性探测是按线性方法一个一个找，只要表里有空位总能将元素填入；而二次探测有可能出现表中有空间但平方探测找不到的情况

线性探测容易聚集，二次探测聚集情况较线性探测要好。

二次探测有时候探测不到整个散列表空间，是其一大缺陷。但是经过数学家的研究，散列表长度TableSize是某个4k＋3（k是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间.

Reference:

https://www.icourse163.org/learn/ZJU-93001?tid=1003997005#/learn/content?type=detail&id=1007588520

https://www.nowcoder.com/discuss/67780

https://en.wikipedia.org/wiki/Quadratic_probing

https://blog.csdn.net/qq_37142034/article/details/87903983

https://blog.csdn.net/pennyliang/article/details/5446961

1145 Hashing - Average Search Time (25 分)

这道题相当于1078的扩展，关键在于如何求不在散列表中的元素的平均查找次数。边界值显然为p+1，当查找到已经查找过的单元格后就知道查找失败了；在这个过程中如果发现有空位也能说明该元素不在单元格中

#include <cstdio>

using namespace std;

const int maxn = 1e6+100;

int p, n, m, tmp, h[maxn];

bool vis[maxn];

bool isPrime(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(){

    scanf("%d%d%d", &p, &n, &m);

    while(!isPrime(p)) p++;

    while(n--){

        scanf("%d", &tmp);

        int x = tmp%p, y = x, inc = 0;

        while(vis[y]&&++inc<p) y = (x+inc*inc)%p;

        if(inc!=p) h[y] = tmp, vis[y] = 1;

        else printf("%d cannot be inserted.\n", tmp);

    }

    int cnt = m, sum = 0;

    while(m--){

        scanf("%d", &tmp);

        int x = tmp%p, y = x, inc = 0;

        while(h[y]!=tmp&&vis[y]&&++inc<p) y = (x+inc*inc)%p;

        sum += inc+1;

    }

    printf("%.1f", 1.0*sum/cnt);

}

巴特西

PTA甲级—常用技巧与算法

最新文章

热门文章