Question

一个关于约瑟夫环的算法问题

Description

设n个人围坐在一圆桌周围，依次编号为1,2,...,n，从第s个人从1开始依次报数，数到m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，…，如此反复直到所有的人全部出列为止。对于任意给定的n,s和m，输出按出列次序得到的n个人员的序列。（数据结构问题，请分别用顺序表和链表解决此问题，并自编多组数据测试）

Input

人数n、第一个开始者的编号s以及报数出列编号m

Output

出列者的编号序列

Sample Input

8 1 4

Sample Output

4,8,5,2,1,3,7,6

Source
wangyongliang

我的代码OJ总是说不过，请各位大虾帮我看看哪出问题了谢谢
#include<stdio.h>
#include<iostream>
#include<malloc.h>

using namespace std;

typedef struct node
{
struct node *next;
long long data;
}NODE;

NODE *create(long long n)
{
NODE *p;
p = (NODE *) malloc (sizeof(NODE));
p->data = 1;
NODE *q = p;
for(long long i = 2;i<=n;i++)
{
q->next = (NODE *) malloc (sizeof(NODE));
q = q->next;
q->data = i;
}
q->next = p;
return p;
}

NODE *DO(NODE *p,long long n,long long s,long long m)
{
for(long long i = 1;i< n + s-1;i++)
{
p = p->next;
}
for(;n>=1;n--)
{
if(n == 1)
printf("%d",p->data);
else
{
for(long long i = 1;i<m;i++)
{
p = p->next;
}
NODE *q = p;
printf("%d ",p->next->data);
p->next = p->next->next;
}
}
return p;
}

int main()
{
long long n,s,m;
scanf("%I64d %I64d %I64d",&n,&s,&m);
NODE *p = create(n);
NODE *q = DO(p,n,s,m);
return 0;
}

Answer 1

约瑟夫问题：
#include<iostream.h>
struct Node
{
int data;
Node *pNext;
};

void main()
{
int n,k,m,i;
Node *p,*q,*head;
cout<<"输入n的值:";
cin>>n;
cout<<"输入起始报数人号码k的值:";
cin>>k;
cout<<"输入 数到m出列的m的值:";
cin>>m;
head=(Node*)new Node; //确定头结点
p=head;
for(i=1;i<=n-1;i++) //赋初值
{
p->data=i;
p->pNext=(Node*)new Node; //为下一个新建内存
p=p->pNext;
}
p->data=n; //最后一个单独处理
p->pNext=head; //指向头，形成循环链表
p=head;

while(p->data!=(p->pNext)->data) //p->data==(p->pNext)->data表示只剩下一个结点的
{
while(p->data !=k) //寻找编号为k的结点
p=p->pNext;
if(m==1)
{
for(i=1;i<=n;i++)
{
cout<<p->data<<'\t' ;
p=p->pNext ;
}
cout<<'\n';
return;
}
else
for(i=1;i<m-1;i++) //开始报数
{p=p->pNext;} //找到报m-1的结点

q=p->pNext; //q为报m的结点
cout<<q->data<<"\t"; //输出报m的结点的值
k=(q->pNext)->data; //k为下一个报数的起点
p->pNext=q->pNext; //删除报m的结点
}
cout<<p->data<<'\n'; //输出最后一个结点的值
}