约瑟夫环

高俊

/ P8 W  s% ]" Wimport java.util.Scanner;
/**
*使用数组实现约瑟夫环问题
*由m个人围成一个首尾相连的圈报数。
*从第一个人开始，从1开始报数，报到n的人出圈，
*剩下的人继续从1开始报数，直到所有的人都出圈为止。
*对于给定的m和n，求出所有人的出圈顺序.
*/
public class RingTest{
( `0 K3 a; G# n    public static void main(String[] args){
) G" Z) N1 x& G        System.out.println("程序说明如下：");
        System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");
6 h9 j- L. O& i        //提示输入总人数
  {3 }3 g2 u" A: ]        System.out.println("请输入做这个游戏的总人数：");
7 [* q+ V8 r' J0 W4 i& V8 z9 l        Scanner sca=new Scanner(System.in);
/ Q/ y) D7 e+ d8 \( f; ?        int m=sca.nextInt();
        //提示输入要出圈的数值
        System.out.println("请输入要出圈的数值：");        
1 j: V  j. H: C% P        int n=sca.nextInt();
        System.out.println("按出圈的次序输出序号：");        
* I7 e; P0 L& R, T, n        //创建有m个值的数组
" ~; u# L* @9 ]8 Y9 }( m        int[] a=new int[m];
0 S  l& [* E9 ]+ _$ K; M3 X( N" u        //初始长度，以后出圈一个，长度就减一
        int len=m;
        //给数组赋值
% I7 ~' D2 ~7 V/ L% K" ]% Z5 V        for(int i=0;i<a.length;i++)
            a[i]=i+1;
0 z$ z# n) y* U        //i为元素下表，j代表当前要报的数
        int i=0;
        int j=1;
        while(len>0){
            if(a[i%m]>0){
                if(j%n==0){//找到要出圈的人，并把圈中人数减一
/ U1 ]& V+ l! c! H                    System.out.print(a[i%m]+"  ");
7 q: f3 E# h; c, j9 Y8 p& K                    a[i%m]=-1;
' i: k2 l# c9 y/ D; t$ k  s                    j=1;
- t" D' P; P/ V. n                    i++;
5 `; R, s2 y- ]+ s, i                    len--;
                }else{
# T- `" `/ m+ v2 |9 [: ^                    i++;
/ O5 K6 j% v+ s. B1 R, S" J* z' o                    j++;
2 V- ^- i9 s+ \* h0 d                }
1 \. }4 t! ]- G* d" y            }else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
3 e+ [+ a% V1 T7 R                i++;
            }
        }
4 k( P& d% b# l# S; G    }
. d3 f! V* M) e/ Y5 ^! }}

& _. T+ v% E( A0 j' X
: E# |# S' k1 A. n' Z4 K

java宫城大师

学习一下。谢谢

woniu

这个项目太棒勒！下下来学习下！

幕后摆手

若m个人以1到m编号，剩余人数为i；当n＜=m时，首先是n至m号的人先出圈；n＞i,每轮第n%i个人出圈。
7 n. Z; J+ d, N6 Gn＞i的情况下：
n除以i的商为1时，从n%i对应的序号开始每隔一位的序号出圈（n%i, n%i + 2,...,[末位序号或末位序号-1]）
* R; }+ S+ A- j+ Z$ j/ Ln除以i的商为2时，出圈顺序同上规律...
int i = m;
List<Integer> baselist = new ArrayList<>();
int[] res = new int[m];
for(int j = 0;j < m;j++)
2 a! o+ l7 J- O! L, p1 |) w        baselist.add(j+1);
* Z% j1 x: c; q& b6 S1 c# Zfor(;i >= n;i--){
) j1 Z8 R' T- X" F/ E$ n( r        res[m - i] = m + n - i;
2 X; |. e. A4 A6 k- j4 M! ?6 V        baselist.remove((Integer)(m + n - i));
: A0 r: d! w  L3 U6 C- f; t1 l}
while(i > 0){
        for(int j = n%i==0? i-1: n%i -1;j < baselist.size();j++){
                res[m - i--] = baselist.get(j);
- v& h! [. W* X1 q, L  i                baselist.remove(j);
2 B& o; k- w; N& g' v( M2 R        }
}
. `  B$ c& q7 ^. |. M数组res为所求

缘丨妙不可言

1111111111111