约瑟夫环c语⾔程序完整版，约瑟夫环的C语⾔实现
引⼦
据说著名犹太历史学家Josephus有过以下的故事：在罗马⼈占领乔塔帕特后，39 个犹太⼈与Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被敌⼈抓到，于是决定了⼀个⾃杀⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀，然后再由下⼀个重新报数，直到所有⼈都⾃杀⾝亡为⽌。然⽽Josephus和他的朋友并不想遵从。⾸先从⼀个⼈开始，越过k-2个⼈(因为第⼀个⼈已经被越过)，并杀掉第k个⼈。接着，再越过k-1个⼈，并杀掉第k个⼈。这个过程沿着圆圈⼀直进⾏，直到最终只剩下⼀个⼈留下，这个⼈就可以继续活着。问题是，给定了和，⼀开始要站在什么地⽅才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在第16个与第31个位置，于是逃过了这场死亡游戏。
进⼊正题
约瑟夫环问题，在计算机界是⼀个经典的循环链表问题，题意是：已知 n 个⼈(分别⽤编号 1，2，3，…，n 表⽰)围坐在⼀张圆桌周围，从编号为 k 的⼈开始顺时针报数，数到 m 的那个⼈出列；他的下⼀个⼈⼜从 1 开始，还是顺时针开始报数，数到 m 的那个⼈⼜出列；依次重复下去，直到圆桌上剩余⼀个⼈。
如图所⽰，假设此时圆周周围有 5 个⼈，要求从编号为 3 的⼈开始顺时针数数，数到 2 的那个⼈出列：
一个完整的c语言程序出列顺序依次为：
编号为 3 的⼈开始数 1，然后 4 数 2，所以 4 先出列；
4 出列后，从
5 开始数 1，1 数 2，所以 1 出列；
1 出列后，从
2 开始数 1，
3 数 2，所以 3 出列；
3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
最后只剩下 5 ⾃⼰，所以 5 胜出。
⼿敲代码实现如下
#include "stdlib.h"
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct Node{
ElemType data;
typedef struct Node * LinkList;
/*
1、初始化单向循环链表(带⼊节点总数)
*/
Status initJosehuList(LinkList *list, int count){ LinkList tempNode,lastNode = NULL;
int i = 1;
while (i <= count) {
//创建⼀个节点
tempNode = malloc(sizeof(Node));
if (tempNode == NULL) {
return ERROR;
}
tempNode->data = i;
if (*list == NULL) {
//⾸元节点插⼊
*list = tempNode;
tempNode->next = tempNode;
}
else {
/
/尾节点插⼊
tempNode->next = lastNode->next;
lastNode->next = tempNode;
}
//记录尾节点
lastNode = tempNode;
i++;
}
return OK;
}
/*
2、遍历链表
void ListTraverse(LinkList list){
printf("遍历链表：");
LinkList p = list;
if (!p) {
printf("这是⼀个空链表");
}
else {
do {
printf("%d ",p->data);
p = p->next;
} while (p != list);
}
printf("\n");
}
int JosehuMethod(LinkList *list,int startIndex,int num){
if (*list == NULL || startIndex < 1 || num < 1) {
return 0;
}
//到最后⾯的那个⼈，因为他是index为1时第⼀个数数的⼈的前⼀个⼈LinkList preNode;
for (preNode = *list; preNode->next != *list; preNode = preNode->next); //记录要出列的⼈
LinkList locaNode;
/
/第⼏次出列
int serialNum = 1;
//记录报到⼏号了
int newNum = 1;
//判断是否只留下⼀个⼈了
while ((*list)->next != *list) {
//1、先到开始报数的⼈
if (startIndex > 1) {
preNode = preNode->next;
}
//2、到后，让他开始报数
if (newNum < num) {
newNum ++;
preNode = preNode->next;
}
else {
//3、到要出列的⼈，将他出列
newNum = 1;
locaNode = preNode->next;
//判断是否⾸元节点，要特殊处理下
if (locaNode == *list) {
*list = locaNode->next;
}
preNode->next = locaNode->next;
printf("第%d个出列的⼈是：%d\n",serialNum,locaNode->data); serialNum ++;
free(locaNode);
}
}
printf("最后留下的⼈是：%d\n",(*list)->data);
return (*list)->data;
}
int main(int argc, const char * argv[]){
//初始化
LinkList list;
int count;
printf("输⼊队列数量：");
scanf("%d",&count);
initJosehuList(&list, count);
//遍历数据
ListTraverse(list);
printf("输⼊开始报数的位置：");
scanf("%d",&startIndex);
printf("输⼊出列的报数序号：");
scanf("%d",&num);
/
/执⾏约瑟夫⽅法
JosehuMethod(&list, startIndex, num); printf("\n");
return 0;
}
复制代码
输⼊效果如下

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。