编程之美4.7蚂蚁爬杆扩展问题附猎人抓狐狸(必胜策略)

2024-03-17 15:38

本文主要是介绍编程之美4.7蚂蚁爬杆扩展问题附猎人抓狐狸(必胜策略),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

    4.7节讲的是一根长27cm的木棍上,在5个点上有5只蚂蚁,蚂蚁在开始的时候朝任意方向出发,只能掉头或者往前走。让任意两只蚂蚁碰头时,它们同时掉头朝反方向走。假设蚂蚁的速度都是一秒一厘米,求蚂蚁都离开木棍的最短时间和最长时间。

    穷举很麻烦,书上的思路非常精巧,即把蚂蚁碰头后掉头走,看做两个蚂蚁相遇后擦肩而过。这样就可以把蚂蚁的运动看做是独立的,是否碰头并不重要。代码也很简单,不过书上的代码有个错误,最短时间和最长时间都是所有蚂蚁走出木棍的最短时间和最长时间的最大值。书上的最短时间求的是最小值,一个小错误。代码细节可参看[1]

    代码和这一题不是本文重点,重点是其后面的扩展问题和其他一些扩展

    问题1、3、4参考了[2]的解题思路~非常巧妙的思路!赞一个。

 

1、第i个蚂蚁,什么时候走出木杆?

    假设每一只蚂蚁都背着一袋粮食,任意两只蚂蚁碰头时交换各自的粮食然后调头。这种情况下,每次有一只蚂蚁离开木杆都表明有一袋粮食离开木杆。离开的这袋粮食花在离开木杆的时间同样也是最后背这袋粮食离开木杆的蚂蚁离开木杆所花的时间。看起来有点绕口,就是说离开木杆的蚂蚁和其最后背在背上的粮食花在离开木杆上的时间是一样的(可以理解么,因为它们的起始时间是一样的,结束时间也是一样的)。那要求第i只蚂蚁离开木杆的时间,只需要找到第i只蚂蚁最后离开时背的那袋粮食的时间就可以了。而粮食是不调头的,一直向前走。只要找到这袋粮食,只需要这袋粮食的距离除以速度就可以了。

    怎么找这袋粮食呢。先确定一个命题:若开始时有M只蚂蚁向右走,N-M只向左走,最终结果肯定是M只蚂蚁从左边走下来,N-M只蚂蚁从右边走下来(每次碰头,不改变向左向右的蚂蚁数量)——代表着,必然是木杆最左边的M只蚂蚁将会从左边走下木杆,右边的N-M只从右边走下(好好想想为什么)。

    这样就好做了,如果i<=M的话,则第i只蚂蚁肯定最终在左边走下木杆,那么只要找到往左行走的第i袋粮食即可,它的最初 距离/速度 即第i只蚂蚁走下木杆的时间;如果i>M,同样道理;时间复杂度是O(n)。

def CalTime(antIndex, l, p, d):leftDown = []rightDown = []for i in range(len(p)):if (d[i] == 0):leftDown.append(p[i]) #Assume speed is 1elif (d[i] == 1):rightDown.append((l-p[i]))leftDownLen = len(leftDown)if (antIndex < leftDownLen):return leftDown[antIndex]else:return rightDown[antIndex-leftDownLen]if __name__ == '__main__':l = 20position  = [1,3,5,13]direction = [1,1,1,0] # 0 is leftres = CalTime(0, l, position, direction)print(res)

2、如果蚂蚁在一个平面上运动,同样也是碰头后原路返回(这样和弹性碰撞不同,不能等同于两个蚂蚁叫唤继续前进),问蚂蚁如何走出平面?

感觉有点问题,如果6只蚂蚁组成三角形形状,就造成死锁了,永远走不出去了,一直在碰撞。求大神解答。

3、蚂蚁一共会碰撞几次?

    理论上,只要求得每个蚂蚁的碰撞次数,然后累加,当然还得剔除重复的,分析比较麻烦。换一种思路,还是把碰头调转方向看成穿过继续前行,则原问题求碰撞次数就变成了求穿过的次数(因为速度不变,原来的每次碰撞都对应于现在的一次穿过)。对应于每只向左走的蚂蚁,它只会穿过那些在它右边并且向右走的蚂蚁。因此,每只蚂蚁的穿过次数等于刚开始时在它前进方向上与它前进相反的蚂蚁个数。总的次数的话,只需要统计一个方向上的所有蚂蚁的穿过次数即可,时间复杂度也是O(n)。

def CalCollideTime(d):accumulatedRight = 0totolCollide = 0for curD in d:if (curD == 1):accumulatedRight += 1else:totolCollide += accumulatedRightreturn totolCollideif __name__ == '__main__':l = 20position  = [1,3,5,13]direction = [1,0,1,0,0] # 0 is leftres = CalCollideTime(direction)print(res)

4、每只蚂蚁的碰撞次数,以及哪只蚂蚁的碰撞次数最多?

    解决这个问题,就解决了问题3的原始问题。由题1我们知道每只蚂蚁最终的走下木杆的方向。假设第i只蚂蚁最终往左掉下,而开始的时候它的左边有r只蚂蚁朝右走,那么它最终要朝左碰撞r次才能把它们全部撞成向左走。如果第i只蚂蚁最开始是朝左走,那么它的最终碰撞次数是2r次,如果是朝右走,那么碰撞次数是2r+1次。同样利用一些计数器,在O(N)内能计算出每只蚂蚁的碰撞次数,并求出最大值。

def CalIthCollideTimes(antIndex, l, p, d):leftDown = []rightDown = []for i in range(len(p)):if (d[i] == 0):leftDown.append(p[i])  # Assume speed is 1elif (d[i] == 1):rightDown.append((l - p[i]))leftDownLen = len(leftDown)if (antIndex < leftDownLen):leftTowardsRight = 0for i in range(antIndex):if (d[i] == 1):leftTowardsRight += 1return leftTowardsRight*2 if d[antIndex] == 0 else leftTowardsRight*2+1else:rightTowardsLeft = 0for i in range(len(p)-1, antIndex,-1):if (d[i] == 0):rightTowardsLeft += 1return rightTowardsLeft*2 if d[antIndex] == 1 else rightTowardsLeft*2+1if __name__ == '__main__':l = 20position = [1, 3, 5, 13,14]direction = [1, 0, 1, 0, 0]  # 0 is leftfor i in range(5):res = CalIthCollideTimes(i, l, position, direction)print(res)

4、鸽子共飞了多少路程?

这个比较简单,不要想鸽子飞来飞去,直接以时间为基准来考虑就行了。c*(s/(a+b))

5、什么时候轮船可找到救生圈

简单的,1个小时

 

还有一些比较复杂的扩展题,看得有点晕,有空再回过来仔细瞧瞧,都是摘自[2]。

6、第k次碰撞发生在哪个时刻?哪个位置?哪两个蚂蚁之间。

7、如果不是一根木杆而是一个铁圈,经过一段时间后所有蚂蚁都会回到原状态么?时间上界是多少?

 

 

References

[1]http://blog.chinaunix.net/uid-20766194-id-1850409.html

[2]http://lam8da.sinaapp.com/?p=11

 

BTW在看这个扩展题[2]的时候,看到博主贴的一个某度的面试题,的确挺有一次,原题+解题思路都摘过来了

皆转自[2]

原题如下:

    山上有五个山洞排成一行,编号从1到5。有个狐狸,它第一天藏在某个山洞中,从第二天开始,每天可以逃到前一天所在山洞相邻的山洞中,但逃到哪一个是随机的(当然如果狐狸当前在1号山洞那么它第二天只能去2号洞了,5号也类似)。有个猎人,他每天只能搜寻一个山洞(因为山洞太复杂了。。。。),如果狐狸当天在他搜寻的山洞中就被逮到了。问猎人是否有必定能抓住狐狸的策略?

 

解题思路:思路的确是非常巧妙,其实就是一个奇偶性的判断。只要猎人知道狐狸是在偶数号洞还是奇数号洞就可以了。比方说,猎人知道狐狸是在偶数号洞里,那猎人只要第一天待2号洞,第二天待3号洞,第三天待4号洞,最晚第三天必然能抓到狐狸,因为猎人和狐狸都在偶数号洞里,那么猎人和狐狸的距离差偶数大小,而猎人每经过一天,和狐狸的距离要么不变,要么减2,所以总会相互!

狐狸在奇数号洞里同样如此,猎人选择从奇数号洞开始待就可以了。

所以关键是猎人如何确定狐狸到底是在奇数号洞还是在偶数号洞里!

方法差不多,猎人从1号洞开始待,一直到第四天待到4号洞,都没抓住狐狸,说明狐狸第四天待在奇数号洞里,那第五天狐狸必然要去偶数号洞里拉...(自己想想为什么)

 

还想不明白的读者就去参看[2]吧...

附上对于n个洞的答案:

不论n多大,最坏情况下只需2n−4天就能逮到狐狸,策略是这样的:

若n为奇数,则从第一天开始搜寻的山洞编号为:2, 3, 4, …, n-1, 2, 3, 4, …, n-1

若n为偶数,则从第一天开始搜寻的山洞编号为:2, 3, 4, …, n-1, n-1, n-2, …, 3, 2

不管哪种情况,只需2n−4步即可逮到狐狸。

 

最后,感谢[2]带来的各种精妙思路~

这篇关于编程之美4.7蚂蚁爬杆扩展问题附猎人抓狐狸(必胜策略)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/819377

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

在JS中的设计模式的单例模式、策略模式、代理模式、原型模式浅讲

1. 单例模式(Singleton Pattern) 确保一个类只有一个实例,并提供一个全局访问点。 示例代码: class Singleton {constructor() {if (Singleton.instance) {return Singleton.instance;}Singleton.instance = this;this.data = [];}addData(value)

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)