程设论道二：筛法在线视频

这节课我们还用一个

小朋友做的游戏

引入了一个挺有意思的方法

叫 这个 筛法

然后我觉得 这个筛法 我讲的时候就觉得

其实大家平时在用的时候，这个筛法

真的很不常用

除了大家中学的时候可能听说过

拿它求个质数，基本上不会再听说用这个筛法干什么别的事了

所以我觉得有必要跟同学再聊一聊为什么要讲这个筛法

但是我觉得就是 筛法虽然是说 我们看上去 从数学上来觉得

好像用的少

但是生活当中这个现象 其实是经常用的到的

对吧 比方说我们拿那个 在建筑的工地上经常那个

看到那种筛沙子的

那就是标准的筛（法）

然后我们以前小时候在家里头，挑米里头的壳子

包括弄那个黄豆

其实也是用大大小小不同的筛子

去筛那个 你想要的 或者你不想要的

所以生活当中其实是一个 非常非常常见的

所以我觉得就是

在这一章里头去介绍它

其实 还是很符合我们的那个教学的理念

希望能够引导大家 从生活当中去获得一些

更抽象的 更通用的知识

这个重要性还是非常重要的

那 有没有想过说

为什么这个

用筛法 比如说 求素数

它就会比你一个一个看，每个是否是素数，这样会快，而且快很多呢？

对 为什么呢

我觉得这个问题 可能还是一个

就是 抓它本质上 可能是 看问题的角度的一个思路

其实大家可以下去 让同学们去画一下那个图

咱们现在有100个数

然后每个数单独去判断素数，它是需要从2判断到10

就是判断到根号n嘛

这相当于是一个 像矩阵一样的东西

就是横的有一个100，纵的有一个10。

那我直接一个一个判呢

是在里面去点，每次判断是在里面点一个点。

这里头最关键的问题啊 就是说

这个 它其实是说

我们原来对每一个 从2到100啊

这每一个元素

在判断这个素数

看起来是一个判断

但其实 它是不是素数

其实是若干个有关联的条件组成的

对吧 比方说 凡是比它小的数，都不可以整除它

然后里头整除的数量最多只能是1个

对吧 那么这样的话就是 好比一个比较大的数

它里头 底下比它小的 其实你每个都要去做那种尝试

所以相当于说 你的这个

为了去判断它是不是素数

你是做了若干个条件的 一种与的 最后得到的结果

对吧 这样的话 其实就相当于你刚才说的

它其实形成了一个

矩阵的这种形式

每一列是一个 代表2到100的元素

而每一行 代表的是一个需要去测的这种条件

然后传统的办法呢 其实就是对每一个元素

它的每一个列 的这里头的所有的条件 都要测一遍.

对 然后点出来的点就很密集。

每隔一个就要点一下 每隔一个就要点一下

或者说就是 每一个元素 它所有的这些条件

其实它都做了一个运算

这就是常规的这种 直接循环 一个个去枚举

反过来到筛法的时候呢

看我们里层那层循环

写的是每次+2 +2

每次+2呢 那就是中间跳过了一些元素

或者说 中间有些元素没有做那些运算。

都空掉了。

如果+2的时候 大家可能体会不是很明显

到+3 +5 到+7 的时候

你刚才说的很对

你看你现在说的时候是

+2 +3 +5 +7

实际上就等同于原来 本来是说

我要从2 判断到10

是一个一个去判断

现在变成了说

我先把2这一个条件

给它全看一遍

然后再来看3

然后再来看4

然后每次一看的时候呢，是把这一个条件

去把 所有的数

都给它查了一遍

这是一个很重大的变化

所以 就像你最开始说的

其实是观察问题的角度

本来是按照列 往下看的

现在变成了按行

对吧 我一个条件一个条件去看

正是因为它有这样一个转换

我们发现在按行去看的时候

其实循环更方便

从这个新的角度看这个问题 诶

它变了以后 可能将变简单了

有同样的性质 处理起来 对于筛法来讲

同样的性质 处理起来就快

就是你原来没有办法去加快的

现在由于你横着看之后

你就有办法加快了

因为你是做2的

好比说 我们还是以求素数为例子的话

你是横着看的话 相当于说 这个数

能不能被2整除

对不对 那这个时候

你+1就没有必要了

就不要每个数循环一下

但是你 之所以说 我能够跳着去看

是因为你现在就在看这一个条件

所以你不是横着去

用这一个条件去看的时候

是无法去 所谓的 +2 或者 跳着走的

带来的它是一种可能性

但是你仍然还是可以去+1 去加了。

只不过说是

你可以跳着做之后 就可以把那种

重复劳动给去掉

所以我觉得这节课给大家将筛法的意义

不是说 这个筛法有多么普适，多么常用

更重要的是 筛法体现出了一种

你从一个方向考虑问题的时候可能很难

如果换一个角度考虑问题，就有可能把这个问题简化

有更好的方法去解决

这个思路其实在以后很多的这个解决问题的过程当中会经常用到。

这么说 可能学生理解呢

会感觉比较抽象点 但是我觉得

我们也可以说一些 比较

更具有操作性的指导意见

当你去用筛法的时候

或者你试图去用筛法去做尝试的时候

首先你要考虑

是不是能够用到数组

如果没有数组的话，筛法肯定是没法去实现的

也就是说

筛东西要有筛子

数组就是筛子

假如说这个题目 你可以看到说

数组没有用武之地

那恐怕就不是我们去考虑 用筛法的时候了

对吧 这是一个

那反过来也是一样

如果我们觉得它

可以同筛法

那么呢 一定要让

它在数组上去得到一个体现

借助数组这个工具

去完成这个筛的过程

这是第一个特点

要通过若干个筛子

我们要定义若干个筛子

之所以我们说筛法好

从某一种形式的角度去看以后

我们定的那个筛子啊，就能充分利用

它的这个特点

-- 然后加快我们
-- 层层过滤

数据处理的速度

所以这里归结起来 第二个条件就是说

你的真的具备多个筛子

然后它的条件就很简单

你怎么找第二个筛子出来

所以你只能是

肯定是 很复杂的条件 相对复杂的条件

而且这个筛子它必然是内部有一定相似性

单独判断每一个小的数的时候

然后要符合一群的条件

然后我们把这一群的条件

单独拿出来去筛一群的数

一个转换的过程

所以这个 我觉得课后

咱们刚才说了 筛法用处就是不太多

那我觉得 课后如果有兴趣的同学

数学比较好的同学

可以去试一下

用筛法可以去求那个

咱们叫 欧拉函数

那个 fai 的那个值

可以去试一下 筛法应该是同样适用的

我觉得筛法跟我们生活中间的 比如说

流水线 它有一定的这种关系

就比如说你一个人要做一个零件的话

可能会有好几个工序

那一个人在那 先做第一道 再做第二道

半天做完一个零件

但是我们实际上 我们工厂很多时候并不是这么做的

我们找几个人 每人负责一道工序

每个人只要做同样一道工序

他就能处理一批零件

这样会发现说 效率会是提高的

也是说明什么 就是

我可能换一个角度 组织方式的话呢

它是有可能能把这个效率提高的

其实筛法正好也是说 我们求素数的时候

有很多道工序

然后你现在就把一道工序整理成一个

我不用一个一个去除，我可能就一个内部循环

可能用+2 这种很简单 统一工具 哗 一批批的做

最后发现 诶 效率提高了

而且是很多 其实在数学上相当于一种与的关系

就是你都得做 对吧

可是呢

尽管你都得做

你可以分批去做

而你分批去做呢 你可以

某一个工序 或者某一个任务

可以先对你所要做的这个数据

全部处理完了

再来处理下一个条件

所以就像你（说的）那个组装一样

对不对 100个零件

诶不 100个产品要组装

那你这个工人 是第一道工序

你负责装第一个

其实每一个都是要装的

对不对 但是呢我不让你把每个都装完

你一直装第一个

对吧 流水作业

它就是快

那改卷子啊 做零件啊

也是 很典型对不对 经常在使用

其实有时候这个思想我们有时候操作比如计算机

对 文件操作 其实有时候也用得到

好比说我这目录里头有

几百个文件

我让你把某种特殊后缀的

比方说 obj后缀 exe后缀

是吧 要把它删掉

同时呢又要求你说

一定是 什么时间之前的

我不想要

对吧 那怎么办啊

你如果是按照文件名排序

你一个一个去考虑 对吧

啊 是不是这个 是不是这个 特别麻烦

那我可以分开来做啊

反正这两个 与 的条件的嘛

我可以先按照后缀名

我把它很快的排个序

因为这是计算机系统天然提供的

对吧 就想说你那个for循环里头

+2 +3 很easy

对不对 那就很快嘛

我这个也是一样 我一点

后缀名它肯定就集中在一起了

一下子 批处理 一选择它

拿鼠标一划拉就选了

然后删掉它

然后再按时间排个序

之前的一选 又删掉它

三下五除二把它搞完了

所以我觉得 我们学这课 还是最开始那个理念

一方面要去生活当中去感受到

里头有 算法的 思想在里面蕴含这

同时在学完我们这个课程呢

在我们的引导之下

又要善于把这个 理论的这种升华的部分

运用到 你的生活当中去

去看到更多的

我们讲到的这种知识

没准我们今天举了两例子之后

回头一看

扯出第三个来

所以我也欢迎他们在

讨论区里头列出来

看看谁列的多，我们回头可以给点奖励

回头布置一下助教让他干这个事儿