josephus_seqlist.cpp

回顾基础

//【例2.1】使用顺序表求解约瑟夫环问题。

#include "SeqList.h"                                       //顺序表类
   
void josephus_remove(int number, int start, int distance)  //求解约瑟夫环
{                                                          //参数指定环长度、起始位置、计数
    SeqList<char> jose(number);                            //创建顺序表，长度为number
    int i=0;
    for (i=0; i<number; i++)
        jose.insert('A'+i);                                //在顺序表最后添加元素
    cout<<"约瑟夫环("<<number<<","<<start<<","<<distance<<")，"<<jose;    //输出约瑟夫环中所有元素
    cout<<"查找E："<<jose.indexOf('E')<<endl;

    i = start;                                             //计数起始位置
    while (jose.length()>1)                                //多于一个元素时循环 
    {
        i = (i+distance-1) % jose.length();                //计数时按循环规律变化
        char old;
        if (jose.remove(i, old))
            cout<<"删除"<<old<<"，";                       //删除指定位置元素
        cout<<jose;
    }
    cout<<"被赦免者是"<<jose.get(0)<<"\n";                 //若get(i)参数i指定元素序号无效则抛出异常
}

void josephus_set(int number, int start, int distance)     //求解约瑟夫环
{                                                          //参数指定环长度、起始位置、计数
    SeqList<char> jose(number);                            //创建顺序表，长度为number
    int i=0;
    for (i=0; i<number; i++) 
        jose.insert('A'+i);                                //在顺序表最后添加元素
    cout<<"约瑟夫环("<<number<<","<<start<<","<<distance<<")，"<<jose;
//   jose.print();                                          //输出约瑟夫环中所有元素

    i = start-1;                                           //计数起始位置
    int count = jose.length();
    while (count>1)                                        //多于一个对象时循环
    {
        int j=0;
        while (j<distance) 
        {
            i = (i+1) % jose.length();                     //计数时按循环规律变化
            if (jose.get(i)!=' ')
                j++;
        }
        cout<<"删除"<<jose.get(i)<<"，";
        jose.set(i, ' ');                                  //以空格表示该位置元素为空
        count--;
        cout<<jose;//.print();
    }

    i=0;                                                   //寻找最后一个元素
    while (i<jose.length() && jose.get(i)==' ')
        i++;
    cout<<"被赦免者是"<<jose.get(i)<<endl;
}

int main()
{
    josephus_remove(5,0,2);
//    josephus_set(5,0,2);
    return 0;
}

/*
    josephus_remove(5,0,2);
程序运行结果如下：
约瑟夫环(5,0,2)， (A, B, C, D, E) 
删除B， (A, C, D, E)
删除D， (A, C, E)
删除A， (C, E)
删除E， (C)
被赦免者是C 


     josephus_set(5,0,2);
程序运行结果如下：
约瑟夫环(5,0,2)，list: (A, B, C, D, E) 
删除B，list: (A,  , C, D, E)
删除D，list: (A,  , C,  , E)
删除A，list: ( ,  , C,  , E)
删除E，list: ( ,  , C,  ,  )
被赦免者是C 


*/