回分類題庫
d088: 4.數字序號轉換為雜湊表中對應的數字位置
關鍵字: 106年台中區複賽

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 132 Times / 114 Users | Submit : 316 Times / 127 Users | Accepted rate : 90%
題目加入時間 : 2018-09-06 13:57

Content: 简体中文

請利用邊界摺疊法(folding at the boundaries)和除法取餘數(modulo)來寫出一個雜湊函數(hash function),將授權碼的數字序號轉換為雜湊表中對應的數字位置。

  1. 邊界摺疊法是將數字序號分為多個固定長度的分段,本題固定3個數字為一個分段(但最後一個分段的長度會可能不足3個數字),例如12389020311256725的數字序號可以分為6個分段,x1=123, x2=890, x3=203, x4=112, x5=567, x6=25。將每一個奇數分段的值和偶數分段的反轉值相加即為對應值,例如奇數分段的值為x1=123, x3=203, x5=567,偶數分段的反轉值為x2'=098, x4'=211, x6'=52,所以相加後的對應值為123 + 203 + 567 + 98 + 211 + 52 = 1254。
  2. 除法取餘數是將邊界摺疊法相加後的對應值再除以一個固定質數後,所得餘數作為雜湊表中對應的數字位置,本題是除以固定質數997,因此1254 % 997 = 257,亦即12389020311256725的數字序號在雜湊表中對應的儲存位置為257。

本題請輸入一個數字序號(由0~9組成),此序號的長度不超過30個數字,再將此數字序號依據邊界摺疊法和除法取餘數的雜湊函數,轉換為在雜湊表中對應的數字位置進行輸出。 

Input:

由0~9組成的一串數字序號,此序號的長度不超過30個數字。

Output:

一個介於0~996之間的整數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
123456789012345678901234567890

輸入2:
1234567890123456789012345678

Sample Output :

輸出1:
10

輸出2:
917

Hint :

Author :

106年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum