黑白翻片:一次翻一片的步數
用不同色片數量的變化判斷達到目標所需最少操作。
影片暫時無法載入。請檢查網絡後重試,或直接下載影片。
下載影片
展開影片文字稿
- 6片开始全部白色,每次只能翻一片,目标是恰好4片黑。我们要找最少次数。
- 一次操作最多把一片白变黑,所以从0片黑增加到4片黑,至少需要4次。
- 这个“至少”还不是完整答案,还要展示4次真的能做到。
- 依次翻4片不同的白片,它们各变黑,另外2片保持白色,正好得到4黑2白。
- 3次最多只接触三片并新增3黑,不可能达到4黑;4次方案已经达到。
- 所以下界与构造相遇,最少是4次。重复翻同一片只会浪费步数。
邏輯思維
變化下界與構造
看一個例子
6片開始全白,每次翻一片。要得到恰好4片黑,最少翻幾次?
一次操作最多把一片白變黑,所以從0片黑增加到4片黑,至少需要4次。這個“至少”還不是完整答案,還要展示4次真的能做到。依次翻4片不同的白片,它們各變黑,另外2片保持白色,正好得到4黑2白。3次最多隻接觸三片並新增3黑,不可能達到4黑;4次方案已經達到。
立即試一題
每次最多新增1黑,翻3片不同白片即可。