算法设计教学与哲学思维(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。