（C++）“韩信点兵”问题的求解方法

一时失言乱红尘 2023-02-26 05:28 21阅读 0赞

有一队士兵，确切人数不知，但若每３人一组，则余２人；

每５人一组，余３人；每７人一组，余５人；每１１人一组，余４人。

请解答下列问题：

⑴至少有多少人？

⑵若已知人数在5000～10000之间，问有多少个答案？

解：初学者容易想到用逐个试探的方法来求解，

这样显然很耗时间，特别是在所求解的值非常大时。

求解方法是：逐个满足条件，在寻找满足下一个条件的解时保证前面条件继续成立。

如何做到这一点？

可以这样实现：探索满足下一个条件的ｎ的值时，

以累加前面各数的最小公倍数来试探。

由此得到求解的程序段。

#include <iostream>
    using namespace std;
     
    int main(int argc, char** argv) {
    	int n = 2;
    	// 满足 3人一组余2
    	while(n%5!=3) n+=3;
    	// 在保证 3人一组余2的前提下寻找满足5人一组余3的n值
    	while(n%7!=5) n+=15;
    	//在满足前两个条件的前提下寻找满足7人一组余5的n值
    	while(n%11!=4) n+=105;
    	//在满足前三个条件的前提下寻找满足11人一组余4的n值
    	//(1)至此得到第一个满足条件的人数488  
    	//下面第二小题范围   逐个输出
    	while(n<5000){
    		n+=1155;
    	} 
    	cout<<"所有满足要求的数量如下："<<endl; 
    	//达到范围要求5000~10000
    	while(n<10000){
    		cout<<n<<endl;
    		n+=1155;
    	} 	
    }

> 所有满足要求的数量如下：  
> 5108  
> 6263  
> 7418  
> 8573  
> 9728
> 
> \--------------------------------  
> Process exited after 0.1292 seconds with return value 0

另外可以用中国剩余定理求解：

中国剩余定理详解： [https://zhuanlan.zhihu.com/p/152226583][https_zhuanlan.zhihu.com_p_152226583]

[https_zhuanlan.zhihu.com_p_152226583]: https://zhuanlan.zhihu.com/p/152226583

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关实验4-1-5 韩信点兵 (10 分)

实验4-1-5 韩信点兵 (10 分) 在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝建立了卓越的功劳。据说韩

太过爱你忘了你带给我的痛/ 2023年10月03日 11:31/ 0 赞/ 17 阅读

相关韩信点兵，在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝建立了卓越的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了知道有多少兵，

7 韩信点兵在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝建立了卓越的功劳。据说韩信的数学水平也非常高超，他在

àì夳堔傛蜴生んèń/ 2023年07月13日 03:06/ 0 赞/ 10 阅读

相关（C++）“韩信点兵”问题的求解方法

有一队士兵，确切人数不知，但若每３人一组，则余２人；每５人一组，余３人；每７人一组，余５人；每１１人一组，余４人。请解答下列问题： ⑴至少有多少人？ ⑵若已知人数在

一时失言乱红尘/ 2023年02月26日 05:28/ 0 赞/ 22 阅读

相关韩信点兵

输入包括多组数据，每组数据包括三个非负整数a,b,c,表示每种队形排尾的人数，输出总人数的最小值(或报告无解）。已知总人数在10到100之间。样例输入： 2 1 6

朱雀/ 2023年02月11日 11:23/ 0 赞/ 98 阅读

相关韩信点兵(穷举法)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

浅浅的花香味﹌/ 2022年11月13日 12:22/ 0 赞/ 204 阅读

相关韩信拜将：委派模式

大家好，我是老田，从今天开始，本公众号每周给大家`送福利`，送什么呢？肯定是技术书啦，没那么多花里胡哨的，参与方式见文末。好啦，进入我们的主题，今天我给大家分享设计模

比眉伴天荒/ 2022年10月18日 04:52/ 0 赞/ 177 阅读

相关题目34 韩信点兵

![20160728121050764][] 已AC代码： include<cstdio> using namespace std; in

深藏阁楼爱情的钟/ 2022年09月24日 09:23/ 0 赞/ 158 阅读

相关平面最近点对问题求解

平面最近点对问题求解问题描述： > 最近点对问题是指求解平面点集n个点中距离最近的两个点间的问题。为简单起见，在二维坐标平面来考虑该问题。如果说讨论的点以标准二维坐标

朴灿烈づ我的快乐病毒、/ 2022年07月20日 12:24/ 0 赞/ 228 阅读

相关算法题-韩信点兵

/请教别人写的代码,这是最简单的写法/ include<stdio.h> int main(void){ int i,a,b,c;

r囧r小猫/ 2022年06月18日 08:20/ 0 赞/ 160 阅读

相关 acm 韩信点兵

韩信点兵时间限制：3000 ms | 内存限制：65535 KB 难度：1 输入输入3个非负整数a,b,c ，表示每种队形排尾的人数（a<3,b<5,c<7

痛定思痛。/ 2022年05月18日 02:24/ 0 赞/ 175 阅读