把我上学时候在csdn上的笔记搬过来了，便于自己查找
经典的约瑟夫问题
题目：假设下标从0开始，0，1，2 .. n-1共n个人，从1开始报数，报到m则此人从环中退出，下一个人重新从1开始报数，以此类推，问最后剩下的一个人的编号是多少？
分析：
看到这个题目，我想最简单的思路就是写个程序模拟这个过程，最终产生结果。
首先我们需要一个长度为n的数组，每个位置有两个状态分别表示该处的人是否退出，可以选择boolean型。需要一个变量i来移动反复遍历数组，变量s来计数是否达到m，还需要一个变量count来计数环内到底还有几个人，以终止遍历。
算法如下：
public static int yueSe(int n, int m) {
//true 表示退出 ，false表示没有退出
boolean[] arr = new boolean[n];
int i = 0;
int s = 1;
int count = n;
while (count > 0) {
i++;
if (i > n - 1) {
i = 0;
}
if (!arr[i]) {
s++;
if (s == m) {
s = 0;
arr[i] = true;
System.out.print(i+" ");
count--;
}
}
}
return i;
}
但是这种算法我们分析出它每删除一个元素循环就要进行m次，那么总的时间复杂度就是O(mn) ，并不理想。题目只是要求我们求出最后一个人的编号，我们可以另辟蹊径。
我们知道第一个人（编号一定是(m-1)%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod n的人开始）：
k ，k+1， k+2 … n-2, n-1, 0, 1, 2 , … ，k-2
我们把他们的编号做一下转换：
k –> 0
k+1 –> 1
k+2 –> 2
…
…
k-2 –> n-2
那么变换之后问题变成了和原问题一样的问题只是规模变成了n-1，照这个思路下去最终数组长度变为1，转换之后的角标为0；这时候只要我们倒着推0转换前的角标为x，x转换前的角标为x’,x’转换前的角标为x”，有灵感了没有这么递推的话只要我们递归n-1次即可得到我们想要的角标。
关键是这个递推公式是什么呢？
我们可以先看正着递推的思路，假设当前角标为x那么改变后的角标y为
y=(x+n-k)%n ,其中k=m
那么倒推得公式即为
x=(y+k)%n ,这里对于一般情况我们要理解n是删除前的数组长度。
算法如下：
public static int yueSe2(int n,int m){
int f=0;
for(int i=2;i<=n;i++){
f=(f+m)%i;
}
return f;
}
网易笔试题（约瑟夫问题变形）
题目：小明同学把1到n这n个数字按照一定的顺序放入了一个队列Q中。现在他对队列Q执行了如下程序：
while(!Q.empty()) //队列不空，执行循环
{
int x=Q.front(); //取出当前队头的值x
Q.pop(); //弹出当前队头
Q.push(x); //把x放入队尾
x = Q.front(); //取出这时候队头的值
printf("%d\n",x); //输出x
Q.pop(); //弹出这时候的队头
}
做取出队头的值操作的时候，并不弹出当前队头。
小明同学发现，这段程序恰好按顺序输出了1,2,3,…,n。现在小明想让你构造出原始的队列，你能做到吗？
这个题目虽然是取出一个放到队列尾，删除接下来一个，但是仔细一想其实这个问题和约瑟夫问题是一样的，而且m=2。但是这个题是要确定所有位置的出场顺序，目前博主没有找到O(n)的解法，不多做分析啦，相信大家一看就懂，代码如下
public static void answer(int n) {
int[] arr = new int[n];
int count = 0;
int i = 0;
int s = 1;
while (count < n) {
i++;
if (i > n - 1) {
i = 0;
}
if (arr[i] == 0) {
s++;
}
if (s == 2) {
s = 0;
count++;
arr[i] = count;
}
}
for (int j = 0; j < n - 1; j++) {
System.out.print(arr[j] + " ");
}
System.out.print(arr[n - 1]);
}
网友评论