首页 > 其他分享 >P1996 约瑟夫问题-循环链表方法

P1996 约瑟夫问题-循环链表方法

时间:2023-04-17 23:55:48浏览次数:43  
标签:输出 出圈 int 约瑟夫 链表 P1996 include 节点

题目描述

n 个人围成一圈,从第一个人开始报数,数到 m 的人出列,再由下一个人重新从 1 开始报数,数到 m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1 名小朋友,而该题是全部出圈。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数,按顺序输出每个出圈人的编号。

输入输出样例

输入 #1
10 3
输出 #1
3 6 9 2 7 1 8 5 10 4

说明/提示

1≤m,n≤100

 

分析:

  利用模拟链表来实现查找下一个节点,将尾与头连在一起形成循环链表,当出圈时可直接将出圈节点删除,为了防止出现下标0可以将节点全部向前移动1个节点。

代码:

#include <iostream>
#include <cstdio>

using namespace std;

const int N=110;

int ne[N];
int n,m;

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<n;i++) ne[i]=i+1;
    ne[n]=n;
    
    int now=n;
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<m;j++) now=ne[now];
        printf("%d ",ne[now]);
        ne[now]=ne[ne[now]];
    }
    
    return 0;
}

 

标签:输出,出圈,int,约瑟夫,链表,P1996,include,节点
From: https://www.cnblogs.com/yaowww/p/17328030.html

相关文章

  • 用双链表实现双端队列
    //双链表publicstaticclassNode<V>{publicVvalue;publicNode<V>last;publicNode<V>next;publicNode(Vv){value=v;last=null;next=null;}}//双端队列前后皆可进出publicstaticclassMyDequ......
  • [Leetcode]删除链表中等于val 的所有结点
    力扣链接方法一:使用前后两个指针,cur指向当前位置,prev指向前一个位置,通过改变指向和释放结点来删除val初步代码,还存在问题:/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*remo......
  • 四种语言刷算法之环形链表
    力扣141. 环形链表1、C/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/boolhasCycle(structListNode*head){if(head==NULL||head->next==NULL)returnfalse;structListNode*p=h......
  • 单双链表
    单链表定义//单链表publicstaticclassNode{publicintvalue;publicNodenext;publicNode(intdata){value=data;}}单链表反转新增1、2、3三个节点publicstaticNodereverseLinkedList(Nodehead){Nodepre=null;Nodenext=......
  • leetcode160-相交链表
    leetcode160方法一:哈希表思路:先创建一个unordered_set,存放ListNode*类型的变量先遍历其中一个链表,把所有节点的指针放在set中再遍历另一个链表,查找是否存在一个节点已经在set中,如果存在则说明这是它们的相交节点的指针,返回这个指针,如果不存在则说明不存在相交节点,......
  • 链表
    数据的创建,前插后插,遍历,计数,动态内存开辟动态创建等#include<stdio.h>#definededata8structTest{ intdata; structTest*next;};voidPrintlink(structTest*point){ //structTest*point; //point=head; intcount=0; while(point!=NULL) { print......
  • [牛客]链表中倒数第k个结点
    牛客链接使用快慢指针法:两种思路:1.fast先向后走k-1次,slow再向后走1次,然后fast和slow同时向后走,当fast走到最后一个结点时,slow刚好在倒数第k个位置上;2.fast先向后走k次,slow再向后走1次,然后fast和slow同时向后走,当fast走到最后一个结点的后面时(此时为NULL),slow刚好在倒数......
  • 算法-回文链表-24
    /***Definitionforsingly-linkedlist.*publicclassListNode{*publicintval;*publicListNodenext;*publicListNode(intx){val=x;}*}*/publicclassSolution{publicListNodeReverseList(ListNodehead){i......
  • 链表
    list链表:STL中的链表是双向循环链表迭代器不支持随机访问包括数据域和指针域构造:默认、区间、拷贝、n个elem赋值:重载=、区间,n个elem交换:swap();大小:resize();插入和删除:remove();insert();erase();数据存取:无法使用[]和at, 可以使用front();back();不支持随机访问的......
  • 环形链表_相交链表_多数元素(java语言)
    环形链表力扣141题问题:思路:创建hashset,把链表的每个节点放到集合中,在放入的过程中检查这个节点是否已经存在,存在则证明存在环。代码实现:publicclassSolution{publicbooleanhasCycle(ListNodehead){Set<ListNode>set=newHashSet<>();whi......