韩信点兵
##0 前言 韩信点兵
0.a 孙子算经
在孙子算经中对这问题给了如下解法:
本讲主要先从暴力搜寻法,开始找到答案。
接着在以线性分解的概念来理解韩信点兵的核心方法。
##1 直接搜寻法
1.a 以 for-loop 找答案
利用迴圈直接搜尋 0 到 的答案就直接輸出
1.b 修正程式为对任意组除数余数都能计算
请定义一个 remainderL(ds,rs) 函式可以搜寻任意多组除数与余数的关系。
remainderN([3,5,7],[2,3,2])
remainderN([3,5,7,11],[1,3,5,7])
1.c 是否有 『乙子年』呢?
中国的甲子记年法也与余数问题有关。
天干共 10 个:甲、乙、丙、丁、戊、己、庚、辛、壬、癸
地支共 12 个:子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥
西元 1984 为甲子年,而 2018 与 1984 相差 34 年。
因此,2018 为 戊戌年。
而要问哪一年为 辛亥年,
则先找一个除以 10 余 7 、除以 12 余 11 的数。
可用 remianderL([10,12],[7,11]) 得到 47。
因此,辛亥年为 1984+47 = 2031 年。
至于 『乙子年』为寻找 除以 10 余 1 、除以 12 余 0 的数。
但其实不存在这样的数,请修正 remainderL 使得找不到时回传
1.d 判断天干地支年
写个 DC2tidi(n) 输入西元年 n 转换为天干地支年
请利用 RemainderL 来写个 tidi2DC 输入 天干地支年转换为 西元年
2 中国剩余定理
2.a 利用中国剩余定理来计算韩信点冰问题
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) 表示的意思为 的倍数 除以 3 余 2
而 正好为所求。
即 R(2,0,0) = 35
类似的 R(0,3,0) 为找一个 3, 7 倍数除 5 余 3
因为
因此,将此数乘以 倍,得到
即 R(0,3,0) = 63
类似的 R(0,0,2) 为找一个 3, 5 倍数除 7 余 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 ) 的计算
2.c 可是用于任意的除数余数
2.d 适用多组除数、余数
在上述 CR3 程式中,只能使用固定三个数。
在此程式,要将其改为对任意除数都能适用的情况。
用 ds, rs 分别存取除数组与余数组
CRL([5,7,9],[1,3,5]))
请比对这算法与 直接搜寻法的执行时间