目录:
1.题目要求:2.C语言代码:3.运行结果:1.题目要求:
《数据结构与算法分析-C语言描述》[3. 10]
Josephus 问题是下面的游戏: N个人从1 到N编号,围坐成一个圆圈。从1号开始传递一个热土豆。经过M次传递后拿着热土豆的人被清除离座,围坐的圆圈缩紧,由坐在被清除的人后面的人拿起热土豆继续进行游戏。最后剩下的人取胜。因此,如果M=0和N=5,则依次清除后,5号获胜。如果M=1和N=5,那么被清除的人的顺序是2, 4,1, 5。
2.C语言代码:
文件1:源文件
#include"list.h"#define N 7#define M 2/*define后面不可以加分号啊*/int main(){List headNode = CreateNode();List endNode = headNode;if (M > 0){int i;for (i = 1; i <= N; i++){/*填充N个数[1、2、3......]*/endNode = Insert(i, headNode, endNode);}endNode->next = headNode->next;/*将链表变成单向循环链表,之后free头结点*/Position P = headNode->next;/*热土豆*/free(headNode);while (P->next != P){/*至少有俩的时候*/Position delNode;/*删除点的指针*/for (i = 1; i <= M - 1; i++){/*找到本轮清除点的前一个点*/P = P->next;}delNode = P->next;/*定位删除点*/P->next = P->next->next;/*将删除点前后粘在一起*/P = P->next;/*热土豆放在删除点的下一点*/free(delNode);}printf("%d个人传热土豆,每次传递%d次:\n\n 最后%d号获胜\n\n",N,M,P->num);}else if(M == 0){printf("%d个人传热土豆,每次传递%d次:\n\n 最后%d号获胜\n\n",N,M,N);}return 0;}
文件2:list.h
#ifndef _LIST_H#include<stdio.h>#include<stdlib.h>struct Node;typedef struct Node *PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;typedef short int ElementType;Position CreateNode();Position Insert(ElementType num, List L, Position P);#endif/*_LIST_H*/struct Node{ElementType num;Position next;};Position CreateNode(){/*返回创建节点指针*/Position P = (Position)malloc(sizeof(struct Node));if (!P){fprintf(stderr, "ERROR:%s", "out of space");/*错误提示*/exit(1);}P->next = NULL;return P;}Position Insert(ElementType num, List L, Position P){/*返回插入数据节点的指针*/if (!P){fprintf(stderr, "ERROR:%s", "插入结点不存在");/*错误提示*/exit(1);}Position NewP = CreateNode();NewP->num = num;NewP->next = P->next;P->next = NewP;return NewP;}