Question

C语言Josephus问题

有一群学生围成一圈，顺序编号，从第一个学生起，顺时针方向报数，从1报到m，凡是报到m的学生离开圈子，随着学生的不断离开，圈子越缩越小，最后剩下的学生便是 胜利者，问最后剩下的学生是原来的第几号？ 分析：首先对每一个学生赋以一个序号值作为学生离开时，将他的序号改为0作为离开的标志。

Answer 1

#define OK 1
#define ERROR 0

typedef struct {
int num;
int key;
}Elemtype;//定义链表的元素类型
typedef struct LNode {
Elemtype data;
struct LNode *next;
}LNode, *LinkList;//定义一个链表
typedef int Status ;
int m1;//定义全局变量,存储报数上限值

#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;

Status main()
{ Status CreatList_L(LinkList &L, int n);//声明函数CreatList_L
LinkList L;//初始化一个链表
Elemtype e;
int n,m2;
printf("请输入人数（n <= 30）：n = ");
scanf("%d",&n);//读取n值
if(n < 0 || n > 30) return ERROR;//判断n值正确与否
else
printf("请输入报数上限值：m1 = ");
scanf("%d",&m1);//读取报数上限值
if( m1 <= 0) return ERROR;
else printf("请输入m的初始值(<=%d)：",m1);
scanf("%d",&m2);//读取m的初始值
while( m2 <= 0 || m2 > m1) {
printf("初始值有误，请重新输入");
scanf("%d",&m2);
}//判断初始值是否正确
CreatList_L(L,n);//调用函数CreatList_L
LinkList p = L;
//开始报数,并将符合规则的出列
for( int i = 1; i <= n; i++){
int j = 1;
if(m2 == 1){//当m2值为1时执行以下语句
LinkList q = p;
while(p->next != q) {
p = p->next;//寻找要删除结点的直接前驱
}//while
p->next = q->next;
p = p->next;
e = q->data; free(q);//删除结点并用e返回其值
printf("%d ",e.num);
m2 = e.key;//将密码付给m2
}
else{//当m2值不为1时执行
while (p->next != p && j < m2-1){
p = p->next; ++j;
}//寻找要删除结点的直接前驱
if ( p->next == p) { //判断是否为最后一个结点
printf("%d ",p->data.num);
free(p);
}
else{
LinkList q = p->next;
p->next = q->next;
p = p->next;
e = q->data; free(q);//删除结点并用e返回其值
printf("%d ",e.num);
m2 = e.key; //将密码付给m2
}
}
}//for
return OK;
}//main

Status CreatList_L(LinkList &L, int n){
LinkList p,q;
L = (LinkList) malloc(sizeof (LNode));//初始化一个带头结点的链表
q = L;
for(int i = 1; i <= n; ++i){
p = (LinkList) malloc(sizeof (LNode));
p->data.num = i;
printf("请输入编号为%d的人的密码(<= %d)：",i,m1);
scanf("%d",&p->data.key);//读取每人的密码
while(p->data.key <= 0 || p->data.key > m1){
printf("密码有误，请重新输入\n");
scanf("%d",&p->data.key);
}//判断密码是否正确
q->next = p; q = p;
}//for
q->next = L->next;//将单链表变为循环链表
//释放头结点
p = L;
L = L->next;
free(p);
return OK;
}//CreatList_L

————不知道这一个能不能满足你的要求？可能要改一下