信息學(xué)奧賽課課通第7單元第9課哈希表課件

1、例1、用哈希表存儲(chǔ)以下線性表(18,75,60,43,54,90,46,問(wèn)題分析： 假設(shè)選取的哈希函數(shù)為h(k)=k mod m,k為元素的關(guān)鍵字，m為哈希表的長(zhǎng)度，用余數(shù)作為存儲(chǔ)該元素的哈希地址。k和m均為正整數(shù)，并且m要大于或等于線性表的長(zhǎng)度n。此例n=7,故取m=13就已經(jīng)足夠，得到的每個(gè)元素的哈希地址為： h(18)=18 mod 13=5 h(75)=75 mod 13=10 h(60)=60 mod 13=8 h(43)=43 mod 13=4 h(90)=90 mod 13=12 h(46)=46 mod 13=7,根據(jù)哈希地址，依次把元素存儲(chǔ)到哈希表H(0m-1)中的效果如下,

2、當(dāng)然，這是一個(gè)比較理想的情況，假如要再往表中插入第8個(gè)元素30,h(30)=30 mod 13=4，會(huì)發(fā)現(xiàn)H4已經(jīng)存放了43,此時(shí)就發(fā)生了沖突，那么就可以從H4往后按順序找一個(gè)空位置存放30,即可以把它插入到H6中,H,例2:分身數(shù)對(duì)。(sumx,1s,256MB,問(wèn)題描述： 給出n個(gè)不同的正整數(shù)a1an,它們的值在11000000之間。再給定一個(gè)整數(shù)x，編程計(jì)算這樣的數(shù)對(duì)個(gè)數(shù)(ai,aj),1=ij=n并且ai+aj=x,輸入格式： 第1行1個(gè)正整數(shù)n,1=n=100000。 第2行n個(gè)正整數(shù),表示元素a1an,每?jī)蓚€(gè)數(shù)之間用一個(gè)空格分隔。 第3行1個(gè)正整數(shù)x，1=x=2000000。 輸出

3、格式： 1行，1個(gè)整數(shù)，表示這樣的數(shù)對(duì)個(gè)數(shù)。 輸入樣例： 9 5 12 7 10 9 1 2 3 11 13 輸出樣例： 3,樣例說(shuō)明： 不同的和為13的數(shù)對(duì)是(12,1),(10,3)和(2,11)共3對(duì)。 問(wèn)題分析： 如果使用雙重循環(huán)來(lái)查找，本題是要超時(shí)的。用哈希表來(lái)處理，定義ax代表x這個(gè)數(shù)在數(shù)列中是否存在，1代表存在，0代表不存在，那么只需要掃描1x/2，若數(shù)字存在，那么只需要查看x減去這個(gè)數(shù)的結(jié)果在數(shù)列里是否存在，若存在就增加一對(duì)數(shù)列,例3：明明的隨機(jī)數(shù)(noip2016普及組復(fù)賽,randam,1s,256MB,問(wèn)題描述: 明明想在學(xué)校中請(qǐng)一些同學(xué)一起做一項(xiàng)問(wèn)卷調(diào)查，為了實(shí)驗(yàn)的客觀

4、性，他先用計(jì)算機(jī)生成了N個(gè)1到1000之間的隨機(jī)整數(shù)（N100），對(duì)于其中重復(fù)的數(shù)字，只保留一個(gè)，把其余相同的數(shù)去掉，不同的數(shù)對(duì)應(yīng)著不同的學(xué)生的學(xué)號(hào)。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請(qǐng)你協(xié)助明明完成“去重”與“排序”的工作,輸入格式 輸入有2行，第1行為1個(gè)正整數(shù)，表示所生成的隨機(jī)數(shù)的個(gè)數(shù)N。 第2行有N個(gè)用空格隔開(kāi)的正整數(shù)，為所產(chǎn)生的隨機(jī)數(shù)。 輸出格式 輸出也是2行，第1行為1個(gè)正整數(shù)M，表示不相同的隨機(jī)數(shù)的個(gè)數(shù)。第2行為M個(gè)用空格隔開(kāi)的正整數(shù)，為從小到大排好序的不相同的隨機(jī)數(shù)。 樣例輸入 10 20 40 32 67 40 20 89 300 400 15 樣例輸

5、出 8 15 20 32 40 67 89 300 400,問(wèn)題分析： 因?yàn)閚=100，可以使用冒泡排序、插入排序、選擇排序等時(shí)間復(fù)雜度為O(n2)的算法實(shí)現(xiàn)，這樣做不會(huì)超時(shí)。實(shí)際上，對(duì)于產(chǎn)生的隨機(jī)數(shù)ai，由于0ai1001,且ai為整數(shù)。所以，可以使用哈希表ai=0表示沒(méi)有i這個(gè)數(shù)，ai=1表示有i這個(gè)數(shù)。那么，每次讀一個(gè)i，把a(bǔ)i賦值為1,讀完所有數(shù)據(jù)后，只要再掃描一下這個(gè)數(shù)組就可完成統(tǒng)計(jì)和排序輸出任務(wù)。這種方法類(lèi)似“桶排序”原理,練習(xí)1：整數(shù)集合(sumsets,1s,256MB,問(wèn)題描述： 給定一個(gè)整數(shù)集合s，請(qǐng)你尋找一個(gè)最大的d，使得a+b+c=d，并且a、b、c、d都是集合中的元素

6、。 輸入格式： 若干集合s。 對(duì)于每個(gè)集合s的第1行包含1個(gè)整數(shù)n,1=n=1000，表示集合中元素的個(gè)數(shù)。隨后有n行，每一行一個(gè)整數(shù)，表示集合s中的元素，每個(gè)整數(shù)的范圍是536870912,536870911. 輸入的最后一行包含一個(gè)0。 輸出格式： 對(duì)于每個(gè)集合s，輸出一行一個(gè)整數(shù)d，或者“No Solution”表示無(wú)解,輸入樣例： 5 2 3 5 7 12 5 2 16 64 256 1024 0 輸出樣例： 12 No Solution,練習(xí)2：生日(birthday,1s,256MB,問(wèn)題描述： 多多今天很高興，因?yàn)樗暮门笥烟O(píng)果要過(guò)生日了。由于今天多多得到了兩張價(jià)值不菲的SHOP

7、購(gòu)物券，所以他決定買(mǎi)N件禮物送給蘋(píng)果。 一個(gè)下午過(guò)去了，多多選好了N件禮物，并且它們的價(jià)格之和恰好為兩張購(gòu)物券的面額這和。當(dāng)多多被自己的聰明所折服，高興地去結(jié)賬時(shí)，他突然發(fā)現(xiàn)SHOP對(duì)購(gòu)物券的使用有非常嚴(yán)格的規(guī)定：一次只允許使用一張，不找零，不與現(xiàn)金混用。多多身上根本沒(méi)有現(xiàn)金，并且他不愿意放棄挑選好的禮物。這就意味著，他只能通過(guò)這兩張購(gòu)物券結(jié)賬，而且每一張購(gòu)物券所購(gòu)買(mǎi)的物品總價(jià)格，必須精確地等于這張購(gòu)物券的面額。 怎樣才能順利地買(mǎi)回這N件禮物送給蘋(píng)果呢？本題的任務(wù)就是幫助多多確定是否存在一個(gè)購(gòu)買(mǎi)方案。已知其中一張購(gòu)物券的面額以及所有商品的價(jià)格，只需要確定能否找到一種方案使得選出來(lái)的物品的價(jià)格總和正好是這張購(gòu)物券的面額即可,輸入格式： 有多組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)的第一行為兩個(gè)整數(shù)N和M，分別表示多多一共挑選了N個(gè)物品送給蘋(píng)果以及多多的一張購(gòu)物券的面額為M。接下來(lái)的一行有N個(gè)用空格隔開(kāi)的正整數(shù)，第i個(gè)數(shù)表示第i個(gè)物品的價(jià)格。 輸出格式： 包含若干行，每行一個(gè)單詞“YES”或者“NO”，分別代表存在一個(gè)購(gòu)買(mǎi)方案或不存在一個(gè)購(gòu)買(mǎi)方案。 輸入樣例： 10 2000 1000 100 200 300 400 500 700 600 900 800 10 2290 1000 10