困在洞穴的兔子技能攻略

当农夫从n-1号到2号洞穴扫描时,由于他在n-1处连续待了两天,其所在洞穴编号的奇偶性不再与绿毛兔子一致,反而与红毛兔子一致,因此此时可将农夫看成一只红毛兔子。所有红毛兔子都在农夫左边,同上分析,可得:当农夫扫描到2号洞穴时,所有红毛兔子都会被逮住。

无论什么时候,所有红毛兔子所在洞穴编号奇偶性一致,所有绿毛兔子所在洞穴编号奇偶性一致,且与红毛兔子的奇偶性相反;无论什么时候,每个洞穴要么没有兔子,要么全是红毛兔子,要么全是绿毛兔子,不可能出现红毛兔子和绿毛兔子混在一个洞穴中的情况;不可能存在两只红毛兔子相邻,也不可能存在两只绿毛兔子相邻;每个红毛兔子想要越过其左边(或右边)的红毛兔子,必定会在某一洞穴内相遇;每个绿毛兔子想要越过其左边(或右边)的绿毛兔子,必定会在某一洞穴内相遇

有n个水平并排相邻的洞穴,从左到右依次编号1,2,...,n。某个洞穴中有一只兔子,该兔子每天晚上都会跳到相邻的洞穴中,有个农夫每天晚上会去一个洞穴逮兔子,请问该农夫至少要花多少天(或查看多少次洞穴)才能一定逮住该兔子?

由于开始兔子的位置未知,原问题等价于:刚开始每个洞穴中有且仅有一只兔子,它们彼此互不干扰对方活动,洞穴足够大,可以容纳无穷只兔子,请问该农夫至少要花多少天(或查看多少次洞穴)才能逮住所有兔子?(若一个洞穴中有多只兔子,该农夫一次逮住该洞穴内的所有兔子)

当农夫从2号到n-1号洞穴扫描时,由于其行为是在兔子的行为(每次只能向相邻位置跑,在同一位置不能连续待两天)基础上,加上约束:只能向右跑,所以此时可以将农夫看成一只绿毛兔子,即农夫在向右扫描的过程中,要么遇到的洞穴为空,要么会逮住绿毛兔子;刚开始,所有绿毛兔子都在农夫右边,它们想要越过农夫,必定会在某个洞穴内相遇,即被逮住,所以当农夫扫描到第n-1个洞穴时,所有绿毛兔子都被逮住了。

      打开APP搜你想看,本站所刊载图文之著作权归快看漫画官方和快看漫画用户所有,内含官方内容和快看社区用户编辑内容,非经本站授权许可,禁止转载。