CoCalc Shared Files(HW)ChineseRemainder.ipynb
Author: An-Chiang Chu
Views : 34
Description: (HW) PyMath 中国剩余定理

# 韩信点兵

##0 前言 韩信点兵

### 0.a 孙子算经

今有物不知其数，

──《孙子算经》


术曰：



##1 直接搜寻法

### 1.a 以 for-loop 找答案

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

print(remainder357(2,3,2))


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

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 是否有 『乙子年』呢？

$34 = 10 \times 3 + 4 = 12 \times 2 + 10$

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 判断天干地支年

In [ ]:
ti="甲乙丙丁戊己庚辛壬癸"
di="子丑寅卯辰巳午未申酉戌亥"

def DC2tidi(n):
return ???

print(DC2tidi(2018))


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 化繁为简、以简御繁

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

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 适用多组除数、余数

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 [ ]: