算法设计教学与哲学思维（20210330）

本科教学过程中，一直在尝试面向数据、信息、知识与智慧的融合教学改革。

一些小例：

(a) 最大公约数的辗转相除与相减等方式：本质上是对于A>B两部分的最大公约数的搜索不需要在任何A中与B完全相同的m个划分中进行重复搜索。从而将可以将A中去除m个B区域，直到(A-mB)<B，再递归的应用这一原理进行求解。

(b) 百元买百鸡或者鸡兔同笼问题：其优化的极限在于对来自问题描述的问题求解的限制的严格使用。消除不必要的操作是根本。而不必要的操作往往是主观引入的。例如公鸡的数量<=20与母鸡数量<=33单独是对的，但放在一起时就不合适了，这不合适来源于把两个独立假设放在一起了，互相都不成立。而本质上问题描述里面是没有孤立的假设的，把这些变量联合起来才符合对两者之间的关联的对应。

(c) KMP方法：在串B上寻找串A，KMP的效率来源于本质上，查找串A的状态其实面对的就是两个集合{A的部分匹配串，其它的情形}。也就是说B的任何变形对于这个查找A来看都等效对应于{A的部分匹配串，其它的情形}的组合。转喻，在B上的搜寻其实就是在重复搜寻A的片段。把这个搜寻的重复部分的计算节省下来就是KMP。

转载本文请联系原作者获取授权，同时请注明本文来自段玉聪科学网博客。

链接地址：https://wap.sciencenet.cn/blog-3429562-1279277.html?mobile=1

收藏

分享