1、中國礦業大學全校通識選修課數學建模與算法設計課程論文題目：對火車站身份證號碼校核的分析成績：評閱人：姓名 學院 化工學院 班級 能源化學工程14-1 學號 我的郵箱是：ziqiang_xu時間：摘要計算機在生活中扮演著越來越重要的角色，并且已經為人類的進步做出過巨大貢獻。比如航空航天、軍事、天氣預測、工程模擬等等諸多領域。計算機作為高速計算模擬設備，除了需要先進的硬件制造工藝之外，還需要優秀的軟件的配合。而軟件的核心是算法，高性能的算法才能合理的調動有效的資源。老師在上課的時候講了一個關于火車站身份證核查的問題，我覺得有更好的方法來進行查詢。并且估計目前所采用的正是這樣的方法。中國居民身份證號

2、碼是中國公民的識別碼，居民身份證是國家法定的證明個人身份的證件。中國的人口規模大概是十四億。關鍵詞：算法；查詢；身份證號碼；分段；結構；地址碼；出生日期碼；順序碼；校驗碼；模擬；python；C語言；計算機；火車站。正文1、 問題描述：在火車站，為了掌握乘客的真實信息，工作人員需要對乘客的身份進行核查，一般是對身份證進行核查，并使用儀器進行掃描識別。需要讀取身份證號碼，并從身份證數據庫里獲取照片和更加詳細的信息。中國有近十四億人口，如果逐一進行比對查詢，將會有一個十分龐大的計算量產生。試分析使用枚舉比對方法，并指出它的弊端，并提出一個更好的核對辦法。2、 問題分析與解決方案：（1）枚舉法：大家

3、都十分熟悉，在進行身份證掃描的時候，是一個識別終端讀取身份證信息，然后傳到工作人員的電腦里；再上傳到國家的身份證服務站，服務站反饋乘客的信息，如是否存在此條數據以及乘客照片；工作人員再進一步進行核實。（考慮到信息安全，全國公民的信息被完全下載在本地電腦的可能性非常低）對十四億組數據進行逐一比對的方法是簡單的，但是絕對是不可取的。這種方法對計算機資源占用太大。根據概率論的知識，x表示核查一個人的身份證號碼需要進行的數據比對的次數，則x的期望E（x）=7億。為了進行進一步的驗證7億次查詢的計算量的巨大，由于不會使用c語言，我使用python語言對查詢過程進行模擬。先隨機產生7000萬條數據（由于p

4、ython語言的設計，一個元組不能容納7億條數據，故此處只生成了7000萬條數據，并執行十次用以模擬對七億條數據進行檢索比對。）python是解釋性的腳本編程語言，在性能上弱于C語言，但是單純從打印性能上有數據表明大約是2比3的比例，參考地址見參考文獻： 預測C語言和Python在檢索的性能上比值不會超過3倍，以此由圖2的運行結果看可以得出一個粗略估計的檢索比對耗時：以當前硬件配置（如圖3）進行檢索查詢的話，至少會耗費大約70秒的時間。 考慮到實際情況下數據的處理是在云端進行，故云端計算機的性能是咱們普通PC不可比擬的，進行一次數據檢索的時間必定會大大減少。這是不可否認的，但是還應該充分考慮到

5、：同一時間線上會有多個查詢請求并行發生，即全國各地都在進行著身份證的校核。這又會進一步增加這一算法的的復雜度，就算云端服務器的性能十分強勁，也是有很大的壓力的，很有可能會對其他業務造成干擾，甚至導致宕機這樣的重大事故發生。源代碼圖片（圖1）運行結果（圖2）計算機配置截圖（圖3）(2) 分段檢索法：要高效率地對身份證號碼進行檢索校核，必須要深入了解身份證號碼的規律。通過查詢百度百科，可以了解到：居民身份證號碼，根據中華人民共和國國家標準 GB 11643-1999中有關公民身份號碼的規定，公民身份號碼是特征組合碼，由十七位數字本體碼和一位數字校驗碼組成。排列順序從左至右依次為：六位數字地址碼，八

6、位數字出生日期碼，三位數字順序碼和一位數字校驗碼。 居民身份證是國家法定的證明公民個人身份的有效證件。關于地址碼：第一、二位表示省（自治區、直轄市、特別行政區）；第三、四位表示市（地級市、自治州、盟及國家直轄市所屬市轄區和縣的匯總碼）。其中，01-20，51-70表示省直轄市；21-50表示地區（自治州、盟）；第五、六位表示縣（市轄區、縣級市、旗）。01-18表示市轄區或地區（自治州、盟）轄縣級市；21-80表示縣（旗）；81-99表示省直轄縣級市。關于出生日期碼：（身份證號碼第七位到第十四位）表示編碼對象出生的年、月、日，其中年份用四位數字表示，年、月、日之間不用分隔符。例如：1981年05

7、月11日就用19810511表示。關于順序碼：（身份證號碼第十五位到十七位）地址碼所標識的區域范圍內，對同年、月、日出生的人員編定的順序號。其中第十七位奇數分給男性，偶數分給女性。關于校驗碼： 作為尾號的校驗碼，是由號碼編制單位按統一的公式計算出來的，如果某人的尾號是0-9，都不會出現X，但如果尾號是10，那么就得用X來代替，因為如果用10做尾號，那么此人的身份證就變成了19位，而19位的號碼違反了國家標準，并且中國的計算機應用系統也不承認19位的身份證號碼。是羅馬數字的10，用X來代替10，可以保證公民的身份證符合國家標準。現在假設工作人員通過設備獲取了一位乘客的身份證號碼為： 500382

8、 19970116 465 81 地址碼（前六位）：500382 重慶市合川區（155萬人口，2013年數據）2 出生日期碼（7-14位）： 1997年01月16日3 順序碼（15-17位）： 4654 校驗碼（最后一位）： 8此處的分段檢索法是在枚舉法的基礎上進行改進的，在枚舉法之前進行幾步操作，分層進行檢索，逐步地縮小檢索范圍。在服務器的數據庫里，如果單方面地從查找速度上考慮的話，為身份證信息加入合適的層級，比如性別，校驗碼等，可以進一步地提高查找速度。即咱們經常聽說的樹狀結構，有多個層級，對信息進行有條理的分類。示意圖如圖4所示：圖4第一步：根據前六位號碼先確定了地址，如戶籍所在地是重慶

9、市合川區。檢索地址碼耗時，如果不進行分層處理大約幾萬條，一萬條數據在我的電腦上的運算耗時是6微秒，幾乎可以忽略不計。第二步：即使不再繼續縮小范圍而是直接進行檢索，枚舉150萬條信息，（普通的區縣是沒有這么多人口的，有這么多人口是少數情況，故在普通狀況下檢索量會更小一些）在與之前一樣的硬件條件下耗時約0.133秒，如圖5所示。這與之前的70秒相比較，是一個非常大的提升，極大地提高了查找效率，如果更進一步進行更加嚴密的分類，即使是一般的手持設備也能勝任這項任務。150萬條數據檢索模擬結果（圖5）3、 結論： 更優的計算機算法能夠更加節省計算機硬件資源，更加高效地為我們工作。研究算法不是誰的專利，就

10、算作為一個非專業研究算法的人，對一些算法進行學習和研究是很有益處的。在現實生活中，一些算法問題的有效解決也將節約大量的資源。所以研究算法是十分有必要的，在此，向算法研究者致敬，我將努力在我所在的領域做出成績，并在需要的時候，向算法研究者尋求幫助，也將做出有效的反饋供研究者更好地進行分析。參考文獻：1、 Python和C語言打印性能對比：2、重慶市合川區人口數據來源：【注：關于身份證的相關標準是由網絡上的資料整理所得，Python和C語言的性能對比也是引用了網友的帖子，并沒有進行嚴格的測試。】【附：Python數據查詢模擬代碼身份證號碼樣本：一個虛假身份證號和隨機數進行加和運算得來程序一（可自由

11、輸入不不大于7000萬的枚舉條數，主要用于測試小查詢量耗時）：from time import *from random import *list_7000=x=int(input('輸入模擬的數據枚舉條數n')num=0for i in range(n): h=int(100000*random() list_7000.append(x+h)start=time()print(str(start)+'n')for i in list_7000: if i num=num+1pri

12、nt('已經找到'+str(num)+'個n')endtime=time()print(str(endtime)+'n')print('總共耗時'+str(endtime-start)+'秒')程序二（模擬7億次數據查詢）：from time import *from random import *list_7000=xum=0for i in range(70000000): h=int(100000*random() list_7000.append(x+h)start=time()print(str(start)for j i