C循环链表解决约瑟夫斯问题

蔚落 2021-07-16 13:38 343阅读 0赞

## 循环链表解决约瑟夫斯问题 ##

**问题描述：设有n个人围坐成一个圆圈，按一定指向方向，从第s个人开始报数，数到m的人出列，然后从下一个人重新报数，数到m的人又出列，…，直到n个人全部出列为止。  
输入：n m s，按次序输出得到的n个人的顺序表。**

#include<iostream>
    using namespace std;
    typedef int datetype;
    
    typedef struct node//构建链表节点 
    { 
    	datetype data;
    	struct node* next;
    }ListNode,*LinkList;//节点与表头指针
    
    void CreateCircleLinkList(LinkList &rear,int n)//创建链表 
    { 
    	ListNode *p,*pre;
    	p = NULL;
    	rear=pre= NULL;
    	for (int i = 0; i < n; i++)
    	{ 
    		p = new ListNode;
    		p->data = i + 1;
    		if (rear == NULL) rear = p;
    		if (pre != NULL) pre-> next= p;
    		pre = p;
    	}
    	p->next = rear;//循环链表的构建 
    	pre = rear;//pre 指向链首节点
    	rear=p;//rear 指向链尾节点 
    }
    
    void josephus(LinkList &rear,int m,int s)//约瑟夫斯 问题 
    { 
    	ListNode *p;
    	for(int i=1;i<s;i++)//移到s-1个节点，从第s个人开始报数 
    	{ 
    		rear=rear->next;
    	}
    	while(rear->next!=rear)//当循环链表不为一个节点 
    	{ 
    		for(int i=1;i<m;i++)//移动m-1个人后再将第m个出列 
    		{ 
    			rear=rear->next;
    		}
    		p=rear->next;
    		cout<<p->data<<" ";
    		rear->next=p->next;//将报到m的人出列
    		delete p;
    	}
    	cout << rear->data;
    }
    
    int main()
    { 
    	LinkList rear;
    	int n,m,s;
    	cin>>n>>m>>s;
    	cout << endl;
    	CreateCircleLinkList(rear,n);
    	josephus(rear,m,s);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，343人围观）

还没有评论，来说两句吧...

相关阅读

相关链表—约瑟夫问题

单向环形链表应用场景约瑟夫问题：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位

爱被打了一巴掌/ 2022年12月02日 10:51/ 0 赞/ 176 阅读

相关用java解决约瑟夫循环问题_Java 用单向循环链表实现约瑟夫问题

public class lianbiao2 \{ class Node\{ Node next; int number; public Node getNext()

迈不过友情╰/ 2022年11月06日 14:50/ 0 赞/ 169 阅读

相关约瑟夫问题——循环链表

think: 1顺序建立循环链表+循环链表中的符合题意的元素结点的删除 2注意只有一个人玩死亡游戏的情况 [sdut原题链接][sdut] 约瑟夫问题 Time

秒速五厘米/ 2022年09月28日 11:46/ 0 赞/ 162 阅读

相关 Go-根据单向循环链表解决约瑟夫问题

单向循环链表实现：[https://blog.csdn.net/luyaran/article/details/119970185][https_blog.csdn.net_l

分手后的思念是犯贱/ 2022年09月09日 02:21/ 0 赞/ 145 阅读

相关活用内核链表解决约瑟夫斯问题

约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为“约瑟夫环”，也有的地方叫做“丢手绢”。问题是这样的：

男娘i/ 2022年06月09日 14:52/ 0 赞/ 162 阅读

相关 C语言链表约瑟夫问题

约瑟夫问题 Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针

你的名字/ 2022年06月01日 05:55/ 0 赞/ 169 阅读

相关循环链表解决约瑟夫环问题

　　约瑟夫环问题可以简单的使用数组的方式实现，但是现在我使用循环链表的方法来实现，因为上午看到一道面试题规定使用循环链表解决约瑟夫环问题。　　什么是约瑟夫环？　　“约瑟

Love The Way You Lie/ 2022年04月10日 08:22/ 0 赞/ 199 阅读

相关约瑟夫问题循环链表做法

程序代码如下： include<stdio.h> include<stdlib.h> include<assert.h> defi

素颜马尾好姑娘i/ 2022年03月26日 06:10/ 0 赞/ 228 阅读

相关 C++数据结构--循环链表的应用--解决约瑟夫问题

解决问题过程图解 ![20130731102002984][] 实现代码： //n个竞争者，每隔m个竞争者就淘汰一个 //返回值为胜

偏执的太偏执、/ 2021年12月01日 15:46/ 0 赞/ 204 阅读

相关 C循环链表解决约瑟夫斯问题

循环链表解决约瑟夫斯问题问题描述：设有n个人围坐成一个圆圈，按一定指向方向，从第s个人开始报数，数到m的人出列，然后从下一个人重新报数，数到m的人又出列，…，直到n

蔚落/ 2021年07月16日 13:38/ 0 赞/ 344 阅读