问题描述
有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。
解决方案
问题分析
(1)如何完成从最后一个人到第一个人的报数。
(2)如何删去报三的人。
解决问题
第一种---切片法
(1)利用切片可以很好的解决最后一个人到第一个人的报数。
list1 = list1[2:] + list1[:2]
(2)可以使用list.remove(x)删除列表中的x元素。
list1.remove(list1[2])
(3)解决代码:
n = int(input("输入n的值:"))
list1 = list(range(1, n + 1))
while True:
if len(list1) <= 2:
break
#print(list1[2])#查看每一次删除报3的人的编号
list1.remove(list1[2])
list1 = list1[2:] + list1[:2]
#print(list1)#查看每一次删除报3的人之后的列表
print(list1[1])
运行实例
第二种---约瑟夫环法
(1)也可以使用约瑟夫环法的思想解决最后一个人到第一个人的报数。
k = 2
while True:
if len(list1) == 1:
break
list1.pop(k)
k += 2
k %= len(list1)
(2)可以使用list.pop(k)删除列表中索引为k的元素。
list1.pop(k)
注:list.remove(x)是删除列表中第一个x元素。
List.pip(k)是删除列表中索引为k的元素
(3)解决代码:
n = int(input("输入n的值:"))
list1 = list(range(1, n + 1))
k = 2
while True:
if len(list1) == 1:
break
#print("删除的人编号为", list1[k])#查看每一次删除报3的人的编号
list1.pop(k)
#print(list1)#查看每一次删除报3的人之后的列表
k += 2
k %= len(list1)
print(list1[0])
运行实例
结语
本题的关键点就是如何正确的完成最后一个人到第一个人的报数衔接。约瑟夫环算法与切片法相比空间复杂度更低。
实习编辑:欧洋
责编 :十七
能力越强,责任越大。
实事求是,严谨细致。
(where2go团队)
微信号:算法与编程之美
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。