算法案例 01：韩信点兵算法求解#

本报告针对经典“韩信点兵”同余方程组问题进行计算思维建模与 C++ 算法求解。

---

一、 题目描述#

韩信带 1500 名士兵打仗，战死四五百人（剩余人数在 1000 ~ 1100 之间）。剩余士兵：

• 3 人一排，多出 2 人；
• 5 人一排，多出 4 人；
• 7 人一排，多出 6 人。

设计算法精确计算剩余士兵数。

---

二、 解题思路与同余数学模型#

设剩余士兵数为 $N$。由题意可得同余方程组：

N \equiv 2 \pmod 3 \\ N \equiv 4 \pmod 5 \\ N \equiv 6 \pmod 7 \end{cases}$$ 观察可知：$N + 1$ 同时能被 $3$、$5$、$7$ 整除。因此： $$N + 1 = k \times \text{lcm}(3, 5, 7) = k \times 105$$ $$N = 105k - 1$$ 已知剩余人数在 $1000 \le N \le 1100$ 范围内： * 当 $k = 10$ 时，$N = 1050 - 1 = 1049$。 --- ## 三、 C++ 算法实现与测试 ```cpp #include <iostream> using namespace std; int main() { int min_soldiers = 1000; int max_soldiers = 1100; int result = -1; for (int n = min_soldiers; n <= max_soldiers; n++) { if (n % 3 == 2 && n % 5 == 4 && n % 7 == 6) { result = n; break; } } if (result != -1) { cout << "剩余士兵数为: " << result << " 人" << endl; } else { cout << "未找到符合条件的士兵数！" << endl; } return 0; } ``` --- ## 四、 求解结果 运行程序得到唯一精确解：剩余士兵数为 **`1049`** 人。