转 韩信点兵 及其算法.doc

【韩信点兵及其算法】 韩信点兵是中国古代流传下来的一个典故，与数学算法密切相关，被西方称为“中国剩余定理”。该算法源于一个经典的数学问题，旨在找到一个正整数，它除以特定的几个数后，余数符合特定条件。在这个故事中，韩信利用这种算法在战场上快速准确地估算出自己军队的人数，从而制定战略。 1. **历史故事** - 版本一讲述了韩信如何通过3人、5人、7人一列的点兵方式，推算出军队实际人数为1073人，以此鼓舞士气击败敌人。 - 版本二则通过刘邦与韩信的对话，展示了韩信对这种算法的运用，准确计算出一队士兵为23人的能力。 2. **韩信点兵的计算方法** - 这种算法最早出现在《孙子算经》中的一道题目：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？” - 解决这类问题的通用方法是找到一系列满足特定余数条件的数，然后进行加减操作。 - 例如，对于刘邦的题目，可以找到能被5和7整除但被3除余1的数70，被3和7整除但被5除余1的数21，以及被3和5整除但被7除余1的数15。 - 接着，将这些数按照题目给出的余数条件进行组合，如140（70×2）、63（21×3）和30（15×2），然后将这些数相加得到233。 - 因为63和30都能被3整除，所以233被3除的余数为2，同理，233被5和7除的余数分别为3和2，满足题目条件。 - 考虑到3、5、7的最小公倍数是105，任何加上或减去105的整数倍都不会改变233对这三个数的余数，因此233是符合条件的解。而题目限制数不超过100，所以实际答案是23（233-105×2）。 3. **秦九韶的《大衍求一术》** - 秦九韶在《数书九章》中提出的“大衍求一术”是解决一次同余式组问题的系统方法，是对《孙子算经》中算法的进一步发展和理论化，为这类问题提供了一套完整的计算程序。 韩信点兵的算法不仅体现了古代中国数学的智慧，而且在现代数学中仍具有重要的理论价值。这种算法可以应用于密码学、编码理论、计算机科学等多个领域，其基本思想和方法至今仍被广泛使用。通过理解和掌握这种算法，我们可以更好地理解中国古代数学的精妙，并从中汲取智慧来解决现代问题。