好贷网好贷款

【韩信点兵 算法总结】

发布时间:2016-12-4 10:04:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【韩信点兵 算法总结】",主要涉及到【韩信点兵 算法总结】方面的内容,对于【韩信点兵 算法总结】感兴趣的同学可以参考一下。

题目描述 相传韩信才智过人,从不直接清点自己军队的人数,只要让士兵先后以三人一排、五人一排、七人一排地变换队形,而他每次只掠一眼队伍的排尾就知道总人数了。输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7),输出总人数的最小值(或报告无解)。已知总人数不小于10,不超过100 。 输入格式 第一行输入整数n(n<10),代表测试数据组数。 其后n行,每行输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7)。例如,输入:2 4 5 输出 输出总人数的最小值(或报告无解,即输出No answer)。实例,输出:89 样例输入 2 2 1 6 3 6 8 样例输出 41 No Answer #include<iostream> using namespace std; int main(){ int n; cin>>n; while(n--){ int a,b,c; cin>>a>>b>>c; if(a>=3 || b>=5 || c>=7 ){ cout<<"No Answer"<<endl; } else{ int sum=a*70+b*21+c*15; cout<<sum%105<<endl; } } } 例如,假如3粒一数余1粒,5粒一数余2粒,7粒一数余2粒,那么,原有蚕豆有多少粒呢? 这类题目看起来是很难计算的,可是我国古时候却流传着一种算法,名称也很多,宋朝周密叫它“鬼谷算”,又名“隔墙算”;杨辉叫它“剪管术”;而比较通行的名称是“韩信点兵”。最初记述这类算法的是一本名叫《孙子算经》的书,后来在宋朝经过数学家秦九韶的推广,又发现了一种算法,叫做“大衍求一术”。这在数学史上是极有名的问题,外国人一般把它称为“中国剩余定理”。至于它的算法,在《孙子算经》上就已经有了说明,而且后来还流传着这么一道歌诀: 三人同行七十稀, 五树梅花廿一枝, 七子团圆正半月, 除百零五便得知。 这就是韩信点兵的计算方法,它的意思是:凡是用3个一数剩下的余数,将它用70去乘(因为70是5与7的倍数,而又是以3去除余1的数);5个一数剩下的余数,将它用21去乘(因为21是3与7的倍数,又是以5去除余1的数);7个一数剩下的余数,将它用15去乘(因为15是3与5的倍数,又是以7去除余1的数),将这些数加起来,若超过105,就减掉105,如果剩下来的数目还是比105大,就再减去105,直到得数比105小为止。这样,所得的数就是原来的数了。根据这个道理,你可以很容易地把前面的五个题目列成算式: 1×70+2×21+2×15-105 =142-105 =37 因此,你可以知道,原来这一堆蚕豆有37粒。  

上一篇:shell常用判断语句
下一篇:MINA2.0用户手册中文版--第二章 第五节 UDP客户端实例

相关文章

相关评论