约瑟夫环 队列+链表

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编号分别为1,2,…,n,打印出列的顺序。

【算法分析】

       本题我们可以用数组建立标志位等方法求解,但如果用上数据结构中循环链的思想,则更贴切题意,解题效率更高。n人围成一圈,把一人看成一个结点,n人之间的关系采用链接方式,即每一结点有一个前继结点和一个后继结点,每一个结点有一个指针指向下一个结点,最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当m人出列时,将m结点的前继结点指针指向m结点的后继结点指针,即把m结点驱出循环链。

1、建立循环链表。

       当用数组实现本题链式结构时,数组a[i]作为"指针"变量来使用,a[i]存放下一个结点的位置。设立指针j指向当前结点,则移动结点过程为j=a[j],当数到m时,m结点出链,则a[j]=a[a[j]]。 当直接用链来实现时,则比较直观,每个结点有两个域:一个数值域,一个指针域,当数到m时,m出链,将m结点的前继结点指针指向其后继结点;

2、设立指针,指向当前结点,设立计数器,计数数到多少人;

3、沿链移动指针,每移动一个结点,计数器值加1,当计数器值为m时,  则m结点出链,计数器值置为1。

4、重复3,直到n个结点均出链为止。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[10000001];
 5 int tot=1;
 6 int main()
 7 {
 8     int n,m;
 9     cin>>n>>m;
10     int j=n;
11     for(int i=0;i<n;i++)
12     {
13         a[i]=i+1;
14     }
15     a[n]=1;
16     int k=1;//报数 
17     while(tot<=n)
18     {
19         while(k<m)
20         {
21             j=a[j];
22             k++;
23         }
24         //cout<<a[j]<<" ";
25         printf("%d ",a[j]);
26         a[j]=a[a[j]];
27         k=1;
28         tot++;
29     }
30     return 0;
31 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 验证二叉查找树题目分析代码

2 / 1 4 / 3 5 上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.

12020
来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

29540
来自专栏每日一篇技术文章

Swift3.0 - 集合

10630
来自专栏用户2442861的专栏

List、Set、Map、数组之间各种转换

刚学Java不久的时候,接到一个电面,然后问了一些java的知识,比如说Java的编码,Unicode等,但是最让我蛋疼的是怎么吗map转为set,那个时候对...

38020
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

11640
来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

10120
来自专栏武培轩的专栏

Hashtable源码解析(JDK1.8)

1 package java.util; 2 3 import java.io.*; 4 import java.util.concu...

31140
来自专栏博岩Java大讲堂

Java集合--List源码

25740
来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

18520
来自专栏专注 Java 基础分享

从源码解析TreeMap

     上篇文章我们介绍了HashMap集合,这是一个键值对集合,可以高效的按照键查找数值。但是它有一个缺陷:数据如果是无序的可以是很高效的,但是如果数据...

21280

扫码关注云+社区

领取腾讯云代金券