0 引言
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:15个教徒和15 个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。
1 问题描述
有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。
示例一:
输入:n = 3
输出:“2”
解释:首先轮流报数,3就被退出了,之后1,2,1,1就被退出了,最后只剩下了2。
2 算法描述
解题思路:首先因为考虑到是不断的有规律退出数字则首先要考虑到循环的使用,我们从索引上看,如果将每次循环的三人看成一组,则被退出的人的索引为2,此时我们就知道了我们删去的就应该是索引为2的人。但我们此时又想到该如何让其满足我们想得到的方式呢?我们不妨将其横排排列,123删去3后变成1212,此时我们发现可以将之前还未删去的数值排列在其之后,我们可以多举几个例子如1234变成12412。那么此时我们就解决了第一个如何将其围成圈的问题,而之后就到了最关键的时候了,如何删去这些值?我们又举123为例,若想得到1,我们可以有很多的做法,而取余则是一种很巧的运算方式,如:“1”的位置是1,所以0%3(3是这三个值的长度(1,2,3))得到0,而1 的索引就是0,同理我们可得其他的值。根据规律可得,若k=2的值为删去的数,那么我们只需进行k = k+2得到下一个删去的值。(简单讲就是本事索引除以长度得到自身位置,本身长度加1除以长度得到下一个位置,同理加2)
3 实验结果与讨论
通过编程最终求出了约瑟夫环的问题。
附件
代码清单 用python求出杨辉三角数
n = int(input()) | list1 = list(range(1, n + 1)) | k = 2 | while True: | if len(list1) == 1: | break | list1.pop(k) | k += 2 | k %= len(list1) | print(list1[0]) |