人教版选修四高中化学电解池

中國剩餘定理之妙用張真誠逢甲大學講座教授中正大學榮譽教授清華大學合聘教授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(