用计算机编程解决问题

问题：韩信点兵

秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。

提出问题：韩信怎么很快就知道士兵的人数，用什么方法计算，结果可信吗？

 “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

实例是一个数学问题：《初步数论》解同余式。

数学原型：

一个数除以3余2，除以5余3，除以7余2，求这个数。这样的问题，也有人称为“韩信点兵”.它形成了一类问题，也就是初等数论中的解同余式。

一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数。 　　

分析问题

解：

先列出除以3余2的数：2， 5， 8， 11， 14， 17， 20， 23， 26…x≡2(mod 3)　　

再列出除以5余3的数：3， 8， 13， 18， 23， 28… x≡3 (mod 5)

这两列数中，首先出现的公共数是8。3与5的最小公倍数是15。

两个条件合并成一个就是8 mod 15整数，列出这一串数是8， 23， 38，…，

再列出除以7余2的数 2， 9， 16， 23， 30… x≡2 (mod 7)

事实上，我们已把题目中三个条件合并成一个：被105除余23。23 (mod 105)

x={x|x≡2mod3,x≡3mod5,x≡2mod7}

x≡23 mod 105

被105除余23。

那么韩信点的兵在1000-1100之间，应该是105×10+23=1073人。

算法设计：

算法一：枚举法

算法说明：

枚举从1到1500的整数

对每个整数进行判断，是否符合以下条件：

1.整数对3求余，余数为2；

2.整数对5求余，余数为3；

3.整数对7求余，余数为2。

符合条件的整数输出来。