约瑟夫环问题幸运的基督徒问题
本帖最后由 a147888123 于 2022-5-18 11:18 编辑"""
有15个基督徒和15个非基督徒在海上遇险，为了能让一部分人活下来不得不将其中15个人扔到海里面去，
有个人想了个办法就是大家围成一个圈，由某个人开始从1报数，报到9的人就扔到海里面，
他后面的人接着从1开始报数，报到9的人继续扔到海里面，直到扔掉15个人。
由于上帝的保佑，15个基督徒都幸免于难，问这些人最开始是怎么站的，哪些位置是基督徒哪些位置是非基督徒。
在gitee下载了一些源码，看到有这么一道题目，刚开始没有思路，今天在上班路上想出一个思路也不知道对不对
# 初始的时候我也不知道谁是基督徒，谁不是，那么就把他们全部设定为1，等到扔完15个人后剩下全是基督徒，说明需要一个循环，循环到被杀15人停止，剩下15人，那15人都是基督徒
# 被扔后，他们的数值变为0，不影响扔人的记数，继续放哪里占位，等到扔完15人到海里面，如果使用删除数组的方式要去算原来的位置太麻烦，被杀的人用0替代，不影响记数，也不影响最初的数组位置
请大佬看看对不对
"""
有15个基督徒和15个非基督徒在海上遇险，为了能让一部分人活下来不得不将其中15个人扔到海里面去，
有个人想了个办法就是大家围成一个圈，由某个人开始从1报数，报到9的人就扔到海里面，
他后面的人接着从1开始报数，报到9的人继续扔到海里面，直到扔掉15个人。
由于上帝的保佑，15个基督徒都幸免于难，问这些人最开始是怎么站的，哪些位置是基督徒哪些位置是非基督徒。
思路是对的，有点小错误，又修改了下
"""
有15个基督徒和15个非基督徒在海上遇险，为了能让一部分人活下来不得不将其中15个人扔到海里面去，
有个人想了个办法就是大家围成一个圈，由某个人开始从1报数，报到9的人就扔到海里面，
他后面的人接着从1开始报数，报到9的人继续扔到海里面，直到扔掉15个人。
由于上帝的保佑，15个基督徒都幸免于难，问这些人最开始是怎么站的，哪些位置是基督徒哪些位置是非基督徒。
"""
list1 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# 初始的时候我也不知道谁是基督徒，谁不是，那么就把他们全部设定为1，等到扔完15个人后剩下全是基督徒，
# 被扔后，他们的数值变为0，不影响扔人的记数，继续放哪里占位，等到扔完15人到海里面
print(len(list1))
kill = 0
temp = 0
while kill <= 15:
for i in range(0, len(list1)):
temp = temp+list1
#print("i值", i, "和值", temp)
if temp == 9:# 表示报到9的那个人的值变为0，表示被扔到海里面
print("i值", i, "记数值", temp)
list1 = 0
print(list1)
kill = kill+1
print(kill)
temp = 0
if kill == 15:
break
print(list1)
有个思路分享给你们，我们使用队列的方法来解决约瑟夫环问题，采用队列来存放所有参加游戏的基督徒number，这里是30个人，按照传递的方向从 队首排到队尾（1，2.......30），程序开始，循环遍历1-9，当报数到指定数q的人到队首（即q=9），这时，我们只需要将队首的人出队，若不到9，则将他们先从队头出队再从队尾入队，直至剩余人数num=15人时跳出循环，这时队内的元素都是存活下来的基督徒。
上面的代码有小错误，我再改
list1 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# 初始的时候我也不知道谁是基督徒，谁不是，那么就把他们全部设定为1，等到扔完15个人后剩下全是基督徒，
# 被扔后，他们的数值变为0，不影响扔人的记数，继续放哪里占位，等到扔完15人到海里面
print(len(list1))
kill = 0
temp = 0
while kill < 15:
for i in range(0, len(list1)):
temp = temp+list1
#print("i值", i, "和值", temp)
if temp == 9:# 表示报到9的那个人的值变为0，表示被扔到海里面
#print("i值", i, "记数值", temp)
list1 = 0
print(list1)
kill = kill+1
# print(kill)
temp = 0
if kill == 15:
break
print(list1) 先赞一个，以后看。 思路没有问题。
n=30的约瑟夫环问题，直接打表输出会更快。
leetcode 有约瑟夫环相关题目，n可达1e5, 欢迎前去挑战。 shenben 发表于 2022-5-18 11:54
思路没有问题。
n=30的约瑟夫环问题，直接打表输出会更快。
leetcode 有约瑟夫环相关题目，n可达1e5, 欢 ...
请简单代码学习下，我太菜了只有这个办法，数学功底太差，这个代码上午还是不断报错 https://s1.ax1x.com/2022/05/18/OTEhN9.png
学习了。。 chaojiak47 发表于 2022-5-18 16:06
学习了。。
我从易学python你倒好，又从python转易 易比python方便 要认真地学习一下 这个思路很nice，Mark一下
页:
[1]
2