.约瑟夫环 【题目描述】 约瑟夫问题（有时也称为约瑟夫斯置换

）是一个经典的问题，源自于一个古老的故事。故事讲的是，约瑟夫和他的朋友们被罗马军队包围在一个洞穴里。他们决定宁愿死也不被俘虏，于是商量好了一个自杀方式，大家围成一个圈，从某个人开始，每次数到第三个人就必须自杀，直到剩下最后一个人时，那个人可以自由选择自己的命运。约瑟夫不想死，他想知道在固定的人数和数到固定的数字的情况下，他应该站在哪个位置，才能成为最后一个存活的人。请你以此为基础，模拟约瑟夫环问题。

【输入格式】
输入共一行，包含两个整数n,m，分别表示约瑟夫环的人数和数到第几个人时自杀。

【输出格式】
输出共一行，包含一个整数，表示最后存活下来的人的编号。

【数据范围】
1≤n,m≤1000

【输入样例】
5 3

【输出样例】
4

【问题分析】
模拟：
首先，我们要将所有人编号为1~n，初始化所有人都是活着的，即将一个数组alive[ ]赋初值为1
接着，我们要进行一个循环，每次循环都从1~n中找到第m个活着的人，将其杀掉，即将alive[ ]中对应的值赋为0
最后，当循环结束时，我们只需要再从1~n中找到alive[ ]中值为1的那个人，即为最后存活的人。

相关问题

约瑟夫环绕问题c++

约瑟夫环绕问题是一个经典的数学问题，也被称为约瑟夫问题或约瑟夫斯置换。问题的描述如下：
有n个人围成一圈排队，从第一个人开始报数，数到 m 的人出列，然后从出列的下一个人开始重新报数，直到所有人都出列。要求找出出列的顺序。

解决这个问题的一种常见方法是使用递归。首先，定义一个递归函数，命名为josephus(n,m)，表示n个人中按照m进行报数的出列顺序。递归函数的返回是一个列表，表示出列的顺序。

递归函数的基本情况是，当只有一个人时，该人是最后出列的，直接返回一个只包含该人的列表。

当有多个人时，我们需要找到第一个出列的人。根据问题的要求，第一个出列的人是从出列的下一个人开始重新报数。所以，我们可以递归调用josephus(n-1,m)，表示去掉第一个人后剩下的n-1个人按照m进行报数的出列顺序。然后，将返回的列表中第一个人加入到结果列表中。

最后返回结果列表，表示n个人按照m进行报数的出列顺序。

下面是一个用Python实现的例子：

def josephus(n,m):
if n == 1:
return [1]
else:
remaining = josephus(n-1,m)
idx = (m-1) % len(remaining)
return remaining[:idx] + [n] + remaining[idx+1:]

n = 10
m = 3
result = josephus(n,m)
print(result)

使用上述代码，当有10个人时，按照每次报数3个人出列的规则，最后出列的顺序为[4, 1, 8, 6, 2, 10, 3, 7, 5, 9]。

2746:约瑟夫问题

约瑟夫问题是一个出现在计算机科学和数学中的问题，也称为约瑟夫斯置换或约瑟夫环。问题描述如下：有n只猴子，按顺时针方向围成一圈选大王（编号从1到n），从第1号开始报数，一直数到m，数到＊＊＊输出最后猴王的编号。

解决约瑟夫问题的方法有很多，其中一种比较简单的方法是使用循环链表。具体来说，我们可以将n只猴子用一个循环链表表示出来，然后从第1只猴子开始，依次数m只猴子，将数到的第m只猴子从链表中删除，直到链表中只剩下一只猴子为止，这只猴子就是猴王。

下面是一个使用循环链表解决约瑟夫问题的伪代码：

1. 定义一个循环链表，将n只猴子加入链表中；
2. 从第1只猴子开始，依次数m只猴子，将数到的第m只猴子从链表中删除；
3. 如果链表中只剩下一只猴子，返回这只猴子的编号，否则回到第2步。