约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
时间复杂度:O(mn)
import java.util.Iterator;
import java.util.List;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
yuesefu2(10, 2, 3);
}
public static void yuesefu2(int n,int k,int m)//该方法使用队列实现
{
Queue<Integer> queue=new LinkedList<Integer>();
for(int i=k;i<=n+k-1;i++)
{
queue.offer((i%n!=0)?i%n:n);
}
int len=n;
int j=1;
while(len>0)
{
if(j==m)
{
System.out.println("编号"+queue.poll());
len--;
j=1;
}
else {
int t=queue.poll();
queue.offer(t);
j++;
}
}
}
//实现方式1:采用数组
/*
* 出圈就将该位置0,同时总长度减一,需要指示数
*
*/
public static void yuesefu1(int n,int k,int m)
{
int [] men=new int[n];
for(int i=1;i<=n;i++)
{
men[i-1]=i;
}
int len=n;//标记长度
int i=k-1;//位置指示 这里不能写成K,注意数组是从0开始的
int j=1;//1-m数数
while (len>0) {
if(men[i%n]>0)
{
if(j==m)
{
System.out.println("编号"+men[i%n]);
men[i%n]=0;
len--;
j=1;
i++;
}
else {
j++;//报数
i++;//下一位
}
}
else {
i++;//该位已经出圈,跳到下一位
}
}
}
}
输出
编号4
编号7
编号10
编号3
编号8
编号2
编号9
编号6
编号1
编号5