约瑟夫环问题(循环链表解法)

标签: 计算机基础

1. 题干

有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位。
输入
初始人数n
输出
最后一人的初始编号
样例输入
3
样例输出
2

2.故事背景

故事背景:
据说著名犹太历史学家 Josephus 有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人 开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止,然而 Josephus 和他的朋友并不想遵从,Josephus 要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

注:故事背景参考链接1

3. 抽象成数学概念

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后 [1] 结果+1即为原问题的解。

4. 代码

#include <stdio.h>
#include <malloc.h>


//约瑟夫环问题,循环链表


typedef struct student {

	int data; //存储编号
	struct student *next;  //存储next指针,指向下一个结构
}*node,Node; // 定义数据类型,结构体指针node,结构Node

node creat(int n);  //创建链表函数
void function ( node pList, int REPORT); //处理链表

int  main ( )

{
	int n;  //要数数的人数,事前给定;//链表的头节点
	node head1; //创建链表的头节点指针
	int REPORT = 3;
	scanf("%d",&n);
	
	//创建链表
	head1 = creat(n);  //创建链表,返回头节点指针
	
	//处理链表
	
	function( head1,REPORT);
	
	
	return 0;
}


node creat(int n){
	
	node p_first;  //头节点指针
	p_first  = (node)malloc (sizeof (Node)); //开辟内存空间,返回类型Node *
	p_first->next = NULL;  //next指针域 赋空指针
	node q = p_first; // q也指向头节点,p_first主要作为头地址的备份
	node p;  // 结构体指针变量
	
	for (int i=0; i<n;i++){
		
		p = (node) malloc(sizeof(Node));
		p->data = i+1;   // 输入编号
		
		q->next = p;
		p->next = NULL; //先视为单链表
		q = p; //q更新,把其视为下一个循环的头
		
	}
	
	q->next = p_first->next;   //尾节点与首节点搭在一起,循环链表构造
	return p_first;
}


void function ( node pList, int REPORT)   //这个函数实现链表的处理
{
	
	node p = pList->next;  // 指向头节点的下一个节点
	free ( pList);  //释放头节点
	node q = NULL;  // 定义一个空指针q
	
	while ( p->next !=p )  //即节点的个数大于1个的时候,进行处理
	{
		
		for (int i=0; i<REPORT -2;i++){
			
		//当前p指向第一个节点,当报数为3时,它需要移动1=3-2 次,
		//1=REPORT -2
		p=p->next; //for 循环结束时,p节点为需要删除的节点的前一个位置
		}
		
		q=p->next;  //此时的q作为记录需要删除的节点的位置
		
		p->next = q->next;  // q的next节点即需要删除的位置的下一个节点,
		                    // 把这个地址值复给p->next,即把p节点删除
		
		p=p->next; //前面的处理完了之后,移动到这个位置开始报数(从1开始)
		
		free(q); //释放q节点,for 循环的下一个循环接着用
		
	}
	
	printf("%d\n",p->data);
	free(p); //释放最后只剩下一个节点的内存
}

假设n值为5,图解如下(注下图参考链接2

在这里插入图片描述

5 参考链接

  1. https://blog.csdn.net/tyh18226568070/article/details/79827118
  2. https://www.jianshu.com/p/6ee5c7b21333
版权声明:本文为Codeliang666原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Codeliang666/article/details/104486834