约瑟夫环

高俊

import java.util.Scanner;
/**
8 Z9 J4 N! C4 x! l; R0 v*使用数组实现约瑟夫环问题
7 f) a7 x6 y( c1 E4 t1 O0 D*由m个人围成一个首尾相连的圈报数。
" B; W! U: C- S; ]2 R. V4 D*从第一个人开始，从1开始报数，报到n的人出圈，
*剩下的人继续从1开始报数，直到所有的人都出圈为止。
*对于给定的m和n，求出所有人的出圈顺序.
/ Q1 k4 @( }' C4 k- x*/
public class RingTest{
, p$ c4 |4 A3 ^" o! @: K/ w* s    public static void main(String[] args){
$ Q4 N) E6 u6 _$ I        System.out.println("程序说明如下：");
        System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");
        //提示输入总人数
        System.out.println("请输入做这个游戏的总人数：");
        Scanner sca=new Scanner(System.in);
        int m=sca.nextInt();
7 [' T/ u  x2 ~+ m        //提示输入要出圈的数值
        System.out.println("请输入要出圈的数值：");        
4 I. J  Y3 J! v1 H- l% Y. V        int n=sca.nextInt();
        System.out.println("按出圈的次序输出序号：");        
: p8 ?: S7 L. f4 m        //创建有m个值的数组
        int[] a=new int[m];
* X" H2 J3 ~  x2 b. K  L8 ?! G* {        //初始长度，以后出圈一个，长度就减一
        int len=m;
        //给数组赋值
1 V/ e  ^$ A" o/ t        for(int i=0;i<a.length;i++)
$ S2 L8 ]. ?4 y; j2 L            a[i]=i+1;
; ^+ h! H& _1 f: @3 N$ N, O1 Z$ G        //i为元素下表，j代表当前要报的数
        int i=0;
        int j=1;
" h# T& l6 B, m4 e6 M, p' e* b3 R& I/ p        while(len>0){
( T' N2 C  B: `% r2 l7 t            if(a[i%m]>0){
8 S( E8 f9 O- f+ v- w' A1 J; F                if(j%n==0){//找到要出圈的人，并把圈中人数减一
                    System.out.print(a[i%m]+"  ");
                    a[i%m]=-1;
                    j=1;
                    i++;
                    len--;
                }else{
0 a; i- E8 u& z/ Z                    i++;
                    j++;
                }
& L/ s2 T+ t3 [            }else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
                i++;
            }
        }
    }
- h. _, x# t# q+ n}
8 M0 V7 @( [4 W2 r0 T+ U3 J5 z

java宫城大师

学习一下。谢谢

woniu

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

幕后摆手

若m个人以1到m编号，剩余人数为i；当n＜=m时，首先是n至m号的人先出圈；n＞i,每轮第n%i个人出圈。
" q1 M, e! A0 S; {, _" dn＞i的情况下：
n除以i的商为1时，从n%i对应的序号开始每隔一位的序号出圈（n%i, n%i + 2,...,[末位序号或末位序号-1]）
1 s3 k, U% D$ H6 R. @- Bn除以i的商为2时，出圈顺序同上规律...
8 t2 j5 T$ e& Nint i = m;
List<Integer> baselist = new ArrayList<>();
int[] res = new int[m];
for(int j = 0;j < m;j++)
        baselist.add(j+1);
' ~2 S2 G, k# n9 Ofor(;i >= n;i--){
9 Q% R& S6 i6 i- D        res[m - i] = m + n - i;
7 q# U9 n3 A. n        baselist.remove((Integer)(m + n - i));
) d1 i2 n1 u# L6 p8 E}
$ k8 n, n! H2 x) i% cwhile(i > 0){
  ^' B5 R# c; ~3 j$ ?/ n" n$ E        for(int j = n%i==0? i-1: n%i -1;j < baselist.size();j++){
                res[m - i--] = baselist.get(j);
                baselist.remove(j);
# O9 U  k$ m& a  f" ~1 t2 J        }
7 h  A' R1 J/ S7 J9 m2 e0 k}
( a' o% g, F- V4 L* v) Q数组res为所求

缘丨妙不可言

1111111111111