约瑟夫环问题的代码

Question

我用的vc 6.0++,表示数据结构不通，求大侠修改#include
#include<stdio.h>
#define N 100
void OutRing(int n, int quit[N]);
//数据结构设计//
typedef struct node{
int number;//每个人的编号
struct node *next;//指向下一个人的结点
}Lnode, *Linklist;
Linklist p;//设头指针p

Linklist InitRingLList(int n);
void Josephus(Linklist R, int n, int k, int quit[N]);

void main(){
int quit[N];
int n,k,m;
printf("enter :");
scanf("%d %d %d",&n,&k,&m);
p=InitRingLList(n);
Josephus(p,n,k,quit[N]);
OutRing(n,quit[N]);
}

//建立单循环链表函数与初始化//
Linklist InitRingLList(int n){ //尾插法建立//n代表总人数
Lnode *R, *p, *q;
int i;
R = new Lnode;
q = R;
for (i = 1; i < n; i++){
p = new Lnode;
q->number = i;
q->next = R;
q = p;
}
p->number = n;
p->next = R;//链表首尾相连
R = p;//R指向循环链表尾结点
return R;
}

//删除结点和保存输出顺序的函数//
void Josephus(Linklist R, int n, int k, int quit[N]){ //从编号为k的人开始报数
int i, j;
Lnode *p, *q;
p = R;
for（i = 0; i < n; i++ ）{
for (j = 1; j <= k - 1; j++)//沿链前进 k-1步
p = p->next;
q = p->next;//q为被删除结点
p->next = q->next;//删除结点
quit[i] = q->number;//保存编号
delete q;//释放空间// delete为保留字
}
}

//序列的输出函数
void OutRing(int n, int quit[N]){
int i;
for (i = 0; i < n; i++)
cout << quit[i];
}

void main(){
int n;
printf（"请输入总人数："）
scanf("%d", &n);
int k;
printf("/n请输入开始编号")
scanf("%d", &k);
int m;
printf("/n请输入报数上限")
scanf("%d", &m);

}

Answer 1

首先，这个代码输出的是，约瑟夫环到达的最后位置。输出结果是15。
//把iostream这个文件中的内容复制到这个地方。
#include<iostream>
using namespace std;
int main()
{
//定义一个常量的整形100，表示人的个数。
const int n=100;
//定义约瑟夫环的参数。
int m=30;
//定义一个数组，用于计算约瑟夫环的位置。
int a[n];

//给数组赋值，让数组的每个值就是这个元素的编号。
for(int j=0;j<n;j++)
a[j]=j+1;
//定义一个标志k，当K等于N的时候，表示到达约瑟夫环的最后位置。
int k=1;
int i=-1;
while(1)
{
for(int j=0;j<m;)
{
//不停的取数组的下一个元素。
i=(i+1)%n;
//如果这个元素没有被标记为0，说明这个位置还没有被排除，j加1，进入下一个循环
if(a[i]!=0)
j++;
}
//如果标志K等于n，说明约瑟夫环的循环到达最后一个位置，跳出While死循环。
if(k==n)
break;
//否则，把这个位置的元素设为零，标志它被排除。
a[i]=0;
//标志+1。
k++;
}
//输出约瑟夫环到达的最后一个位置。
cout<<a[i]<<endl;
return 0;
}