专栏首页祥的专栏[DS]链表之约瑟夫环(Josephus)问题

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

原创文章

原文链接:https://blog.csdn.net/humanking7/article/details/80786920


  • 算法问题
  • 代码
  • 测试结果
  • 分析

算法问题

约瑟夫环(Josephus)问题: 有N个人做成一圈,编号为1至N。从编号为1的人开始传递马铃薯。 M次传递后,持有马铃薯的人退出游戏,圈缩小,然后游戏从退出人后面的人开始,继续进行。 最终留下来的人获胜。 eg:

  • 如果 M = 0 且 N = 5,那么参加游戏的人依次退出,5号获胜。
  • 如果 M = 1 且 N = 5, 那么退出顺序就是 2、4、1、5

用链表实现,依次运用了3种算法,算法效率依次变高。

本例程主要是针对链表的运用,其题目来源于《数据结构与算法分析:C++描述》中的

题3.6,针对于约瑟夫环问题,应该有更好的简单解法,针对于链表的操作,在下认为alg3()应该是最佳选择了,期待算法大神指导。

代码

//算法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;

}

测试结果

人数N

传递次数M

离场顺序

算法1CNT

算法2CNT

算法3CNT

5

0

1,2,3,4,5

0

0

0

5

1

2,4,1,5,3

5

4

4

5

2

3,1,5,2,4

10

6

5

5

3

4,3,5,2,1

15

7

4

5

4

5,1,3,4,2

20

5

2

5

5

1,3,2,5,4

25

4

3

5

6

2,5,1,3,4

30

3

3

5

7

3,2,5,4,1

35

7

5

5

8

4,5,3,1,2

40

5

3

5

9

5,2,3,1,4

45

6

3

分析

  • 算法1:中规中矩,最差的实现,随着传递次数m的增加,迭代器移动次数增加,算法时间复杂度O(mn)
  • 算法2:节省的部分在于多余的传递部分圈数(当人数numLeft少于传递次数时m时,每次踢人会多传递nLoop = m/numLeft圈,也就是多传递[nLoop*numLeft]次,实际只需要传递mPrime = m%numLeft次),这样会节省相当多的时间尤其是m比较大的时候,算法时间复杂度在下不会求--!,大概是…..
  • 算法3:相较于算法2,最大的优势在于运用了双向链表这一优势,当要迭代器移动的次数( mPrime )大于当前人数的一半时,就反向移动(numLeft - mPrime)次,算法时间复杂度大概是…..

对这些算法进行了简单测试,测试结果如下,希望能从里面推断出算法时间复杂度的一丝端倪,不过还是没有搞明白,希望有大神解答一下。

人数N

传递次数M

算法1CNT

算法2CNT

算法3CNT

7000

1

7000

6999

6999

7000

3500

24,500,000

14,422,282

7,519,652

7000

5500

38,500,000

13,616,600

4,565,344

7000

6999

48,993,000

8,705,026

5,569,974

7000

9000

63,000,000

12,370,413

7,211,057

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3137 栈练习1

    3137 栈练习1  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descriptio...

    attack
  • extern "c"(2)

    源文件为*.c,__cplusplus没有被定义,extern "C" {}这时没有生效对于C他看到只是extern intadd(int, int);add函...

    随心助手
  • 【PAT乙级】素数对猜想

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【PAT乙级】数素数

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • c++STL之常用算术生成算法

    绝命生
  • Bio、Nio、Aio的用法系列之BIO(一)

    上面我们开始监听8888端口,启动这个main后,肯定阻塞到accept,等待客户端发送过来消息

    用户1257393
  • 最短路径—弄懂Dijkstra(迪杰斯特拉)算法

    对于 dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解 bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法...

    bigsai

扫码关注云+社区

领取腾讯云代金券