黑白翻片:一次翻一片的步数
用不同色片数量的变化判断达到目标所需最少操作。
视频暂时无法加载。请检查网络后重试,或直接下载视频。
下载视频
展开视频文字稿
- 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片不同白片即可。