韩信点兵算法原理

韩信点兵，多多益善我国汉代有位大将,名叫韩信.他每次集合部队,只要求部下先后按l～3、1～5、1～7报数,然后再报告一下各队每次报数的余数,他就知道到了多少人。

1、他的这种巧妙算法,人们称为鬼谷算,也叫隔墙算,或称为韩信点兵,外国人还称它为“中国剩余定理”。

2、到了明代,数学家程大位用诗歌概括了这一算法韩信点兵韩信点兵又称为中国剩余定理,相传汉高祖刘邦问大将军韩信统御兵士多少。

3、韩信答说,每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人…….刘邦茫然而不知其数。

4、我们先考虑下列的问题：假设兵不满一万,则兵有多少?首先我们先求5、9、13、17之最小公倍数9945。

扩展知识——韩信

1、韩信（？-前196年），淮阴（今江苏淮安市淮阴区）人，西汉开国功臣、军事家，汉初三杰之一，中国军事思想“谋战”派代表人物，明朝茅坤赞其为“兵仙”。

2、韩信出身平民，早年家庭贫困，曾寄人篱下，受过胯下之辱。秦末农民起义爆发后，韩信先投靠项梁，后投靠刘邦，均不被重用。

3、刘邦入汉中时，韩信曾逃走，被萧何连夜追回，并推荐给刘邦。刘邦于是拜韩信为大将，与项羽争夺天下。汉元年（前206年），韩信献策平定三秦。

4、楚汉之争中，韩信以其杰出的军事才能横扫魏、赵、代、燕、齐诸国，并数次以兵支援刘邦。蒲坂之战韩信声东击西拿下魏国都城安邑；井陉之战韩信背水一战大破赵军；潍水之战韩信水淹齐楚联军，斩杀楚将龙且。

5、垓下之战韩信布五军阵诱敌，击破项羽军。高祖五年（前202年），楚霸王项羽走投无路自刎于乌江。韩信因功徙封楚王。

6、高祖六年（前201年），刘邦开始剪除异姓王。韩信被贬为淮阴侯。汉高祖十一年（前196年），因被人告发参与陈豨谋反，韩信被吕后与萧何合谋杀死于长乐宫，并被诛三族。

7、韩信是秦汉之际第一流的军事家。不仅指挥过许多重大的取得辉煌战绩的军事行动，而且具有深厚的兵学素养，留下了兵学著作《韩信》三篇。

8、是《汉书·艺文志》记载的“兵权谋十三家”之一，与孙武、孙膑、商鞅、吴起等兵家并列。不仅如此，韩信还与张良一起，对流传至西汉初年的兵书进行整理。

韩信点兵是一个有趣的中国数学问题，它可以用现代数学语言描述如下：
若士兵人数是x，则有x除以3余2，x除以5余4，x除以7余6。我们也可以用同余式来表示这个问题：x ≡ 2 (mod 3)，x ≡ 4 (mod 5)，x ≡ 6 (mod 7)。
我们发现，若将x加上1，则可以同时被3、5、7整除，即x+1 ≡ 0 (mod 3)，x+1 ≡ 0 (mod 5)，x+1 ≡ 0 (mod 7)。因此，x+1一定是3、5、7的最小公倍数的整数倍，由于3、5、7两两互素，则x+1 ≡ k * lcm(3,5,7) (mod 3)，x+1 ≡ k * lcm(3,5,7) (mod 5)，x+1 ≡ k * lcm(3,5,7) (mod 7)。
其中k是某个正整数，lcm(3,5,7)表示3、5、7的最小公倍数。通过解同余方程，我们可以求得k的值，从而得到x的值。
这就是韩信点兵算法的原理。