书生本色分享 http://blog.sciencenet.cn/u/analytic 举头望明月,低头看剖面

博文

一个找田鼠的算法问题

已有 3899 次阅读 2017-3-7 11:16 |系统分类:科普集锦

昨晚导师群里有学弟发了一个找田鼠的问题:田里有并排六个田鼠洞,田鼠每天晚上都从洞里跳到相邻的洞里。农夫每天早上只能检查一个田鼠洞。问农夫最多需要多少天能抓到田鼠,并给出方法。


我按下图的计算路线是八天,箭头代表下一天可能跳进的洞。第六天若排除4号洞知道在2号洞,则第七天只能1或3,第七天检查3号,第八天直接在2号洞抓老鼠。但是目前我还没有抽象出一个数学模型,感觉可能是一个图论的模型。设洞的编号为1-6,天数为n,则田鼠的状态可表示为Xn,且abs(Xn+1-Xn)=1,1<=Xn<=6,那么是否可以认为,是要设计一个Yn,使得n取某个值时,Xn=Yn?或者说,若以横轴为天数,轴为洞号,则为两条曲线何时相交问题?






https://blog.sciencenet.cn/blog-1032764-1038013.html

上一篇:终于把虚拟机下的linux和c++编译器装好了
下一篇:考上了,新规划
收藏 IP: 123.151.38.*| 热度|

1 张云

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-4-26 16:22

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部