[DS]链表之约瑟夫环(Josephus)问题

//算法1
#include <iostream>
#include <list>
using namespace std;

int alg1(int n, int m);
int alg2(int n, int m);
int alg3(int n, int m);

int main()
{
    //Initialization
    int n, m;
    char str[] = "Josephus问题：\n有N个人做成一圈，编号为1至N。从编号为1的人开始传递马铃薯。\nM次传递后，持有马铃薯的人退出游戏，圈缩小，然后游戏从退出人后面的人开始，继续进行。最终留下来的人获胜。\nEg：\n 如果 M = 0 且 N = 5，那么参加游戏的人依次退出，5号获胜。\n如果 M = 1 且 N = 5， 那么退出顺序就是 2、4、1、5";
    cout << str << endl;
    cout << "enter N (# of people) & M (# of passes before elimination):";
    cin >> n >> m;

    int cnt1, cnt2, cnt3;
    cnt1 = alg1(n, m);
    cnt2 = alg2(n, m);
    cnt3 = alg3(n, m);

    cout << "算法1 cnt: " << cnt1 << endl;
    cout << "算法2 cnt: " << cnt2 << endl;
    cout << "算法3 cnt: " << cnt3 << endl;

    return 0;
}

//-----------------------------------
//--------      alg1         --------
//-----------------------------------
int alg1(int n, int m)
{
    int i, j,run_cnt;   
    list <int> L;
    list<int>::iterator iter;
    run_cnt = 0;
    cout << "算法1:" << endl;
    //获得人数圈
    for (i = 1; i <= n; i++)
    {
        L.push_back(i);
    }
    iter = L.begin();


    //传递马铃薯
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            iter++;
            run_cnt++;//迭代器移动
            if (iter == L.end())
                iter = L.begin();
        }

        cout << "\tdel: " << *iter << endl;
        iter = L.erase(iter);
        if (iter == L.end())
            iter = L.begin();
    }
    cout << endl;
    cout << "\t迭代器移动次数: " << run_cnt << endl << endl;

    return run_cnt;
}

//-----------------------------------
//--------      alg2         --------
//-----------------------------------
int alg2(int n, int m)
{//只运用了单向链表
    int i, j, run_cnt, numLeft,mPrime;
    list <int> L;
    list<int>::iterator iter;
    numLeft = n;//剩余人数
    run_cnt = 0;
    cout << "算法2:" << endl;
    //获得人数圈
    for (i = 1; i <= n; i++)
    {
        L.push_back(i);
    }
    iter = L.begin();


    //传递马铃薯
    for (i = 0; i < n; i++)
    {
        mPrime = m % numLeft;//传递次数是人员人数的余数，这样迭代器可以少移动
        for (j = 0; j < mPrime; j++)
        {
            iter++;
            run_cnt++;//迭代器移动
            if (iter == L.end())
                iter = L.begin();
        }

        cout << "\tdel: " << *iter << endl;
        iter = L.erase(iter);
        numLeft = L.size();//由于删除人员，获取现在人数
        if (iter == L.end())
            iter = L.begin();
    }
    cout << endl;
    cout << "\t迭代器移动次数: " << run_cnt << endl << endl;

    return run_cnt;
}

//-----------------------------------
//--------      alg3         --------
//-----------------------------------
int alg3(int n, int m)
{//体现出双向链表的强大之处
    int i, j, run_cnt, numLeft, mPrime;
    list <int> L;
    list<int>::iterator iter;
    numLeft = n;//剩余人数
    run_cnt = 0;
    cout << "算法3:" << endl;
    //获得人数圈
    for (i = 1; i <= n; i++)
    {
        L.push_back(i);
    }
    iter = L.begin();


    //传递马铃薯
    for (i = 0; i < n; i++)
    {
        mPrime = m % numLeft;//传递次数是人员人数的余数，这样迭代器可以少移动


        if (mPrime <= numLeft / 2) //正向移动迭代器
        {
            cout << "forward";
            for (j = 0; j < mPrime; j++)
            {
                iter++;
                run_cnt++;//迭代器移动
                if (iter == L.end())
                    iter = L.begin();
            }
        }
        else//反向移动迭代器
        {
            cout << "backward";
            for (j = 0; j < (numLeft - mPrime); j++)
            {
                run_cnt++;//迭代器移动
                if (iter == L.begin())
                    iter = --L.end();
                else
                    iter--;
            }
        }

        cout << "\tdel: " << *iter << endl;
        iter = L.erase(iter);
        numLeft = L.size();//由于删除人员，获取现在人数
        if (iter == L.end())
            iter = L.begin();
    }
    cout << endl;
    cout << "\t迭代器移动次数: " << run_cnt << endl << endl;

    return run_cnt;

}