这是我参加“14天阅读挑战赛”第二周第3篇
前面发布的学习笔记《Py递归解“约瑟夫”的一种变形问题》，其实也是可以用for来实现的。
代码
def j(n):
'''用for循环解“约瑟夫环”一种变形问题。\n 约瑟夫环的一种变形。我们考虑的问题是开始时有n个人，记为1到n，站成一个圆圈。每一步，每第2个人将被去除，直到只剩下一个人为止。我们把剩下的人记为J(n)，用程序求出1≤n≤16的J(n)。'''
persons = list(range(1, n+1))
k = [0] # 确定第一个被删除人的位置。
while len(set(persons)) > 2:
# print(persons) #调试用语句。
for i in range(len(persons)):
if len(set(persons)) == 2:
break
if k[0] != 0 and persons[i] != 0:
#print(persons[i], end=', ')
persons[i] = 0
k[0] = 0
else:
k[0] = 1
persons = list(set(persons))
if 0 in persons:
persons.remove(0)
# input(persons) # 调试用语句。
return persons[0]
运行代码输出：
/sdcard/qpython $ python 1234.py
用for循环解“约瑟夫环”一种变形问题。
约瑟夫环的一种变形。我们考虑的问题是开始时有n 个人，记为1到n，站成一个圆圈。每一步，每第2个人将 被去除，直到只剩下一个人为止。我们把剩下的人记为J(n)，用程序求出1≤n≤16的J(n)。去除人位置顺序：
当队列为 1人时，约瑟夫环最后剩下的是第 1人。去除人位置顺序：
当队列为 2人时，约瑟夫环最后剩下的是第 1人。去除人位置顺序：
当队列为 3人时，约瑟夫环最后剩下的是第 3人。去除人位置顺序：
当队列为 4人时，约瑟夫环最后剩下的是第 1人。去除人位置顺序：
当队列为 5人时，约瑟夫环最后剩下的是第 5人。去除人位置顺序：
当队列为 6人时，约瑟夫环最后剩下的是第 1人。去除人位置顺序：
当队列为 7人时，约瑟夫环最后剩下的是第 7人。去除人位置顺序：
当队列为 8人时，约瑟夫环最后剩下的是第 1人。去除人位置顺序：
当队列为 9人时，约瑟夫环最后剩下的是第 9人。去除人位置顺序：
当队列为10人时，约瑟夫环最后剩下的是第 1人。去除人位置顺序：
当队列为11人时，约瑟夫环最后剩下的是第11人。去除人位置顺序：
当队列为12人时，约瑟夫环最后剩下的是第 1人。去除人位置顺序：
当队列为13人时，约瑟夫环最后剩下的是第13人。去除人位置顺序：
当队列为14人时，约瑟夫环最后剩下的是第 1人。去除人位置顺序：
当队列为15人时，约瑟夫环最后剩下的是第15人。去除人位置顺序：
当队列为16人时，约瑟夫环最后剩下的是第 1人。循环用时0.001482秒。~~~~~~~~~~~~~~ 2022-10-27 18:14:56 ~~~~~~~~~~~~~~~
Josephus(约瑟夫斯)的故事(点此跳转“约瑟夫环”百科词条)
据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而Josephus和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。
问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
代码
def josephus_story(n=41, k=1, m=3):
''' Josephus的故事：\n 据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。\n 然而Josephus和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。\n 问题是，Josephus and his friend，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。'''
persons = list(range(1, n+1))
def eliminate(k, m):
''' 从第k人开始，步长为m淘汰人。'''
if len(persons) == 2:
return
k += m -1
while len(persons) < k:
k -= len(persons)
print(persons.pop(k-1), end=', ')
eliminate(k, m)
eliminate(k, m)
return persons
代码运行效果截屏图片
数字家Gapas(加帕斯)讲的故事(点此跳转“约瑟夫环”百科词条)
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：
30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
递归代码
def gapas_story(n=30, k=1, m=9):
'''数学家Gapas(加帕斯)讲的故事：\n 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：\n 30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。'''
persons = list(range(1, n+1)) # 用1~n的数组表示30人的队列。
def resursive_work(k, m):
''' 递归算法工作函数。'''
if len(persons) == 15: # 终止递归。
return
k += m-1 # 非教徒位置计算。
while k > len(persons):
k -= len(persons) # while 循环处理大于列表长度的情况。
print(persons.pop(k-1), end=', ') # k 位置的人在列表中下标为 k-1 。
resursive_work(k, m) # 递归调用。
resursive_work(k, m) # 调用函数开始递推。
return(', '.join(map(str, persons))) # 返回教徒应处位置。
代码运行效果截屏图片
循环代码
def gapas_story(n=30, k=1, m=9):
'''数学家Gapas(加帕斯)讲的故事：\n 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：\n 30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。'''
persons = list(range(1, n+1)) # 用1~n的数组表示30人的队列位置。
while len(persons) > 15:
k += m-1 # 定位非教徒。
while k > len(persons):
k -= len(persons) # while 处理 k 大于列表长度。
print(persons.pop(k-1), end=', ') # 推非教徒下水。
return ', '.join(map(str, persons)) # 返回教徒应处位置列表。
代码运行效果截屏图片
标准“约瑟夫环”问题(点此跳转百科词条)
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 结果+1即为原问题的解。
代码
def standard_joseph(n, k, m):
''' 标准约瑟夫环：\n  约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 结果+1即为原问题的解。 '''
persons = list(range(1, n+1)) # 列表1~n代表人的初始站队位置。
k += m-1 # 第一个淘汰的人的位置。
def resursive_cook(k, m):
''' 递归工作函数 '''
if persons == []: # 人全部淘汰，
return
if k <= len(persons):
print(persons.pop(k-1), end=', ')
k += m-1 # 下一个被淘汰的人位置。
else:
while k > (width := len(persons)):
k -= width
resursive_cook(k, m) # 递归调用。
resursive_cook(k, m)
运行效果截图
