Question

C++利用顺序表实现约瑟夫问题

约瑟夫问题：
n个人(编号从1到n)围成一圈, 从第k(1≤k≤n)个人开始依次报数(从1开始), 第m个被杀掉, 然后再由下一个人重新报数, 直到所有人被杀, 依次显示被杀掉的人的编号。
实验: 利用顺序表实现约瑟夫问题。
要求: 输入不同nmk值，输出被杀人员编号，使用c++语言用顺序表实现功能，最好有注释。
急求，谢谢！
利用单链表或循环链表也可以，急求！！！

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励10（财富值+成长值）+提问者悬赏30（财富值+成长值）

Answer 1

#include<iostream>
#define MaxSize 50
#define ElemType int
using namespace std;
typedef struct //定义顺序表结构体类型
{
ElemType data[MaxSize]; //存放每个人的编号
int length;
}SqList;

void CreateList(SqList&L,int n) //创建顺序表
{
int i;
for(i=0;i<n;i++)
L.data[i]=i+1; //编号为1~n L.Data[]
L.length=n; //共n个人
}

void DispList(SqList L) //显示顺序表中的记录
{
cout<<"\n\n 幸存者的位置 :\n";
for(int i=0;i<L.length;i++)
cout<<L.data[i]<<"\t";
cout<<endl;
}
int ListDelete(SqList&L,int i,ElemType &e) //从顺序表中删除所选定的人的编号
{
int j;
if(i<1||i>L.length)
return 0;
i--;
e=L.data[i];
for(j=i;j<L.length-1;i++)
L.data[j]=L.data[j+1];
L.length--;
return 1;
}
void Josephus(SqList&L,int m,int k) //约瑟夫问题实现过程
{
ElemType
int i,n=0; //用n记录下标，下标从0开始
cout<<"被杀者的位置 ：\n";
for(i=1;i<=k;i++) //将k个人抛入大海
{
for(int j=1;j<m;j++) //每报数到m时，此人被扔入大海
{
n=n%L.length;
n++;
}
ListDelete(L,n+1,e); //位置=下标+1
cout<<e<<'\t';
}

}
int main(
{
SqList sql;
CreateList(sql,30); //将30人的编号存入顺序表
Josephus(sql,9,15); //每数到第9个人就将他扔入大海，如此循环进
//行，直到仅余15个人为止
DispList(sql); //输出剩余的15人的位置
return 0;
}