韩信点兵计算公式与代码
韩信点兵计算公式与代码
问题描述：
淮安民间传说着⼀则故事——“韩信点兵”，其次有成语“韩信点兵，多多益善”。
韩信带1500名兵⼠打仗，战死四五百⼈，站3⼈⼀排，多出2⼈；站5⼈⼀排，多出4⼈；站7⼈⼀排，多出6⼈。韩信很快说出⼈数：1049。
问题重述：
上述问题使⽤数学语⾔其实可以描述如下：
假设⼀个数为X，则1000<X<1100（战死四五百），并且X满⾜以下等式：
X%3 = 2
X%5 = 4
X%7 = 6
让求X。
问题解法：
其实韩信点兵问题，在古代已经有了解法。《孙⼦算经》有⼏句乘法⼝诀：三⼈同⾏七⼗稀， 五树梅花廿⼀枝， 七⼦团圆正半⽉， 除百零五便得知。
这句话的意思就是⽤被除数是3的余数（2）与70相乘，被除数是5的余数（4）与21相乘，被除数是7的余数（6）与15相乘，最后如果没在范围之内，就加减若⼲次105就可以得到答案。
所以算法是这样的：2*70+4*21+6*15=314⼈
314+105+105+105+105+105+105+105=1049⼈。
现代⼈们解决这个问题⽤的是中国剩余定理。定理内容可以上⽹看到，这⾥不再多说，直接上公式。
上⾯算式的70，其实就是先让两个被除数相乘，⽐如被除数5*7=35，然后检查(35*1)除以剩余的那个被除数3是否余1，如果余1，则记下倍数为1；如果不为1，在检查(35*2)除以3是否余1，如果余1，则记下倍数为2，否则接着增加倍数继续判断。
因此，5*7=35，判断(35*1)%3 == 2 != 1，故判断(35*2)%3 ==1，记下倍数为2，35*2=70。
以此类推，
3*7=21，判断(21*1)%5==1，记下倍数为1，21*1=21。
3*5=15，判断(15*1)%7==1，记下倍数为1，15*1=15。
然后乘上另⼀项的余数再相加：
70*2+21*4+15*6=314。
最后再求出三个被除数的公倍数：3*5*7=105，通过加若⼲次105，使结果满⾜范围。
公式如下：
将题⽬抽象出来：X在(n,m)之间，并且X满⾜以下等式：
X%a = i
X%b = j
X%c = k
让求X。
第⼀步：
先求三个倍数x1,x2,x3，初始值三个数都为1，求出满⾜以下等式的x1,x2,x3。
(b*c*x1) % a == 1
(a*b*x2) % c == 1
(a*c*x3) % b == 1
第⼆步：
计算三个等式s1,s2,s3
s1 = (b*c*x1) * i
s2 = (a*b*x2) * k
s3 = (a*c*x3) * j
第三步：
求出三个被除数的公倍数s4
s4 = a*b*c
第四步：
计算s = s1+s2+s3
第五步：
根据X所在的范围(n,m)，通过将s加减若⼲次s4，使s满⾜n<=s<=m。则最终结果s即为所得。韩信点兵python代码如下：
print('------------------------韩信点兵------------------------')
print("请输⼊第⼀组被除数与余数（⽤空格隔开）：")
a,i =map(int,input().split())
print("请输⼊第⼆组被除数与余数（⽤空格隔开）：")
b,j =map(int,input().split())
print("请输⼊第三组被除数与余数（⽤空格隔开）：")
c,k =map(int,input().split())
print("请输⼊该数的范围：")
n,m =map(int,input().split())
x1=x2=x3 =1#表⽰倍数
s4 = a*b*c #三个被除数的公倍数
s1=s2=s3 =1#每项的结果
t1=t2=t3 =False#⽤于判断余数是否为1
while True:#计算出每⼀项中的倍数x1,x2,x3
t1 =(b*c*x1)% a ==1
t2 =(a*b*x2)% c ==1
t3 =(a*c*x3)% b ==1
if(not t1):
x1+=1
if(not t2):
x2+=1
if(not t3):
x3+=1
if(t1 and t2 and t3):
break
s1 =(b*c*x1)* i #第⼀项的结果
s2 =(a*b*x2)* k #第⼆项的结果
s3 =(a*c*x3)* j #第三项的结果
# print(s1,s2,s3,s4)
s = s1+s2+s3 #s为计算的最终结果
print("该数为：",end=' ')
while True:#判断该数是否在(n,m)范围⾥，如果不再通过加减若⼲次的公倍数，使其处于范围⾥
if(s>n and s<m):
print(s)
break
elif(s<n):
s=s+s4 #如果⼩于下界，则加上公倍数，直到不⼩于韩信点兵多多益善
elif(s>m):
s=s-s4 #如果⼤于上界，则减去公倍数，直到不⼤于
elif(s==n or s==m):
print(s)
break
发布评论