五.队列的应用案例-烫手的山芋

╰+哭是因爲堅強的太久メ 2023-02-17 14:52 44阅读 0赞

原文链接：https://www.cnblogs.com/bobo-zhang/p/10525106.html

#  #

[ 5.队列的应用案例-烫手的山芋 ][5._-_]

</h1>
            <div class="clear"></div>
            <div class="postBody">

烫手山芋游戏介绍：6个孩子围城一个圈，排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋，需要在计时器计时1秒后将山芋传递给下一个孩子，依次类推。规则是，在计时器每计时7秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后剩下的孩子获胜。请使用队列实现该游戏策略，排在第几个位置最终会获胜。

- 这个游戏相当于著名的约瑟夫问题，一个一世纪著名历史学家弗拉维奥·约瑟夫斯的传奇故事。故事讲的是，他和他的 39 个战友被罗马军队包围在洞中。他们决定宁愿死，也不成为罗马人的奴隶。他们围成一个圈，其中一人被指定为第一个人，顺时针报数到第七人，就将他杀死。约瑟夫斯是一个成功的数学家，他立即想出了应该坐到哪才能成为最后一人。

分析：为了模拟这个圈，我们可以使用队列。假设游戏开始时，排在队列中的第一个（队首）的孩子手里拿着山芋。游戏开始后，拿着山芋的孩子出队列然后再入队列，将山芋传递给下一个孩子。每当山芋到队首孩子手里后，队首的孩子先出队列再入队列，一次类推。当传递六次后，手里有山芋的孩子淘汰，游戏继续，继续传递山芋。

![复制代码][Image 1]

from basic.queue import Queue

def hotPotato(namelist, num):  
simqueue = Queue()  
for name in namelist:  
simqueue.enqueue(name)

</span><span style="color: #0000ff;">while</span> simqueue.size() > 1<span style="color: #000000;">:
        </span><span style="color: #0000ff;">for</span> i <span style="color: #0000ff;">in</span><span style="color: #000000;"> range(num):
            kid </span>=<span style="color: #000000;"> simqueue.dequeue()
            simqueue.enqueue(kid)
    
        simqueue.dequeue()
    
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> simqueue.dequeue()

print(hotPotato(\[“Bill”,“David”,“Susan”,“Jane”,“Kent”,“Brad”\],7))

![复制代码][Image 1]

分类: [数据结构+算法][Link 1]

好文要顶 关注我 收藏该文 ![icon_weibo_24.png][] ![wechat.png][]

[![20190729093950.png][]][20190729093950.png 1]

[波晓张][20190729093950.png 1]  
[关注 - 2][- 2]  
[粉丝 - 542][- 542]

\+加关注

<div class="clear"></div>
    <div id="post_next_prev">
    
    <a href="https://www.cnblogs.com/bobo-zhang/p/10524517.html" class="p_n_p_prefix">« </a> 上一篇：    <a href="https://www.cnblogs.com/bobo-zhang/p/10524517.html" title="发布于 2019-03-13 17:19">4.基本数据结构-队列</a>
    <br>
    <a href="https://www.cnblogs.com/bobo-zhang/p/10525482.html" class="p_n_p_prefix">» </a> 下一篇：    <a href="https://www.cnblogs.com/bobo-zhang/p/10525482.html" title="发布于 2019-03-13 19:14">6.基本数据结构-双端队列（Deque）</a>

posted @ 2019-03-13 18:43  [波晓张][Link 2]  阅读( 372)  评论( 0)  [编辑][Link 3]  收藏

</div>

刷新评论 刷新页面 返回顶部

注册用户登录后才能发表评论，请 登录 或 注册， [访问][Link 4] 网站首页。

[【推荐】了解你才能更懂你，博客园首发问卷调查，助力社区新升级][Link 5]  
[【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库][50_VC_ _CAD_GIS]  
[【推荐】前转转首席架构师的“架构玄学”][Link 6]

[5._-_]: https://www.cnblogs.com/bobo-zhang/p/10525106.html
[Image 1]: 
[Link 1]: https://www.cnblogs.com/bobo-zhang/category/1417180.html
[icon_weibo_24.png]: https://common.cnblogs.com/images/icon_weibo_24.png
[wechat.png]: https://common.cnblogs.com/images/wechat.png
[20190729093950.png]: https://pic.cnblogs.com/face/1489694/20190729093950.png
[20190729093950.png 1]: https://home.cnblogs.com/u/bobo-zhang/
[- 2]: https://home.cnblogs.com/u/bobo-zhang/followees/
[- 542]: https://home.cnblogs.com/u/bobo-zhang/followers/
[Link 2]: https://www.cnblogs.com/bobo-zhang/
[Link 3]: https://i.cnblogs.com/EditPosts.aspx?postid=10525106
[Link 4]: https://www.cnblogs.com/
[Link 5]: https://www.wenjuan.com/s/3uIjeq0/
[50_VC_ _CAD_GIS]: http://www.ucancode.com/index.htm
[Link 6]: https://developer.aliyun.com/live/2668?utm_content=g_1000133217