林厚从信息学奥赛课课通第7单元哈希表公开课一等奖市优质课赛课获奖课件

第7单元第9课哈希表信息学奥赛之数据结构例1、用哈希表存储以下线性表(18,75,60,43,54,90,46).问题分析：假设选取的哈希函数为h(k)=kmodm,k为元素的关键字，m为哈希表的长度，用余数作为存储该元素的哈希地址。k和m均为正整数，并且m要大于或等于线性表的长度n。此例n=7,故取m=13就已经足够，得到的每个元素的哈希地址为：h(18)=18mod13=5h(75)=75mod13=10h(60)=60mod13=8h(43)=43mod13=4h(90)=90mod13=12h(46)=46mod13=7根据哈希地址，依次把元素存储到哈希表H(0~m-1)中的效果如下：当然，这是一个比较理想的情况，假如要再往表中插入第8个元素30,h(30)=30mod13=4，会发现H[4]已经存放了43,此时就发生了冲突，那么就可以从H[4]往后按顺序找一个空位置存放30,即可以把它插入到H[6]中。0123456789101112

54

4318

4660

75

90H例2:分身数对。(sumx,1s,256MB)问题描述：给出n个不同的正整数a[1]~a[n],它们的值在1~1000000之间。再给定一个整数x，编程计算这样的数对个数(a[i],a[j]),1<=i<j<=n并且a[i]+a[j]=x。输入格式：第1行1个正整数n,1<=n<=100000。第2行n个正整数,表示元素a[1]~a[n],每两个数之间用一个空格分隔。第3行1个正整数x，1<=x<=2000000。输出格式：1行，1个整数，表示这样的数对个数。输入样例：951271091231113输出样例：3样例说明：不同的和为13的数对是(12,1),(10,3)和(2,11)共3对。问题分析：如果使用双重循环来查找，本题是要超时的。用哈希表来处理，定义a[x]代表x这个数在数列中是否存在，1代表存在，0代表不存在，那么只需要扫描1~x/2，若数字存在，那么只需要查看x减去这个数的结果在数列里是否存在，若存在就增加一对数列。例3：明明的随机数(noip2016普及组复赛,randam,1s,256MB)问题描述:明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。输入格式输入有2行，第1行为1个正整数，表示所生成的随机数的个数N。第2行有N个用空格隔开的正整数，为所产生的随机数。输出格式输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。样例输入102040326740208930040015样例输出8152032406789300400问题分析：因为n<=100，可以使用冒泡排序、插入排序、选择排序等时间复杂度为O(n2)的算法实现，这样做不会超时。实际上，对于产生的随机数a[i]，由于0<a[i]<1001,且a[i]为整数。所以，可以使用哈希表a[i]=0表示没有i这个数，a[i]=1表示有i这个数。那么，每次读一个i，把a[i]赋值为1,读完所有数据后，只要再扫描一下这个数组就可完成统计和排序输出任务。这种方法类似“桶排序”原理。练习1：整数集合(sumsets,1s,256MB)问题描述：给定一个整数集合s，请你寻找一个最大的d，使得a+b+c=d，并且a、b、c、d都是集合中的元素。输入格式：若干集合s。对于每个集合s的第1行包含1个整数n,1<=n<=1000，表示集合中元素的个数。随后有n行，每一行一个整数，表示集合s中的元素，每个整数的范围是[－536870912,536870911].输入的最后一行包含一个0。输出格式：对于每个集合s，输出一行一个整数d，或者“NoSolution”表示无解。输入样例：523571252166425610240输出样例：12NoSolution练习2：生日(birthday,1s,256MB)问题描述：多多今天很高兴，因为他的好朋友苹果要过生日了。由于今天多多得到了两张价值不菲的SHOP购物券，所以他决定买N件礼物送给苹果。一个下午过去了，多多选好了N件礼物，并且它们的价格之和恰好为两张购物券的面额这和。当多多被自己的聪明所折服，高兴地去结账时，他突然发现SHOP对购物券的使用有非常严格的规定：一次只允许使用一张，不找零，不与现金混用。多多身上根本没有现金，并且他不愿意放弃挑选好的礼物。这就意味着，他只能通过这两张购物券结账，而且每一张购物券所购买的物品总价格，必须精确地等于这张购物券的面额。怎样才能顺利地买回这N件礼物送给苹果呢？本题的任务就是帮助多多确定是否存在一个购买方案。已知其中一张购物券的面额以及所有商品的价格，只需要确定能否找到一种方案使得选出来的物品的价格总和正好是这张购物券的面额即可。输入格式：有多组测试数据。每组数据的第一行为两个整数N和M，分别表示多多一共挑选了N个物品送给苹果以及多多的一张购物券的面额为M。接下来的一行有N个用空格隔开的正整数，第i个数表示第i个物品的价格。输出格式：包含若干行，每行一个单词“YES”或者“NO”，分别代表存在一个购买方案或不存在一个购买方案。输入样例：102000100010020030040050070060090080010229010001002