抽象覆盖点:最少覆盖全部门

逻辑思维 · 建议年级 4

在明定的相邻覆盖模型中给出覆盖五个门点的最少放置方案。

下载视频
展开视频文字稿
  1. 这是抽象覆盖模型,不代表真实摄像头视野。1到5号门排成一列,一个标记只覆盖自己和紧邻门。
  2. 一个标记最多覆盖连续3个门,所以单个标记不可能覆盖5个门,至少需要2个。
  3. 把一个标记放2号,它覆盖1、2、3号。
  4. 另一个放4号,它覆盖3、4、5号。两个范围合起来覆盖全部五门。
  5. 下界说至少2个,构造又用2个做到,所以最少正好是2个。
  6. 现在改成1到4号门,规则不变。请圈出最少标记及各自覆盖范围,小宝贝到你了。
讲解依据

逻辑思维

下界与构造

看一个例子

在本题抽象模型中,1到5号门排成一列;一个标记放在某门,只覆盖该门和紧邻门。最少放几个标记能覆盖全部门?

一个标记最多覆盖连续3个门,所以单个标记不可能覆盖5个门,至少需要2个。把一个标记放2号,它覆盖1、2、3号。另一个放4号,它覆盖3、4、5号。两个范围合起来覆盖全部五门。下界说至少2个,构造又用2个做到,所以最少正好是2个。

马上试一题

四个门排一列,同样规则最少几个标记?