u8,u8国际,u8国际官方网站,u8国际网站,u8国际网址,u8国际链接,u8体育,u8体育官网,u8体育网址,u8注册,u8体育网址,u8官方网站,u8体育APP,u8体育登录,u8体育入口

　　浅谈竞赛中哈希表的应用 哈尔滨市第三小学刘狮 ［关键词］应用哈希表数据结构 ［摘要］ 哈希表是一种高效的数据结构。本文分五个部分：首先提出了哈 希表的优点，其次介绍了它的基础操作，接着从简单的例子中作了效 率对比，指出其适用范围以及特点，然后通过例子说明了如何在题目 中运用哈希表以及需要注意的问题，最后总结全文。 ［正文］ 引言 哈希表(Hash Table)的应用近两年才在NOI中出现，作为一种高效的数据结 构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可 以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越 來越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的 特点之一。 哈希表又叫做散列表，分为“开散列”和“闭散列”。考虑到竞赛时多数人 通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列”，关于其他方而 读者可参阅其他书籍。 基础操作 2.1基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数 (哈希函数，也叫做散列函数)，使得每个元索的关键字都与一个函数值 (即数组下标)和对应，于是用这个数组单元來存储这个元素；也可以简 单的理解为，按照关键字为每一个元索“分类”，然后将这个元索存储在 相应“类”所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极 有可能岀现对于不同的元索，却计算出了相同的函数值，这样就产生了“冲 突”,换句话说，就是把不同的元素分在了和同的“类” Z中。后面我们 将看到一种解决“冲突”的简便做法。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 2. 2函数构造 构造函数的常用方法(下面为了叙述简洁，设h(k)表示关键字为k 的元素所对应的函数值)： 除余法： 选择一个适当的正整数p ,令h(k ) = k mod p 这里，p如果选取的是比较大的素数，效果比较好。而 且此法非常容易实现，因此是最常用的方法。 数字选择法： 如果关键字的位数比较多，超过长整型范围而无法直接运 算，可以选择具屮数字分布比较均匀的若干位，所组成的新的 值作为关键字或者直接作为函数值。 2. 3冲突处理 线性重新散列技术易于实现且可以较好的达到口的。令数组兀素个数 为S ,则当h(k)已经存储了元素的时候，依次探查(h(k)+i) mod S , i=l,2,3……，直到找到空的存储单元为止(或者从头到尾扫描一圈仍未发 现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩人 数组范围避免的)。 2.4支持运算 哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算 (h(x))、插入元索(insert)、查找元素(membei*)。 设插入的元素的关键字为x , A为存储的数组。 初始化比较容易，例如 const empty=maxlongint; //用非常人的整数代表这个位置没有存储元索 p=9997; II表的大小 procedure make null; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： function h(x:longint):lnteger; begin h:= x mod p; end; 我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元 素若存在，它应该存储在什么位置，因此加入一个定位的函数locate function locate(x:lorigint):integer; var orig,i:integer; begin orig:=h(x); i:=0; while (iS)and(A[(orig+i)mod S]x)and(A[(orig+i)mod S]empty) do inc(i); 〃当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元 〃素存储的单元，要么表已经满了 locate:=(orig+i) mod S; end; 插入元素 procedure insert(x:longint); var posi:integer; begin posi:=locate(x); 〃定位函数的返回值 if A[posi]=empty then A[posi]:=x else error; //error即为发牛了错误，当然这是町以避免的 end; 查找元素是否己经在表中 procedure member(x:longint):boolean; var posi:integer; begin posi:=locate(x); if A[posi]=x then member:=true else member:=false; end; 这些就是建立在哈希表上的常用基本运算。 下文提到的所有程序都能在附录q找到。 效率对比 3.1简单的例子与实验 下面是一个比较简单的例了: 集合(Subset) 问题描述： 给定两个集合A、B,集合内的任一元素x满足/ Wx W疋,并且每个集合的元索个 数不大于104个。我们希望求出A、B之间的关系。只需确定在B中但是不在A中的元素 的个数即可。 这个题廿是根据OIBHNOIP2002模拟赛#1的第一题改编的。 分析:我们先不管A与B的具体关系如何，注意到这个问题的本质 就是对于给定的集合A ,确定B中的元素是否在A中。所以，我们使 用哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大 了原题的数据规模，H(x) = x mod 15889; 当然本题可以利用别的方法解决，所以选取了速度最快的快速排序+ 二分查找，让这两种方法作效率对比。 我们假定IAI=IBI ,对于随机生成的数据，计算程序重复运行50次 所用吋间。 对比表格如下： 哈希表(sec) 快速排序+二分查找(sec) 复杂度 O(N)(只有忽略了冲突才是这 个结果。当然实际情况会比这 个大，但是重复的儿率与哈希 函数有关，不容易估计) O(N log N+ N) = O(N log N) 测试数据规模 500 0.957 0.578 1000 1.101 0.825 2500 1.476 1.565 5000 2.145 2.820 7500 2.905 4.203 10000 3.740 5.579 13500 7.775 7.753 15000 27.550 673 对于数据的说明:在Celeron566下用TP测试，为了使时间的差距明显, 让程序重复运了行50次。同时哈希表中的甘15889 ,下标范围0..15888。 出于快速排序不稳定，因此使用了随机数据。 3. 2对试验结果的分析: 注意到两个程序的用时并不像我们期槊的那样，总是哈希表快。设 哈希表的大小为P. 首先，当规模比较小的时候（大约为a10%*P,这个数据仅仅是通 过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。 这是由于，虽然每次计算哈希函数用0（1）的时间，但是这个系数比较大。 例如这道题的H（x）=x mod 15589 ,通过与做同样次数的加法相比较,测 试发现系数 12 ,因为mod运算本身与快速排序的比较大小和交换元 素运算相比，比较费时间。所以规模小的时候，O（N）（忽略冲突）的算法 反而不如O（NlogN）o这-一点在更复朵的哈希函数上会体现的更明显，因 为更复杂的函数系数会更大。 其次，当规模稍大（大约为15%*Pvav85%*P）的时候，很明显 哈希表的效率高。这是因为冲突的次数较少。 再次，当规模再大（大约为90%*P a P ）的时候，哈希表的效 率大幅下降。这是因为冲突的次数大大提高了，为了解决冲突，程序不得 不遍历一段都存储了元索的数组空间来寻找空位置。用白箱测试的方法统 计，当规模为13500的时候，为了找空位置，线次运算，某 些数据其至能达到4265833次。显然浪费这么多次运算来解决冲突是不合 算的，解决这个问题可以扩大表的规模，或者使用“开散列”（尽管它是 动态数据结构）。然而需要指出的是，冲突是不可避免的。 初步结论: 当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现 高效的特点，甚至述不如一般算法。但是如果规模在屮央，它高效的特点 可以充分体现。我们可以从图像直观的观察到这一点。 其他方法 其他方法 哈希表 试验表明当元素充满哈希表的90%的吋候，效率就已经开始明显下 降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大（由 于竞赛屮可利用内存越来越多，大数组通常不是问题，当然也有少数情况 例外)，但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。 通常使它的容量至少是题目最大需求的120% ,效果比较好(这个仅仅是 经验，没有严格证明)。 应用举例 4.1应用的简单原则 什么时候适合应用哈希表呢？如果发现解决这个问题吋经常要询问： “某个元素是否在已知集合中？ ”，也就是需要高效的数据存储和查找， 则使用哈希表是最好不过的了！那么，在应用哈希表的过程屮，值得注意 的是什么呢？ 哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突 的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因 此我们的目标就是尽力避免冲突。前面提到，在使用“除余法”的时候， h(k)=kmodp , p最好是一个大素数。这就是为了尽力避免冲突。为什么 呢？假设p=1000，则哈希函数分类的标准实际上就变成了按照末三位数 分类，这样最多1000类，冲突会很多。般地说，如果p的约数越多， 那么冲突的几率就越大。 简单的证明：假设P是一个有较多约数的数，同时在数据中存在q 满足 gcd(p,q)=d 1 ,即有 p=a*d , q=b*d, 则冇 q mod p= q - p* ［q div p］ =q-p*［b diva］.① 其中［b div a ］的取值范围是不会超过［0, b］的正整 数。也就是说，［b div a］的值只有b+1种可能，而p是一个预先确定 的数。因此 ① 式的值就只有b+1种可能了。这样，虽然mod运算之后 的余数仍然在［0, p-1］内，但是它的取值仅限于①可能取到的那些值。 也就是说余数的分布变得不均匀了。容易看出，p的约数越多，发生这 种余数分布不均匀的情况就越频繁，冲突的儿率越高。而素数的约数是最 少的，因此我们选用大素数。记住“素数是我们的得力助手”。 另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个 几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样 的函数设计很浪费时间而冃编码一定很复杂，与其花费这么大的精力去设 计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数 还需要易于编码，即易于实现。 综上所述，设计一个好的哈希函数是很关键的。而“好”的标准，就 是较低的冲突率和易于实现。 另外，使用哈希表并不是记住了前而的基本操作就能以不变应万变 的。有的时候，需要按照题目的要求对哈希表的结构作一些改进。往往一 些简单的改进就可以带来巨大的方便。 这些只是一般原则，真正遇到试题的时候实际情况T变万化，需要具 体问题具体分析才行。下面，我们看几个例了，看看这些原则是如何体现 的。 有关字符串的例子 我们经常会遇到处理字符串的问题，下面我们來看这个例了: 找名字 问题描述： 给定一个全部由字符串组成的字典，字符串全部rh大写字母构成。其中为每个字符串编 写密码，编写的方式是対于n位字符串，给总一个n位数，大写字母与数字的对应方式按 照电线: D, E,F 6: M, N, 0 9: W, X, Y 4: G, H, 1 7: P, R, S 题目给出一个1——12位的数，找出在字典中出现口密码是这个数的所有字符串。字典 中字符串的个数不超过8000 o 这个是 USACO Training Gate 1.2.4 的一道题。 分析:看懂题目2后，对于给定的编码，只需耍一个回溯的过程，所 冇可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在 给定的字典中了。所以这个问题需要的还是“某个元素是否在已知集合 !?? ”由于给出的“姓名”都是字符串，因此我们可以利用字符的ASCII 码。那么，如何设计这个哈希函数呢？注意到题目给出的字典中，最多能 有5000个不同元素，而一个字符的ASCII码只能有26种不同的取值， 因此至少需耍用在3个位置上的字符(26人3 5000,但是26A2 5000 ), 于是我们就选取3个位置上的字符。由于给定的字符串的长度从1——12 都有可能，为了容易实现，选取最开始的1个字符，和最末尾的2个字符。 让这3个字符组成27进制的3位数，则这个数的值就是这个字符串的编 码。这样哈希函数就设计出来了！ 不过，由于可能出现只冇1位的字符串，在写函数代码的时候需要 特殊考虑；大素数选取13883。 这个函数是这样的： function hash(s:string):integer; var i,tmp:longint; begi n tmp:=0; ｛用来记录27进制数的值｝ if length(s)1 then begin tmp:=tmp*27+ord(s[1])-64; for i:=1 downto 0 do tmp:=tmp*27+ord(s[length(s)-i])-64; ｛取第一位和后两位｝ end else for i:=1 to 3 do tmp:=tmp*27+ord(s[1])-64;｛^长度为1的时候特殊处理｝ hash:=tmp mod 13883; end; 值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似“平 均”，但是对于大多数情况，字符串是有规律的（例如英文单词），这个吋候用呛希表反 而不好（例如英语中有很多以con开头的单词），通常用检索树解决这样的查找问题。 在广度优先搜索中应用的例子 在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点Z前先 判重。而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。 来看下面的例子： 转花盆 题意描述： 给定两个正6边形的花坛，要求求出从第一个变化到第二个的最小操作次数以 及操作方式。一次操作是：选立不在边上的一盆花，将这盆花周围的6盆花按照顺吋针 或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过3 种，对于任意两种花，数量多的花的盆数至少是数量少的屁的2倍 这是SGOI-8的一道题 分析遠先确定木题可以用广度优先搜索处理，然后來看问题的规模。 正6边形共有19个格子可以用来放花，而且根据最后一句限定条件，至 多只能存在C（2,19）*C（5,17）= 1058148种状态，用搜索完全可行。然而 操作的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在 限定时间内出解，因此想到了哈希表。那么这个哈希函数如何设计呢？注 意到19个格了组成6边形是有顺序的，而且每一个格了只有3种可能情 况，那么用3进制19位数最大3A20-1=3486784400用Cardinal完全可以 承受。于是我们将每一个状态与一个整数对应起来，使用除余法就可以了。 小结 从这两个例了可以发现，对于字符串的查找，哈希表虽然不是最好的 方法，但是每个字符都有“天生”的ASCII码，在设计哈希函数的吋候 可以直接利用。而其他方法，例如利用检索树的查找，编写代码不如哈希 表简洁。至于广度优先搜索[?的判重更是直接利用了哈希表的特点。 另外，我们看到这两个题目都是设计好哈希函数之后，直接利用前面 的基木操作就可以了，因此重点应该是在哈希函数的设计上（尽管这两个 例子的设计都很简单），需要注意题目本身可以利用的条件，以及估计值 域的范围。下面我们看两个需要在哈希表基础上作一些变化的例子。 需要微小变化的例子 下面，我们来分析一?道NOI的试题: 方程的解数 问题描述 已知一个n元髙次方程： + k2x2P2 + + 心￡“ =0 其中：X1? X2, ...,xn是未知数，，…,kn是系数，Pi,p2,...pn是指数。-H.方程中的所有数 均为整数。 假设耒知数仁XiSM,匸求这个方程的整数解的个数。 约束条件 1n6； 1M150； kxMpA + \k2M P2 + ……+ knM Pn 231 方程的整数解的个数小于2。 本题中，指数Pi(i=1,2, n)均为正整数。 这个是NOI2001的第二试屮的《方程的解数》。 分析:初看此题,题目耍求出给定的方程解的个数，这个方程在最坏 的情况下可以冇6个未知数，而且次数由输入决定。这样就不能利用数学 方法直接求出解的个数，而且注意到解的范围最多150个数，因此恐怕只 能使用枚举法了。最简单的思路是穷举所有未知数的取值，这样吋间复杂 度是O(MA6),无法承受。因此我们需要寻找更好的方法，自然想到能否 缩小枚举的范围呢？但是发现这样也有很大的困难。我们再次注意到M 的范围，若想不超时，似乎算法的复杂度上限应该是O(MT)左右，这是 因为150八3 o这就启示我们能否仅仅通过枚举3个未知数的 值来找到答案呢？如果这样，前一半式子的值S可以确定，这吋只要枚 举后3个数的值，检查他们的和是否等于-S即可。这样只相当于在 O(MT)前面加了一个系数，当然还需要预先算出1到150的齐个幕次 的值。想到了这里，问题就是如何迅速的找到某个S是否曾经出现过， 以及出现过了多少次，于是乂变成了 “某个元素是否在给定集合中”这个 问题。所以，我们述是使用哈希表解决这个问题。至于哈希函数不是问题, 还是把S的值作为关键字使用除余法即可。然而有一点需要注意，这个 例了我们不仅需要纪录某个S是否出现，出现的次数也很重要，所以可 以用一个2维数组，仅仅是加了一个存储出现次数的威而已。 Var e:array[0..max-l,1..2]of longint; {e[x,l]记录哈希函数值为 x 的 S 值，e[x,2] 记录这个S值ill现了几次} 因此insert过程也需要一些变化： procedure ins(x:longint); var posi:longint; begin posi:=locate(x); e[posi,l]:=x; inc(e[posi,2J); ｛仅仅这一条语句,就可以记录下来S出现了几次｝ end; 4.6 最后一个例子 下面我们来仔细分析下面这个问题： 迷宫的墙 题意描述： 神话屮byte山边有一个井Z迷宫。迷宫的入口在山顶。迷宫中有许多房间，每个的 颜色是以下Z-：红、绿、蓝。两个相同颜色的房间看起来相似而不可区分。每个房间里 有三口井标以1,2,3。从一个房间到另一间只有一种方式：从上面房间的井里跳到(不一定 竖冑地)井底的厉间。对以从入口厉间到达任何其他厉间。迷宫中的所有通路走向朋落在 最底部的龙宫。所有的迷宫之旅对应了一系列在相继访问的房间里选择的井的标号。这一 列数称为一个旅行计划。一个走过好儿次迷宫的英雄bytezar画好了图，然而有的房间重复 出现了多次。 输入： 笫一行有一个整数n,2=n=6000,厉间数(包括龙宫)。房间从1到n标号，较大编 号的历间再较低处(入口房间编号1 ,龙宫编号n)。接下的行描述迷宫的房间(除 了龙宫)和井。每行有一个字母，一个空格，和三个由空格分隔的整数。字母代表了房 间的颜色(C——红，Z——绿，N——蓝)，第i(i=l,2,3)个数是第i个井通往的房间号。 输出： 迷宫最少的房间数FI 这是IOI 2003中国国家集训队难题讨论活动的0020题。 应二题目的意思是给出这个迷宫的地图，去掉重复出现的房间，找 击这个迷宫的最少房间数口。于是关键就是确定什么样的房间是重复的。 通过对样例的分析，可以看出这样的房间是重复的：如果两个房间i和j (l=i,j=n-l),他们的颜色相同，而且第k(k=l,2,3)堵墙通向的房间或 者相同、或者重复。因为这样从i和j可到达的房间是完全相同的。 所以，我们只需要记录下每个房间的情况和已经被确定相同的房间， 然后挨个比较即可。于是又需要用到高效的数据存储与查找，自然想到哈 希表。然而，这里面需要对哈希表作更大的改进：首先每个房间只能是3 种颜色2—，因此针对每种颜色分别建立哈希表，可以使哈希函数的口变 量减少一个；其次述需耍纪录每个不重复的房间每堵墙都通向哪个房间， 还有哪些房间是重复的。 具体这样实现： var e:array[0..2,0..p-l,1..4]of longint; ｛0..2 代表共有 3 种颜色,O..p-1 是哈 希函数的值域，而1..4中的1..3表示三堵墙连接到那个房间，4表示这 个单元存储的是哪个节点｝ 一 r:array[l..maxn]of longint; ｛r[i]表示与i相同的节点。如果有多个节 点都是相同的，择取其屮最大的(这一点不需要特殊的操作，只要在处理 节点的时候注意就行了)｝ 至丁哈希函数，最开始我是随意的写了一个(因为越是随意的，就越 是随机的！)，定位函数是这样的： function locate(var a,b,c,d:longint):longint; var t:longint; i: integer; begin t:=r[b]*10037+r[c]*5953+r[d]*2999; ｛用 3 堵墙的值任意乘大 素数相加再取余数，使得结果分布比较随机，也就比较均匀｝ t:=t mod p; i:=0; while (e[a,(t+i)mod p, l ]0)and(e[a,(t+i)mod p,l ]rb]) do if (e[a,(t+i)mod p,2]or[c])or(e[a,(t+i)mod p,3]r[d]) then inc(i); ｛线性重新散列｝ locate:=(t+i)mod p; end; 但是后来发现完全没有必要这样做，这样的哈希函数在计算t的时候 浪费了很多时间(不过数据规模不是很大，所以这点不I?分明显)，而且 索数起到的作用也不应当是这样的。其实让r[b],r[c],r[d]组成n进制数 就完全能够达到目的了，加入了素数不仅是小规模数据计算浪费时间，对 大数据最后结果的分布平均也没有起到比n进制数更多的作用。因此改 为 t:=r[b]*sqr(n)+r[c]*n+r[d]; 当然肯定会有更好的哈希函数的。 4.7 小结 第一个例子，乍一看与哈希表毫无关系；第二个例子叙述比较复杂, 但是经过仔细分析，发现问题的本质都是确定“某个元素是否在给定集 合中”，这正是哈希表的特点。所以，不论题目的表面看起来如何，只要 木质是需要高效的数据检索，哈希表通常就是最好的选择！ 另外，这两个例子都在原来哈希表的基础上作了一些变化。第一个 例子加入了纪录某个值出现次数的域，第二个例子加入了纪录所有墙的 情况以及原节点编号的域。虽然都只是很小的变化，但是却给问题的解 决带来了不小的方便。因此我们得到提示：哈希表虽然有标准的操作， 但也不是一成不变的，需要具体问题具体分析，根据题目的要求和特点 作出相应变化。 总结 木文介绍了有关哈希表方面的内容，分析了它的特点和优点，指出 了应用需要注意的问题，并且重点举了几个例子來说明它在竞赛中的应 用。希望读者读完本文能够对哈希表有更全面的了解，并能在竞赛中应 用自如！ 参考文献: 《算法与数据结构（第二版）》 付清祥 王晓东 编著 2?《奥赛兵法信息学（计算机）》 朱全民 主编 《SG0I-8烦恼的设计师解题报告》曙光网信息学 《Data Structures》USACO Training Gate 附录： 这是我第一次写论文，水平很有限，希望大家指出我的缺点和不足! 我的邮箱i 我的邮箱 i 1 iuchong @ 下面是所冇前啲提到的程序。其中只冇SGOI-8 Flowers的程序是网上提供的标程，其余 的都是我自己写的，并且已经通过所有测试数据。 1.哈希表的程序 program subset; const max=15889; var fin,fout:text; a,b,s,j:longint; indexiarray [0. .max-1 ]of longint; Creal; function locate(t:longint):longint; var tmp:longint; begin tmp:=t mod max; while (index[tmp]0)and(index[tmp]ot) do tmp:=(tmp+l) mod max; locate:=tmp; end; procedure int(t:longint); begin index[locate(t)]:=t; end; function member(t:longint):boolean; begin if indexflocate(t)l=t then member:=true else member:二); assign(fout/subset.outf); reset(fin); rewrite(fout); close(fout); fillchar(index,sizeof(index),0); read(fin.a); for i:=l to a do begin read(fin,shu); int(shu); end; end; procedure main; var i,shu:longint; begin read(fin,b); s:=0; for i:=l to b do begin read(fin,shu); if not member(shu) then inc(s); end; end; procedure out; begin writeln(s); close(fin); end; begin t:=meml[$40:$6C]; for j:=l to 50 do begin init; main; out; end; t :=meml [ $40: $6C]?t; writeln(t/18.181818:0:8); end. 快速排序+二分查找的程序 program subset; const max=16101; var a,b,sj:longint; da:array[ 1 ..max]of longint; fin:text; t:real; procedure init; var i:longint; begin assign(fin/subset.inf); reset(fin); read(fin,a); for i:=l to a do read(fin,da[i]); end; procedure sort(m,n:longint); var p:longint; function locaterlongint; var value.i j,temp:longint; begin value:=da[(m+n) div 2]; j:=n+l; while true do begin repeat inc(i); until dafi]=value; repeat dec(j); until da[j]=value; if ij then begin temp:=dafi]; da[i]:=da[j]; da[j]:=temp; end else begin if Ioj then locate:=j else locate:=j-l;; exit; end; end; end; begin if mn then begin p:=locate; sort(m,p); sort(p+l,n); end; end; procedure main; var i,x:longint; function member(x:longint):boolean; var p,e5mid:longint; begin p:=l; e:=a; mid:=(p+e) div 2; while (pmid)and(emid)and(da[mid]ox) do begin if x=da[midl then begin member:=true; exit; end; if xda[mid] then begin e:=mid; mid:=(p+e)div 2; end else begin p:=mid; mid:=(p+e)div 2; end; end; if (da[p]=x)or(da[e]=x)or(da[mid]=x) then member:=true else member:=false; end; begin read(fin,b); s:=0; for i:=l to b do begin read(fin,x); if not member(x) then inc(s); end; end; procedure out; begin writeln(s); close(fin); end; begin t:=meml[$40:$6C]; for j:=l to 50 do begin init; sorl(l,a); main; out; end; t:=meml[$40:$6C]-t; writeln(t/l 181818:0:8); end. 《找名字》的程序 program namenum; const empty:stringfl 2]= \ value:array[2..9,1 ..3]of string=((A,,,B,,,C), (D,E,F), (G,H,T), (J,K,L), (M,N,O), (P,R,S), (T,U,V), (W,X,Y)); var fin,fout,dict:text; index:array[-1..13882]of string[ 12]; quest:string; check:boolean; function hash(s:string):integer; var i,tmp:longint; begin lmp:=0; if length(s)l then begin tmp:=tmp*27+ord(s[ 1 ])-64; for i:=l downto 0 do tmp:=tmp*27+ord(s[length(s)-i])-64; end else for i:=l to 3 do tmp:=tmp*27+ord(s[l])-64; hash:=tmp mod 13883; end; function locate(s:string):integer; var tmp,i:integer; begin tmp:=hash(s); i:=0; while (index[(i+tmp)mod 13883]os)and(index[(i+tmp)mod 13883]empty) do i:=(i+23)mod 13883; locate:=(i+tmp)mod 13883; end; procedure inl(s:string); var tmpiinteger; begin tmp:=locate(s); index[tmpl：=s; end; procedure init; var s:string; i:integer; begin assign(fin, {,d:\namenum.txt,} namenum. in); assign(fout,「d:\namenum.out} Wmenum.ouf); reset(fin); rewrite(fout); assign(dict, {fd:\dict 1 .txt1} Ylict.txf); reset(dict); fori:=0 to 13882 do index[i]:=empty; while not eof(dict) do begin readln(dicl,s); int(s); end; close(dict); readln(fin,quest); close(fin); end; function member(s:string):boolean; var tmp:integer; begin tmp:=locate(s); if index[tmp]=s then member:=true else member:=false; end; procedure work; var st:string; j:integer; procedure examin(t:integer;ch:string); var i:integer; begin if t=

　　2、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。

　　3、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。

　　4、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

　　浙江省温州市浙南名校联盟2025-2026学年高一上学期期中联考数学试题含解析.docx

　　26高考数学提分秘诀重难点34圆锥曲线中的定点、定值、定直线问题（举一反三专项训练）（全国通用）（含解析）.docx

　　26高考数学提分秘诀重难点35概率与统计的综合问题（举一反三专项训练）（全国通用）（含解析）.docx

　　26高考数学提分秘诀重难点31圆锥曲线中的切线与切点弦问题（举一反三专项训练）（全国通用）（含解析）.docx

　　26高考数学提分秘诀重难点30圆锥曲线中的弦长问题与长度和、差、商、积问题（举一反三专项训练）（全国通用）（含解析）.docx

　　26高考数学提分秘诀重难点29巧解圆锥曲线的离心率问题（举一反三专项训练）（全国通用）（含解析）.docx

　　26高考数学提分秘诀重难点28直线与圆的综合（举一反三专项训练）（全国通用）（含解析）.docx

　　26高考数学提分秘诀重难点27直线与圆中常考的最值与范围问题（举一反三专项训练）（全国通用）（含解析）.docx

　　2024-2025学年北京东城区八年级初二（上）期末数学试卷（含答案）.pdf

　　中职语文高教版基础模块上册《写景如在眼前》课件(共24张PPT).pptx

　　原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者