Java数组解决约瑟夫环问题

Java数组解决约瑟夫环问题

N个人围成一圈顺序编号，从1号开始按1、2、3…顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。 请按退出顺序输出每个退出人的原序号。

输入格式:

输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。

输出格式:

按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。

输入样例:

在这里给出一组输入。例如： 7 3 结尾无空行

输出样例:

3 6 2 7 5 1 4 结尾无空行

思路：

count计数当count=n说明全部出列，用k来记录报数。 创建一个大小为n+1的数组，初始化为零，每次只有数组元素为零的报数，通过数组下表来代表人的序号，当下标为i的元素数到m时将a[i]的值赋为1，每次读到a[i]的值为1时将此位置的序号i输出，并将记录的报数值k赋为0重新开始报数

代码如下：

import java.util.Scanner;

public class Main {
          
   
    public static void main(String[] args) {
          
   
        Scanner scan=new Scanner(System.in);
        int n,m,count=0,i=0,k=1;
        n=scan.nextInt();
        m=scan.nextInt();
        int a[]=new int [n+1];
        while(count!=n)
        {
          
   
            i++;
            if(i>n)
                i=1;
            if(a[i]==0)
            {
          
   
                
                if(k==m)
                {
          
   
                    
                    a[i]=1;
                    count++;
                    System.out.print(i);
                    if(count!=n)
                    System.out.print(" ");
                    k=0;
                }
                k++;
            }
            
        }
    }
}

递归代码：

public static int recursion(int n, int m, int i)
    {
          
   
    //起始为0
//        if(i==1)return(n+m-1)%n+1;
//        else return(recursion(n-1,m,i-1)+m-1)%n+1;
    //起始为1
        if(i==1)return (n+m-1)%n;
        else return (recursion(n-1,m,i-1)+m)%n;
    }