当前课程知识点:组合数学 >  容斥原理和鸽巢原理 >  看得见摸得着的鸽巢 >  韩信点兵

返回《组合数学》慕课在线视频课程列表

韩信点兵在线视频

韩信点兵

下一节:中国剩余定理

返回《组合数学》慕课在线视频列表

韩信点兵课程教案、知识点、字幕

我给大家来讲一个历史上典故

大家都知道韩信吧

韩信实际上有一个典故非常有名

也就是韩信点兵

他的故事是这样的

当初楚汉相争

有一次韩信带着兵

正走在一个狭窄的道路上

这时候楚军追来

情况非常危机

当时韩信并不知道自己有多少将士

而且地方非常狭窄

追兵在后

没有时间来整理队伍

看一共有多少人了

这时候韩信出了一个

非常奇妙的方法

他说将士们你们不要慌张

你们3人一排

看余多少人

然后再5人一排余多少人

然后7人一排余多少人

最后3人一排余2人

5人一排余3人

而7人一排最后余2人

当时他的副官就报告

说韩将军我们的人数一共是1052人

韩信当时摇头说不对

你数错了

我们的军事一共是1073名

敌人一看不足500

而我们超过了1000人

而且我们居高临下

一定能够打败敌人

这时候将士们士气大涨

于是直接击破了楚军

这个故事大家觉得很奇怪

怎么就排了一下队伍

算了一下余多少人

韩信就能够知道

他一共有多少个将士吗

其实同样的问题我们在孙子算经中

也有类似的一道题目

孙子算经中有这样一段话

他说 今有物不知其数

三三数之余二

五五数之余三

而七七数之余二

问物几何

翻译起来什么意思啊

他说我有这么一个数字

它除以3以后余2

除以5余数是3

除以7余数是2

请问这个数字是多少

这实际上就是在求初等数论中的

同余式

我们把它可能用方程写x等于

3a加2

x等于5b加3

x等于7c加2

韩信就是非常迅速地

可以计算出来x等于多少

就马上得出他一共有多少士兵

而孙子算经也是怎么去

求解这样一个同余式呢

我们可以从简单的问题开始

就看孙子算经的问题

我们先用枚举的方法来做

比如说他不是要求除以3余2吗

我把所有的除以3余2的数

列在这里

同时我也可以列出

所有除以5余3的列在这里

最后我可以把除以7余2的数字

全部列在这里

最后我们发现

确实它们中间存在一些共同的数字

而最小的共同数字恰好是23

但是我想韩信肯定不能靠这种方法

来得到答案吧

我们是不是有

另外一个更巧妙的方法呢

比如说我们可不可以用构造的方法

来找到这样一个数字呢

我们会发现其实在这里面

我们有一些是可以考虑5的倍数

7的倍数

再加上某一些余数

那这里比如说我可以设5和7的

公倍数是S

那么5和7的公倍数要除3余1

能有多少个数字呢

5和7的公倍数除3余1的数字

恰好是70

那么意味着这样一个数字

我如果乘以2的话

它就必然能被5和7整除

但是除以3余2

它就满足了第一个式子

而对应于对应于第二个5b加3

和7c加2

它对余数没有贡献

那我们就可以依次按照这样的思想

比如说用t来表示是3和7的公倍数

但是它除以5余1

这个数字恰巧如果t乘以3等于63

它的标志着它是3和7的倍数

但是它如果它除以5余3

它就恰好满足第二个式子

接着我还可以算

h是3和5的倍数

但是它却除7余1

这时候h乘以2算出来是30

这个数字恰好是3和5的倍数

但是它去除7满足第三个式子

也就是7c加2

那这时候我想构造一个对于除3余2

除5余3

除7余2的式子

我直接可以用2s加上3t加上2h

它恰好等于233

由于我们的设计能够保证

对应于除以3的时候

它的余数是出现在第一个部分

除以5的时候

它的余数出现在3t部分

而除以7的时候

它的余数出现在2h部分

它必然就会满足右边的这个同余式

而当然233是满足的一个数字

如果我们想要求最小的一个呢

因为3 5 7的公倍数恰好是105

那么我可以用233不停地减105

最后我得到了一个比较小的数字

也就是和刚才枚举出来的

结果是一样的

233减去105

再减去105

恰巧等于23

这时候我再回答孙子算经的问题

今有物不知其数

三三数之余二

五五数之余三

七七数之剩二

问物几何

答曰23

这时候回头再看韩信怎么做呢

韩信实际上确实记住了这些公倍数

然后利用简单的乘法

它就可以直接找到

相应的规模的答案

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(1)

--采访武永卫老师

-第一周作业

--作业说明

--H

--U

--G

--作业讨论区说明

-第一周演示程序

--程序讨论区说明

--幻方生成器

--换方计数

--屏幕解锁方案数

--欧拉路计数

--共享程序

小乒乓球的组合之旅

-加减乘除来计数

--计数的基本法则

-排列还是组合

--排列还是组合

--小乒乓球的组合之旅--排列还是组合

--格路模型与组合恒等式

-各种各样的排列

--圆排列和项链排列

--圆排列和项链排列--习题

--多重排列

--多重排列--练习

-多样的组合

--可重组合

--不相邻组合

--小乒乓球的组合之旅--多样的组合

-钟声里的全排列

--钟声里的全排列

--钟声里的全排列

--字典序法

--SJT算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

韩信点兵笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。