获取题库不需要订阅专栏,可直接私信我进入CSDN领军人物top1博主的华为OD交流圈观看完整题库、最新面试实况、考试报告等内容以及大佬一对一答疑。
题目描述
有n个人围成一圈,顺序排号为1-n。
从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。
输入描述
输入人数n(n < 1000)
输出描述
输出最后留下的是原来第几号
题目解析
这个问题是一个经典的约瑟夫环问题(Josephus Problem),它描述了一个有n个人围坐一圈,从第一个人开始报数,每次报到m的人就退出圈子,直到最后只剩下一个人的过程。在这个特定问题中,m是3。
为了解决这个问题,我们可以使用循环链表或者数组加模拟的方式。由于每次报到3的人就退出圈子,实际上是一个循环删除的过程,因此使用循环链表会更直观和高效。但在这里,为了简化,我们可以使用数组和标记法来模拟这个过程。
python算法代码
def josephus(n, m):