100个python算法超详细讲解：约瑟夫环

admin管理员组

文章数量:1794759

100个python算法超详细讲解：约瑟夫环

完整版下载

超详细python算法案例讲解100例.zip-Python文档类资源-CSDN下载

 1．问题描述 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲到一个故事： 15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的 人才能幸免于难。于是想了一个办法，将30个人围成一个圆圈，从第一个 人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅 剩15个人为止。问怎样的排法才能使每次投入大海的都是非教徒？ 2．问题分析 本题明显是一个约瑟夫问题。约瑟夫问题的求解方法很多，这里仅给 出一种实现方法。 问题描述中说“将30个人围成一个圆圈”，据此可以考虑使用一个循环 的链来表示。 3．算法设计 我们使用一个二维数组array[flag][next]来存放30个人，其中flag用来表 示是否被扔下海的标记。为1表示没有被扔下海，为0表示已被扔下海。next 表示指向下一个人的数组下标。 程序从第一人开始对还未扔下海的人进行计数，每数到9时，就将数组 中的标记改为0，表示该人已经被扔下海了，如此循环计数直到有15个人被 扔下海为止。 4．确定程序框架 1）定义二维数组。定义一个二维数组用来存放30个人，代码如下：

array = [[0] * 2 for i in range(31)] # 30个人，0号元素没有使用

上面的代码定义了二维数组array，该数组有31个元素，数组中的0号元 素未使用，1～30号元素分别表示题中所述的30个人。 2）初始化二维数组。二维数组的初始化代码如下：

for i in range(1, 31): # 初始化结构数组 array[i][0] = 1 # flag标志置为1，表示人在船上 array[i][1] = i + 1 # next的值为数组中下一个元素的下标，即指向下一个人 array[30][1] = 1 # 第30个人的数组下标指向第一个人以构成环

 上面的代码使用for循环完成对二维数组的初始化工作。初始情况下， 由于30个人都在船上，因此数组中每个元素的flag成员的值都置为1，next成 员的值设置为数组中下一个元素的下标，即指向下一个人。需要注意的 是，array数组中第30个元素的next成员值需要重新指定为1，用于指向第一 个人以构成环。 3）计数15次，每到第九个人就将其扔入大海。实现核心功能的代码如 下：

j = 30 # 变量j指向已经处理完毕的数组元素，从array[i]指向的人开始计数 for i in range(15): # 循环变量i作为计数器，记录已扔下海的人数，共15个人 k = 0 while True: # 循环变量k作为计数器，决定哪个人被扔下海，计数到9为止 if k < 9: j = array[j][1] # 修改数组下标，取下一个人 k += array[j][0] # 进行计数，已扔下海的人标记为0 else: break # 计数到9则停止计数 array[j][0] = 0 # 将标记置0，表示该人已被扔下海

上面的程序中循环变量i作为计数器，用于记录已扔下海的人数。循环 变量k作为计数器，用于找到每次被扔下海的那个人，计数到9为止。每次 循环找到被扔下海的那个人后就将其flag标记置0。 程序流程图如图12.1所示。 5．完整的程序 根据上面的分析，编写程序如下：

#!/usr/bin/python3 # -*- coding: utf-8 -*- # @author : liuhefei # @desc: 约瑟夫环 if __name__ == '__main__': array = [[0] * 2 for i in range(31)] # 30个人，0号元素没有使用 print('最终结果为(s:被扔下海,b:在船上):') for i in range(1, 31): # 初始化结构数组 array[i][0] = 1 # flag标志置为1，表示人在船上 array[i][1] = i + 1 # next的值为数组中下一个元素的下标，即指向下一个人 array[30][1] = 1 # 第30个人的数组下标指向第一个人以构成环 j = 30 # 变量j指向已经处理完毕的数组元素，从array[i]指向的人开始计数 for i in range(15): # 循环变量i作为计数器，记录已扔下海的人数，共15个人 k = 0 while True: # 循环变量k作为计数器，决定哪个人被扔下海，计数到9为止 if k < 9: j = array[j][1] # 修改数组下标，取下一个人 k += array[j][0] # 进行计数，已扔下海的人标记为0 else: break # 计数到9则停止计数 array[j][0] = 0 # 将标记置0，表示该人已被扔下海 for i in range(1, 31): # 输出结果 if array[i][0]: print('b', end='') else: print('s', end='') print()

6．运行结果 在PyCharm下运行程序，结果如图12.2所示。其中，s表示数组中该位 置代表的人将会被扔进海里，b表示数组中该位置代表的人会待在船上。

 

 7．拓展训练 思考题：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3 报数），凡是报到3的人就退出圈子，问最后留下的人是原来的第几号。

本文标签： 约瑟夫算法详细Python