Python |
您所在的位置:网站首页 › 约瑟夫环Python代码if › Python |
欢迎点击「算法与编程之美」↑关注我们! 本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。 问题描述 问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈。(模拟此过程,输出出圈的人的序号) 解决方案 这道题涉及到的算法叫做“约瑟夫算法”,我们需要将列表内所有人类似排列成一个“圈”来解决,需要将前一次删除后剩下的元素的索引不变,但是位置向前提。无限循环这个“圈”,直到删除到只剩一个。 这道题的关键在于如何将每个数的索引数字固定,在删除前一个数字后,后面的数字都应该在排序中加一。所以我们一开始需要创建一个列表,从1开始到含有位数的数字,代表每个数字的索引列表。 代码示例: def Josephus_problem(num,gap): location_list = [a for a in range(1,num+1)] if num == 1 : return else: index = 0 for i in range(num-1): index = (index + gap )%len(location_list) - 1 print("本次出局的人为:",location_list[index]) del location_list[index] if index == 0: index = 0 print( "最后剩下的为:",location_list[0])
Josephus_problem(5,3) 结语 这道题的解决方法有很多种,这里主要介绍一下这种算法。还有重点为推导出(index + gap )%len(location_list)这个公式。 END 实习编辑 | 王楠岚 责 编 | 李和龙 where2go 团队
微信号:算法与编程之美 长按识别二维码关注我们! 温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发! |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |