對火車站身份證號碼校核的分析(數(shù)學(xué)建模與算法設(shè)計)

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

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

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

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

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

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

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

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

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

10、算作為一個非專業(yè)研究算法的人，對一些算法進(jìn)行學(xué)習(xí)和研究是很有益處的。在現(xiàn)實生活中，一些算法問題的有效解決也將節(jié)約大量的資源。所以研究算法是十分有必要的，在此，向算法研究者致敬，我將努力在我所在的領(lǐng)域做出成績，并在需要的時候，向算法研究者尋求幫助，也將做出有效的反饋供研究者更好地進(jìn)行分析。參考文獻(xiàn)：1、 Python和C語言打印性能對比：2、重慶市合川區(qū)人口數(shù)據(jù)來源：【注：關(guān)于身份證的相關(guān)標(biāo)準(zhǔn)是由網(wǎng)絡(luò)上的資料整理所得，Python和C語言的性能對比也是引用了網(wǎng)友的帖子，并沒有進(jìn)行嚴(yán)格的測試?！俊靖剑篜ython數(shù)據(jù)查詢模擬代碼身份證號碼樣本：一個虛假身份證號和隨機(jī)數(shù)進(jìn)行加和運算得來程序一（可自由

11、輸入不不大于7000萬的枚舉條數(shù)，主要用于測試小查詢量耗時）：from time import *from random import *list_7000=x=int(input('輸入模擬的數(shù)據(jù)枚舉條數(shù)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('已經(jīng)找到'+str(num)+'個n')endtime=time()print(str(endtime)+'n')print('總共耗時'+str(endtime-start)+'秒')程序二（模擬7億次數(shù)據(jù)查詢）：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