开发者社区> 问答> 正文

【每日一题】数据结构与算法测试题——约瑟夫环

【每日一题】3月19日

问题描述:

假设有n个人站成一圈,每个人都有不同的编号i(1<=i<=n),从编号为1的人开始顺时针方向“1,2,3,4….m”循

环报数,数到m的人出列。然后从出列者的下一个人重新开始按报数,数到m的人再出列,如此重复进行,直

到n个人都出列为止。对于任意给定的n个人原始排列顺序和m值,输出n个人的出列顺序。

0319.jpg

答案在评论区哦,建议大家先思考再看答案,如果有自己的解题想法,欢迎来讨论!

展开
收起
答题小助手 2020-03-19 17:35:37 1851 2
1 条回答
写回答
取消 提交回答
  • 本期答案

    1、现在假设参与人数为:n=8;指定出列数:m=4;

    那么第一个出列的数为:4 . . .

    2、数组结构示意图: 约瑟夫.png

    3、设出列元素的下标为t,初始值为:t=0,可以得到一个规律:

    t=(t+m-1)%n=(0+4-1)%8=3;

    那么数组下标为3的人出列。出列一个元素之后,数组的规模:n-1;然后出列位置后面的元素向前移动。

    import java.util.Scanner;
    public class Tree1 {
      int[] a=new int[20];				//定义成员编号数组
      int n;						//定义参与人数的属性
      public static void main(String[] args) {
    	  Scanner input=new Scanner(System.in);
    	Tree1 l=new Tree1();
    	System.out.println("请输入参与人数的整数值:");
    	l.n=input.nextInt();
    	int m=0;
    	System.out.println("请输入出列的整数值:");
    	m=input.nextInt();
    	for(int i=0;i<l.n;i++) {
    		l.a[i]=i+1;
    	}
    	System.out.println("*************");
    	int t=0;
    	while(l.n>0) {					//利用循环将所有人员出列
    		t=(t+m-1)%l.n;			//得到出列人员的下标
    		System.out.print("\t"+l.a[t]);
    		for(int j=t+1;j<l.n;j++) {				//利用循环将出列人员位置后面的数组元素前移
    			l.a[j-1]=l.a[j];
    		}
    		l.n--;					//出列一个人员之后参与人员数目n-1
    }
    }
    
    
    2020-03-19 17:42:46
    赞同 1 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载