Hash在信息學(xué)競賽中的一類應(yīng)用_第1頁
Hash在信息學(xué)競賽中的一類應(yīng)用_第2頁
Hash在信息學(xué)競賽中的一類應(yīng)用_第3頁
Hash在信息學(xué)競賽中的一類應(yīng)用_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、 能的 N（因為 ( N + 1 N +1 在 N10 時顯然大于 10，不可能位數(shù)相同） ，剩下的工作就是判斷 NN 這個 N 滿不滿足 NN=S。顯然，算對數(shù)是不可取的，因為實數(shù)類型沒有這么高的精度。同理， 高精度計算也是難以實現(xiàn)的（即使是 FFT 也面臨著時間復(fù)雜度的挑戰(zhàn)）聯(lián)系到前面的例題， 可以想到，找到一個 Hash 函數(shù) f(x，通過比較 f(NN和 f(S是否相同即可確定 NN 是否和 S 相 等。同時，這個 f(x還要滿足，如果 x=ab，則可以方便地通過 f(a和 f(b來計算得到 f(x，以 便可以不把 NN 計算出來就直接比較。 一個很簡單但是很有效的 Hash 函數(shù)就是

2、取余！即，f(x=x mod p。如果 x=ab，則 f(x= f(a f(b mod p。 對于原題（S 和 NN 最多相差一位） ，只要 p 不能被 10 整除，即可保證判斷的準確性。 而改編之后的題目呢（S 可以修改任意位）？取若干個 p，由于 S 的長度限制（只有 500000）位，不超過 130000 以內(nèi)質(zhì)數(shù)的乘積。換句話說，在 500000 內(nèi)隨便取一個 p，恰好 能被|S-NN|整除的可能性只有大約 1/4，如果多取一些，或者再加大 p 的范圍就可以幾乎肯定 判斷是正確的了。 【總結(jié)】 Hash 函數(shù)除了做為 Hash 表的輔助工具， 在單獨使用的時候可以實現(xiàn)幾乎肯定地判斷兩

3、個數(shù)據(jù)是否相同或等價。Hash 函數(shù)的本質(zhì)是對含有較大信息量的信息加以“概括” 。因此在 遇到需要頻繁比較兩個數(shù)據(jù)是否相同的操作的問題時，不妨考慮使用 Hash 函數(shù)作為解題的 工具。 有時使用 Hash 函數(shù)會犧牲一定的正確性，而且使用 Hash 函數(shù)的算法看上去也不夠優(yōu) 美。但是靈活使用 Hash 函數(shù)，可以化難為易，解決一些原來難以解決的問題。也往往可以 用較短的代碼獲得較高的效率。 盡管有所舍棄，卻也有所收獲；正因為有所舍棄，才會有所收獲。在選擇算法的時候， 總會遇到這樣的矛盾，有失必有得，有得也必有失，選擇恰當?shù)倪m合題目也適合自己思維習(xí) 慣的算法才是最好的。 【參考文獻】 劉汝佳 黃亮算法藝術(shù)與信息

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論