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

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

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

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

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

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

6、。 輸入格式： 若干集合s。 對于每個集合s的第1行包含1個整數(shù)n,1=n=1000，表示集合中元素的個數(shù)。隨后有n行，每一行一個整數(shù)，表示集合s中的元素，每個整數(shù)的范圍是536870912,536870911. 輸入的最后一行包含一個0。 輸出格式： 對于每個集合s，輸出一行一個整數(shù)d，或者“No Solution”表示無解,輸入樣例： 5 2 3 5 7 12 5 2 16 64 256 1024 0 輸出樣例： 12 No Solution,練習(xí)2：生日(birthday,1s,256MB,問題描述： 多多今天很高興，因為他的好朋友蘋果要過生日了。由于今天多多得到了兩張價值不菲的SHOP

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