CoCalc Public Files(HW)ChineseRemainder.ipynbOpen with one click!
Author: An-Chiang Chu
Views : 118
Description: (HW) PyMath 中国剩余定理

韩信点兵

##0 前言 韩信点兵

0.a 孙子算经

孙子算经 中国南北朝著作,

在下卷第 26 题 『物不知数』中提到以下问题:

今有物不知其数,
三三数之剩二,
五五数之剩三,
七七数之剩二,
问物几何?
                 ──《孙子算经》

此问题为:『求一个满足以下条件的正整数:除以 3 余 2;除以 5 余 3;除以 7 余 2。』

在孙子算经中对这问题给了如下解法:

术曰:
三三数之,剩二,置一百四十;
五五数之,剩三,置六十三;
七七数之,剩二 ,置三十。
并之,得二百三十三,以二百一十减之,即得。
凡三三数之,剩一,则置七十;
五五数之,剩一,则置二十一;
七七数之,剩一,则置十五。
一百六以上,以一百五 减之,即得。

本讲主要先从暴力搜寻法,开始找到答案。

接着在以线性分解的概念来理解韩信点兵的核心方法。

##1 直接搜寻法

1.a 以 for-loop 找答案

利用迴圈直接搜尋 0 到 3×5×73\times 5\times 7 的答案就直接輸出

In [ ]:
def remainder357(r1,r2,r3): for n in range(???): if n % 3 == r1 ??? : return n print(remainder357(2,3,2))

1.b 修正程式为对任意组除数余数都能计算

请定义一个 remainderL(ds,rs) 函式可以搜寻任意多组除数与余数的关系。

remainderN([3,5,7],[2,3,2])

remainderN([3,5,7,11],[1,3,5,7])

In [5]:
def remainderL(ds,rs): N = 1 # N= ds[0]*ds[1]*ds[2]*...*ds[-1] for i in ds: ??? for n in range(N): find = True for i in range(len(ds)): if n % ds[i] != rs[i]: ??? ??? if find == True: return n print(remainderL([3,5,7],[2,3,2])) print(remainderL([3,5,7,11],[1,3,5,7])) print(remainderL([10,12],[1,3]))
23 733 189206677

1.c 是否有 『乙子年』呢?

中国的甲子记年法也与余数问题有关。

天干共 10 个:甲、乙、丙、丁、戊、己、庚、辛、壬、癸

地支共 12 个:子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥

西元 1984 为甲子年,而 2018 与 1984 相差 34 年。

34=10×3+4=12×2+1034 = 10 \times 3 + 4 = 12 \times 2 + 10

因此,2018 为 戊戌年。

而要问哪一年为 辛亥年,

则先找一个除以 10 余 7 、除以 12 余 11 的数。

可用 remianderL([10,12],[7,11]) 得到 47。

因此,辛亥年为 1984+47 = 2031 年。

至于 『乙子年』为寻找 除以 10 余 1 、除以 12 余 0 的数。

但其实不存在这样的数,请修正 remainderL 使得找不到时回传 1-1

In [2]:
def remainderL(ds,rs): N = 1 for i in ds: N*=i for n in range(N): find = True for i in range(len(ds)): if n % ds[i] != rs[i]: find = False break if find == True: return n ??? ??? print(remainderL([10,12],[1,0]))
Error

1.d 判断天干地支年

写个 DC2tidi(n) 输入西元年 n 转换为天干地支年

In [ ]:
ti="甲乙丙丁戊己庚辛壬癸" di="子丑寅卯辰巳午未申酉戌亥" def DC2tidi(n): return ??? print(DC2tidi(2018))

请利用 RemainderL 来写个 tidi2DC 输入 天干地支年转换为 西元年

In [ ]:
ti="甲乙丙丁戊己庚辛壬癸" di="子丑寅卯辰巳午未申酉戌亥" def tidi2DC(tidi): t = ti.find(tidi[0]) d = di.find(tidi[1]) return 1984+ remainderL(???) print(tidi2DC("甲午"))

2 中国剩余定理

2.a 利用中国剩余定理来计算韩信点冰问题

In [ ]:
def chineseRem357(a,b,c): return (a*70+???)% 105 print(chineseRem357(2,3,2))

2.b 化繁为简、以简御繁

先将原问题先简记为 R(2,3,2)。

中国剩余定理的核心精神就是化繁为简:

将 R(2,3,2) 化为 R(2,0,0) + R(0,3,0) + R(0,0,2)

其中 R(2,0,0) 表示的意思为 5,7 5,7 的倍数 除以 3 余 2

5×7=35=3×11+25\times 7 = 35 = 3\times 11 +2 正好为所求。

即 R(2,0,0) = 35

类似的 R(0,3,0) 为找一个 3, 7 倍数除 5 余 3

因为 3×7=21=5×4+13\times 7 = 21 = 5 \times 4 + 1

因此,将此数乘以 33 倍,得到 3×21=63=5×12+3 3\times 21 = 63 = 5\times 12 +3

即 R(0,3,0) = 63

类似的 R(0,0,2) 为找一个 3, 5 倍数除 7 余 2

因为 3×5=15=7×2+13\times 5 = 15 = 7 \times 2 + 1

因此,将此数乘以 22 倍,得到 2×15=30=7×4+2 2\times 15 = 30 = 7\times 4 +2

即 R(0,0,2) = 30

通过以下三式就可得 R(2,3,5) = R(2,0,0)+R(0,3,0) + R(0,0,2) = 35+63+ 30 = 128

而 R(0,0,0) = 105 ,因此 128+105k 为答案,最小的解为 23。

请仿照此例,做个 R357(2,3,5 ) 的计算

In [ ]:
def R357(a,b,c): R3,R5,R7 = 5*7, 7*3, 3*5 for i in range(3): if R3 * i % 3 == a: R3 = R3*i for i in range(5): if R5 * i % 5 == b: R5 = R5*i # ??? # ??? # ??? #return ???%(3*5*7) print(R357(2,3,2))

2.c 可是用于任意的除数余数

In [3]:
def CR3(d1,d2,d3,r1,r2,r3): R1,R2,R3 = d2*d3, d3*d1, d2*d1 while (R1 % d1 != r1): R1 += d2*d3 while (R2 % d2 != r2): R2 += d3*d1 # ??? # return ??? print(CR3(5,7,11,2,3,2))
332

2.d 适用多组除数、余数

在上述 CR3 程式中,只能使用固定三个数。

在此程式,要将其改为对任意除数都能适用的情况。

用 ds, rs 分别存取除数组与余数组

CRL([5,7,9],[1,3,5]))

In [4]:
def CRL(ds,rs): N = 1 for i in ds: N*=i ms = [0]*len(ds) for i in range(len(ds)): # while (???): # ??? # return(???) print(CRL([3,5,7],[2,3,2])) print(CRL([2,3,5,7],[1,2,3,4])) # print(CRL([991,997,1009],[2,5,6]))
23 53 189206677

请比对这算法与 直接搜寻法的执行时间

In [ ]:
def remainderL(ds,rs): N = 1 for i in ds: N*=i for n in range(N): find = True for i in range(len(ds)): if n % ds[i] != rs[i]: find = False break if find == True: return n print(remainderL([991,997,1009],[2,5,6]))

3 大衍求一数与中国剩余定理的结合

In [ ]: