抽象覆蓋點:最少覆蓋全部門

邏輯思維 · 建議年級 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個。

立即試一題

四個門排一列,同樣規則最少幾個標記?