韩信点兵算法

Qusetion

相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。输入3个非负整数a,b,c ，表示每种队形排尾的人数（a<3,b<5,c<7），输出总人数的最小值（或报告无解）。已知总人数不小于10，不超过100 。

Idea1

简单粗暴，枚举法，从i = 10开始，到 i =100为止，每一个数进行判断，同时满足取余3等于a，取余5等于b，取余7等于c的时候就输出，否则，没有结果

code1

#include<iostream>
using namespace std;
int main() {
    int a, b, c;
    int i = 10;
    cout << "请输入abc三个数的值" << endl;
    cin >> a >> b >> c;
    while(i < 100) {
        if (i % 3 == a && i % 5 == b && i % 7 == c) {
            cout << "人数为" << i << endl;
            return 0;
        } else i++;
    }
    cout << "没有结果" << endl;
    return 0;
}
​
using namespace std;
int main() {
    int a, b, c;
    int i = 10;
    cout << "请输入abc三个数的值" << endl;
    cin >> a >> b >> c;
    while(i < 100) {
        if (i % 3 == a && i % 5 == b && i % 7 == c) {
            cout << "人数为" << i << endl;
            return 0;
        } else i++;
    }
    cout << "没有结果" << endl;
    return 0;
}
​

idel2

思考了下，发现如果数一旦大了，不是一百，那就很容易导致用时过长，所以就在想其它方法。百度了下，发现了个算法，网上有些讲解很粗糙，我就按我自己的理解整理了下，简化步骤如下

三个数，每两个数找公倍数，满足取余第三个数为1，此时即时满足我要求的

①能被5,7除尽数是35k,其中k=2，即70除3正好余1，70a 除3正好余a。

②能被3,7除尽数是21k,其中k=1，即21除5正好余1，21b 除5正好余b。

③能被3,5除尽数是15k,其中k=1，即15除7正好余1，15c 除7正好余c。

根据①可知 70a+21b+15c 除3正好余a。

根据②可知 70a+21b+15c 除5正好余b。

根据③可知 70a+21b+15c 除7正好余c。 （70a+21b+15c）%（3 * 5 * 7）为最小值，然后再判断最小值是否满足条件。

 

code2

#include<iostream>
using namespace std;
int main() {
    int a, b, c;
    cout << "请输入三个数" << endl;
    cin >> a >> b >> c;
    int res = (70 * a + 21 * b + 15 * c) % (3 * 5 * 7);
    if (res < 100 && res >10) {
        cout << "人数为" << res << endl;
        return 0;
    } else {
        cout << "没有结果" << endl;
        return 0;
    }
}
​
using namespace std;
int main() {
    int a, b, c;
    cout << "请输入三个数" << endl;
    cin >> a >> b >> c;
    int res = (70 * a + 21 * b + 15 * c) % (3 * 5 * 7);
    if (res < 100 && res >10) {
        cout << "人数为" << res << endl;
        return 0;
    } else {
        cout << "没有结果" << endl;
        return 0;
    }
}
​