我的日常

登录/注册
您现在的位置:论坛 盖世程序员(我猜到了开头 却没有猜到结局) 项目源码 > 约瑟夫环
总共48087条微博

动态微博

查看: 1349|回复: 4

约瑟夫环

[复制链接]

2

主题

0

听众

18

金钱

一袋弟子

该用户从未签到

跳转到指定楼层
楼主
发表于 2015-12-14 21:31:55 |只看该作者 |倒序浏览
- d" d! U; g6 f; ^3 b1 ?" y
import java.util.Scanner;, h; N7 V8 Z/ p! O1 S7 D( q2 O; s
/**, J  ]/ s0 D  }8 y' ]/ P
*使用数组实现约瑟夫环问题  x7 R: ~- z+ q$ P" \( C% A
*由m个人围成一个首尾相连的圈报数。9 U0 f* S$ @+ z0 k- ^5 F
*从第一个人开始,从1开始报数,报到n的人出圈,! b* |( k" G$ c
*剩下的人继续从1开始报数,直到所有的人都出圈为止。- u* H) P. L' U1 f1 _) }
*对于给定的m和n,求出所有人的出圈顺序.
" `6 d9 g! P  ]' @+ q2 F*/
) R4 z' k: J. l. {public class RingTest{
! ^( w: r: A+ K# d) Y, ~2 v    public static void main(String[] args){
, ~" l+ Z6 T, U9 W! v; p        System.out.println("程序说明如下:");
8 A$ U# v2 Z/ g% A; ^        System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始,从1开始报数,报到n的人出圈,剩下的人继续从1开始报数,直到所有的人都出圈为止。对于给定的m和n,求出所有人的出圈顺序.");
1 X0 S# }& e$ f+ ~( g        //提示输入总人数& _' U) F$ g  ]! Y2 ?2 Y. M
        System.out.println("请输入做这个游戏的总人数:");* N6 @; V4 k3 A+ j: K. m
        Scanner sca=new Scanner(System.in);
7 |# c5 H2 Z5 H7 `# P        int m=sca.nextInt();% x' y( }; A( _9 v. j6 m
        //提示输入要出圈的数值+ [5 a% }9 S6 w1 Y$ Q" X9 v" R0 Y
        System.out.println("请输入要出圈的数值:");        8 Z1 r" ^/ ~5 N9 j3 |6 A9 N
        int n=sca.nextInt();$ |) K* n% X, D7 s
        System.out.println("按出圈的次序输出序号:");        ' M8 D1 ?3 o" ~1 ?9 V
        //创建有m个值的数组8 J/ B  h5 V- C
        int[] a=new int[m];3 B3 q2 {* {& f) W! O- ~
        //初始长度,以后出圈一个,长度就减一/ T6 v; ]' T- D! O9 u5 H
        int len=m;% l6 e- m, F: _, e5 Z# @
        //给数组赋值! s/ S4 A+ m* r; Z. H
        for(int i=0;i<a.length;i++)
: j% f9 {4 a) v            a[i]=i+1;( J: F8 X! S+ m' a$ ?; c6 F) j( e
        //i为元素下表,j代表当前要报的数
5 k/ p2 r4 ?$ V  _7 t3 v7 c; D9 E        int i=0;+ z  h% F' ^3 b; C
        int j=1;
( o3 m% M0 z) j- N$ j* i7 G: K        while(len>0){
' Z: G* J5 n, v# ~( i1 c% ]            if(a[i%m]>0){
$ g- v/ p; ^1 r, {# u2 d                if(j%n==0){//找到要出圈的人,并把圈中人数减一' _" M: F2 ?  |% o* P" K
                    System.out.print(a[i%m]+"  ");: {! K2 I& S$ t/ t: R; y2 m# D5 o; N
                    a[i%m]=-1;
+ u- V/ K; G6 a: E                    j=1;+ w, C: z. o& X! g3 h' _: P" y
                    i++;
* A7 G- i) _. H) g! b: N% x                    len--;* L) R- ~: y) E5 \* e  w1 K
                }else{9 A$ ^3 A% E( e: P# x& E
                    i++;
& P  e+ f( Z/ o% I% l/ s. u                    j++;
$ p6 _, w) }' D                }
; ?- U6 \; K3 n% m4 D4 p) q5 [6 x            }else{//遇到空位了,就跳到下一位,但j不加一,也就是这个位置没有报数: T: B0 t6 a& `& r% l% h
                i++;) _: a6 S0 d! Z: Z+ W7 o4 d, E) u6 ~5 y- ?
            }
8 q% s$ a( r, o) o$ Q  Q! `        }4 n) U" M" K" W
    }
) l! n* Y( q9 `+ f3 ?1 O7 i}
& k1 J0 ~  i4 x& s- k& a2 H0 [4 u) \6 L
+ w3 D8 q1 Y7 |# M" w, O+ B

科帮网 1、本主题所有言论和图片纯属会员个人意见,与本社区立场无关
2、本站所有主题由该帖子作者发表,该帖子作者与科帮网享有帖子相关版权
3、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和科帮网的同意
4、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任
5、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责
6、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除并致以最深的歉意
7、科帮网管理员和版主有权不事先通知发贴者而删除本文


JAVA爱好者①群:JAVA爱好者① JAVA爱好者②群:JAVA爱好者② JAVA爱好者③ : JAVA爱好者③

1

主题

3

听众

341

金钱

四袋长老

该用户从未签到

沙发
发表于 2016-03-17 22:08:20 |只看该作者
学习一下。谢谢
回复

使用道具 举报

woniu 实名认证   

2

主题

0

听众

330

金钱

四袋长老

该用户从未签到

板凳
发表于 2016-04-12 11:39:10 |只看该作者
这个项目太棒勒!下下来学习下!
回复

使用道具 举报

1

主题

0

听众

81

金钱

三袋弟子

该用户从未签到

地板
发表于 2016-11-01 15:48:08 |只看该作者
若m个人以1到m编号,剩余人数为i;当n<=m时,首先是n至m号的人先出圈;n>i,每轮第n%i个人出圈。& X2 ~- d' w5 }- t+ b
n>i的情况下:/ k8 p6 U8 T# e0 H: I* q
n除以i的商为1时,从n%i对应的序号开始每隔一位的序号出圈(n%i, n%i + 2,...,[末位序号或末位序号-1])
& I5 i0 \$ \3 y  s5 p; `3 B) Un除以i的商为2时,出圈顺序同上规律...
5 c6 V! f- ~- a# Bint i = m;
) d! N; o) i, y' Z2 W1 eList<Integer> baselist = new ArrayList<>();" e/ i- l& T  S- j6 Q
int[] res = new int[m];- A/ ?! ?! w) Z' H8 m, T, l
for(int j = 0;j < m;j++)
9 n& u& h) a+ `5 I5 J7 ?! z; p0 ?        baselist.add(j+1);. }8 k* A: }/ d, g# U9 g% H9 O
for(;i >= n;i--){
3 a/ G. U* Y9 Y% W& k        res[m - i] = m + n - i;; r+ `6 Q; u$ k- s& d1 g2 J4 w
        baselist.remove((Integer)(m + n - i));
/ d- |, I4 |& |. K( ^; c2 j}
! \$ c( c0 Q1 swhile(i > 0){1 S0 p  `# p7 q8 o- Q
        for(int j = n%i==0? i-1: n%i -1;j < baselist.size();j++){$ S& n& v' A) }8 Z- X% d
                res[m - i--] = baselist.get(j);
* [$ Q1 i; s5 D( g9 R' S                baselist.remove(j);
3 a5 m1 I/ E+ j$ g  _        }
9 z2 O) e3 K5 g& l0 \0 q7 _}
  h3 Z# W7 G. o4 q' `9 V  d数组res为所求
" w& D; ?  I; K
回复

使用道具 举报

0

主题

0

听众

104

金钱

三袋弟子

该用户从未签到

5#
发表于 2017-12-20 18:33:04 |只看该作者
1111111111111
回复

使用道具 举报

快速回复
您需要登录后才可以回帖 登录 | 立即注册

   

关闭

站长推荐上一条 /1 下一条

发布主题 快速回复 返回列表 联系我们 官方QQ群 科帮网手机客户端
快速回复 返回顶部 返回列表