Question

c++怎么实现约瑟夫问题?

老师布置了一个c++题目，只用数组实现约瑟夫问题？我该怎么实现呢？

Answer 1

数组实现约瑟夫问题的思想就是建立一个标记数组，未删除的人标记为0，否则为1，然后采用循环数组，对下标求余，具体实现如下，其中N为总人数，D为每次向下数的人数。
#include <iostream>
using namespace std;
void main(){
int N=40;//假设40个人
int a[100]={0};//最大支持100个人的标记,初始化为0
int D=6;//假设报数为6
int i=0;//循环变量
int j=-1;//当前的位置，初始化为-1，相当于一个虚拟的人
//输入我要的N和D
cout<<"请输入需要的N和D:"<<endl;
cin>>N>>D;
cout<<"结果显示如下："<<endl;
for(i=0;i<40;i++){//循环40次，所有人均出来
int sum=0;//来记录数的人数
while(sum!=D){
j=(j+1)%40;
if(a[j]==0){
sum++;
}
}
a[j]=1;
cout<<j+1<<endl;//输出删除的位置
}
//最后输出来的就是最后剩下的人了
}

Answer 2

1、约瑟夫问题：
n个人(编号从1到n)围成一圈, 从第k(1≤k≤n)个人开始依次报数(从1开始), 第m个被杀掉, 然后再由下一个人重新报数, 直到所有人被杀, 依次显示被杀掉的人的编号。

2、例程：

#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;
}

Answer 3

这个问题其实就是要考虑怎么让数组形成一个循环，就像循环链表似地！你有邮箱吗？我发到你邮箱自己看吧！