韩信点兵公式及其Java代码
韩信点兵公式及其Java代码
问题描述：
淮安民间传说着⼀则故事——“韩信点兵”，其次有成语“韩信点兵，多多益善”。
韩信带1500名兵⼠打仗，战死四五百⼈，站3⼈⼀排，多出2⼈；站5⼈⼀排，多出4⼈；站7⼈⼀排，多出6⼈。韩信很快说出⼈数：1049。
问题重述：
上述问题使⽤数学语⾔其实可以描述如下：
假设⼀个数为X，则1000<X<1100（战死四五百），并且X满⾜以下等式：
X%3 = 2
X%5 = 4
X%7 = 6
让求X。
问题解法：
可见博客
公式如下：
将题⽬抽象出来：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即为所得。
例⼦：
⼀个数在200与400之间，它被3除余2，被7除余3，被8除余5，求该数。
将题⽬抽象出来：X在(200,400)之间，并且X满⾜以下等式：
X%3 = 2
X%7 = 3
X%8 = 5
让求X。
代⼊上述公式可得X=269。
韩信点兵Java代码如下：
import java.util.Scanner;
public class HanXinDianBing {
public static void main(String[] args){
Scanner sc =new Scanner(System.in);
System.out.println("------------------------韩信点兵------------------------");//输⼊已知数据
System.out.println("请输⼊第⼀组被除数与余数（⽤空格隔开）：");
int a = sc.nextInt();
int i = sc.nextInt();
System.out.println("请输⼊第⼆组被除数与余数（⽤空格隔开）：");
int b = sc.nextInt();
int j = sc.nextInt();
System.out.println("请输⼊第三组被除数与余数（⽤空格隔开）：");
int c = sc.nextInt();
int k = sc.nextInt();
System.out.println("请输⼊该数的范围：");
int n = sc.nextInt();
int m = sc.nextInt();
int x1=1,x2=1,x3=1;//表⽰倍数
int s4 = a*b*c;//三个被除数的公倍数
int s1=1,s2=1,s3=1;//每项的结果
boolean t1=false,t2=false,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(!t1)
x1+=1;
if(!t2)
x2+=1;
if(!t3)
x3+=1;
if(t1 && t2 && t3)
break;
}
s1 =(b*c*x1)* i;//第⼀项的结果
s2 =(a*b*x2)* k;//第⼆项的结果
s3 =(a*c*x3)* j;//第三项的结果
int s = s1+s2+s3;//s为计算的最终结果
System.out.printf("该数为：");
while(true){//判断该数是否在(n,m)范围⾥，如果不再通过加减若⼲次的公倍数，使其处于范围⾥if(s>n && s<m){
System.out.print(s);
break;
}
else if(s<n)
s=s+s4;//如果⼩于下界，则加上公倍数，直到不⼩于
else if(s>m)
s=s-s4;//如果⼤于上界，则减去公倍数，直到不⼤于
else if(s==n || s==m){
System.out.print(s);
break;
}
}
}
}
运⾏结果：
------------------------韩信点兵------------------------请输⼊第⼀组被除数与余数（⽤空格隔开）：32
请输⼊第⼆组被除数与余数（⽤空格隔开）：73
请输⼊第三组被除数与余数（⽤空格隔开）：85
请输⼊该数的范围：
200400
该数为：269