相传韩信才智过人,从不直接清点自己军队的人数,只要让士兵先后以三人一排、五人一排、七人一排地变换队形,而他每次只掠一眼队伍的排尾就知道总人数了。输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7),输出总人数的最小值(或报告无解)。已知总人数不小于10,不超过100 。
输入输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7)。
输出输出总人数的最小值(或报告无解,即输出No answer)。实例,输出:89
样例输入:
2 1 6
样例输出:
41
样例输入:
2 1 3
样例输出:
No Answer
方法一:枚举法(不讲)
方法二:古人法
我国古代学者早就研究过这个问题.例如我国明朝数学家程大位在他著的《算法统宗》(1593年)中就用四句很通俗的口诀暗示了此题的解法:
三人同行七十稀,
五树梅花甘一枝,
七子团圆正半月,
除百零五便得知.
“正半月”暗指15.”除百零五”的原意是,当所得的数比105大时,就105、105地往下减,使之小于105;这相当于用105去除,求出余数.
如何有3 5 7 推断出70 21 15,105这四位数字
为了求出是5与7的倍数而用3除余1的数,我们看看5与7的最小公倍数是否合乎要求.5与7的最小公倍数是5×7=35,35除以3余2,35的2倍除以3余2,35的2倍除以3就能余1了,于是我们得到了”三人同行七十稀”.
为了求出是3与7的倍数而用5除余1的数,我们看看3与7的最小公倍数是否合乎要求.3与7的最小公倍数是3×7=21,21除以5恰好余1,于是我们得到了”五树梅花甘一枝”.
为了求出是3与5的倍数而用7除余1的数,我们看看3与5的最小公倍数是否合乎要求.3与5的最小公倍数是3×5=15,15除以7恰好余1,因而我们得到了”七子团圆正半月”.
3、5、7的最小公倍数是105,所以”除百零五便得知”.
意思是:70取余3得1
21取余5得1
15取余7得1
用2 1 6做例子
2*70 + 1*21 + 6*15= 251
105*2 + 41 = 251
70*2取余3得2
21*1取余得1
15*6取余得6
那么不难发现这相当于用105去除,求出余数.,然后余数41大于10小于100,符合要求。
因此2 1 3求出来余数是101不符合要求,故没答案
代码如下:
此方法可以应用到其他数字例如4,5,6求出三者中的两个数字的公倍数除以另外一个数字取余得1,然后求出三位数字的最小公倍数。