




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
中國剩餘定理之妙用張真誠逢甲大學講座教授中正大學榮譽教授清華大學合聘教授1中國剩餘定理之妙用張真誠11.ChineseRemainderTheorem(中國剩餘定理)2.OrderedMinimalPerfectHashingFunctions(OMPHF)3.Conclusions21.ChineseRemainderTheorem(ChineseRemainderTheorem(中國剩餘定理)韓信點兵問題:「今有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?」~(孫武孫子算經) 亦即求正整數C,使得 C≡2(mod3) C≡3(mod5) C≡2(mod7) 兩個疑問? (1)C是否存在? (2)如何求C?3ChineseRemainderTheorem(中國剩回答(1):中國剩餘定理Letr1,r2,…,rnbeintegers.anintegerC.st. C≡r1(modm1) C≡r2(modm2) . . . C≡rn(modmn)If(mi,mj)=1,4回答(1):中國剩餘定理4EX:令m1=3,m2=5,m3=7,且令r1=2,r2=3,r3=2,C=23,s.t. Cmodm1=23mod3=2, Cmodm2=23mod5=3, Cmodm3=23mod7=2.5EX:令m1=3,m2=5,m3=7,且令5回答(2):「三人同行七十稀 五樹梅花廿一枝 七子團圓正半月 除百零五便得知。」 ~(程大位算法統宗(1593))6回答(2):6亦即70×2+21×3+15×2=140+63+30=233233÷105=餘237亦即7OrderedMinimalPerfectHashingFunctions
Non-linearOrganizationEx:binarytreeLinearOrganization8OrderedMinimalPerfectHashinhashingkeytoaddresstransformationproblem:collisionparticularcases(1)one-to-onemappingand|keyspace|≤|addressspace|hPerfecthashing9hashinghPerfecthashing9Hashing(2)one-to-onemappingand|keyspace|=|addressspace|MinimalperfecthashingEx:keyset={20,21,…,217}
h(k)=kmod19isaperfecthashing10Hashing(2)one-to-onemappingaMinimalPerfectHashingsince11MinimalPerfectHashingsince11MinimalPerfectHashing(Cont.)Somequestions12MinimalPerfectHashing(Cont.MinimalPerfectHashing(Cont.)Ans(1):ChineseRemainderTheorem13MinimalPerfectHashing(Cont.MinimalPerfectHashing(Cont.)Ans(2):UsePrimeNumberFunctionsAns(3):
14MinimalPerfectHashing(Cont.MinimalPerfectHashing(Cont.)Ex:m1=4,m2=5,m3=7,m4=9
biMiiC'15MinimalPerfectHashing(Cont.Applications-12monthsEnglishidentifiersJANUARYFEBRUARYMARCHAPRILMAYJUNEJULYAUGUSTSEPTEMBEROCTOBERNOVEMBERDECEMBER16Applications-12monthsEnglishApplications-12monthsEnglishidentifiers(Cont.)(A,N)(E,B)(A,R)(P,R)(A,Y)(U,N)(U,L)(U,G)(E,P)(C,T)(O,V)(E,C)Extract(The2ndchar.,The3rdchar.)17Applications-12monthsEnglishApplications-12monthsEnglishidentifiers(Cont.)GroupLocationExtractionpairOriginalkey1123(A,N)(A,R)(A,Y)JANUARYMARCHMAY24(C,T)OCTOBOR3567(E,B)(E,C)(E,P)FEBRUARYDECEMBERSEPTEMBER48(O,V)NOVEMBER59(P,R)APRIL6101112(U,G)(U,L)(U,N)AUGUSTJULYJUNE18Applications-12monthsEnglishApplications-12monthsEnglishidentifiers(Cont.)xd(x)c(x)p(x)ABCDEFGHIJKLM03416189614272357111317192329313741xd(x)c(x)p(x)NOPQRSTUVWXYZ7891112989434753596167717379838997101H(P,R)=d(P)+(c(P)modp(R))=8+(1mod61)=8+1=919Applications-12monthsEnglish36PascalReservedWordsARRAY,AND,BEGIN,CASE,CONST,DOWNTO,DO,DIV,END,ELSE,FUNCTION,FILE,FOR,GOTO,IF,IN,LABEL,MOD,NIL,NOT,OTHERWISE,OF,OR,PROCEDURE,PROGRAM,PACKED,REPEAT,RECORD,SET,TYPE,THEN,TO,UNTIL,VAR,WITH,WHILE2036PascalReservedWordsARRAY,AA,AD,BI,CE,CS,DNDO,DV,ED,EE,FC,FEGO,IF,IN,LE,MD,NLNT,OE,OF,OR,PC,PGPK,RE,RO,ST,TE,TNTO,UI,VR,WH,WL21AA,AD,BI,CE,CS,DN21xd(x)c(x)p(x)ABCDEFGHIJKLM02358101314161791672500105732361131112357111317192329313741xd(x)c(x)p(x)NOPQRSTUVWXYZ182023262829323334177737857263311156541139434753596167717379838997101H(W,L)=d(W)+(c(W)modp(L))=34+(39mod37)=34+2=3622xd(x)c(x)p(x)A092xd(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 整形医院礼仪培训大纲
- 怎制作产品培训
- 绿色校园工作总结
- 管道保护工初级练习试题附答案
- 2025年标准版租房合同模板
- 组长工作述职报告
- 2025企业办公场地租赁合同模板
- 法治教育培训
- 脂肪烃生产工-天然气乙炔-空分-初级练习测试题附答案(一)
- 有机合成工-二期BDO-反应-高级练习卷含答案
- 湖南省长沙市麓山国际实验学校2024-2025学年高二下学期第一次学情检测化学试卷(图片版含答案)
- 行政管理本科毕业论文-中国逆城市化现象的成因及启示
- xx地块房地产项目可行性研究报告(参考)
- 知识产权法自考考点
- 2024-2025学年第二学期天域全国名校协作体高三3月联考 语文试卷(含答案)
- 2025光伏发电站绿色拆除技术规范
- 爱眼护眼知识竞赛题及答案
- 幼儿园消防安全责任人名单范文
- 道路运输企业安全风险辨识分级管控清单
- 城市轨道交通桥隧维修与养护 课件 1.1桥梁设施基础知识
- 2025年中国航空工业集团公司招聘笔试参考题库含答案解析
评论
0/150
提交评论