热度 1|
/**************************************************************************************/
//题目:用循环链表模拟约瑟夫问题,把41个人自杀的顺序编号输出。
//故事情节:
// 据说著名犹太历史学家 Josephus有过以下的故事:
//在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,
//39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,
//41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,
//然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从,
//Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,
//于是逃过了这场死亡游戏。
/***************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
/*************************************************/
/*链表声明*/
/*************************************************/
typedef int ElementType;
struct Node;
typedef struct Node* PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
ElementType Element;
Position Next;
};
/*************************************************/
/*循环链表*/
/*************************************************/
Position Circulate_LinkList(int n)
{
Position Head=(Position)malloc(sizeof(Node));
if(Head == NULL)
{
printf("动态内存分配失败,程序结束!!");
}
int i=1;
Position p,s;
p=Head;
if(n != 0)
{
while(i <= n)
{
s=(Position)malloc(sizeof(Node));
if(s == NULL)
{
printf("动态内存分配失败,程序结束!!!");
}
s->Element=i++;
p->Next=s;
p=s;
}
s->Next=Head->Next;
}
free(Head);
return s->Next;
}
/*************************************************/
/*主函数*/
/*************************************************/
int main()
{
int n=41;
int m=3;
Position Temp;
Position Point;
Point=Circulate_LinkList(n);
m %= n; // m在这里是等于3
while (Point != Point->Next ) //判断条件就是这个循环链表是不是空链表
{
for (int i = 1; i < m-1; i++)
{
Point = Point->Next ;
}
printf("%d->", Point->Next->Element );
Temp = Point->Next ; //删除第m个节点
Point->Next = Temp->Next ;
free(Temp);
Point = Point->Next ;
}
printf("%d\n", Point->Element );
return 0;
}
小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
GMT+8, 2024-3-29 16:47
Powered by Discuz! X3.4
© 2001-2023 Discuz! Team.