动态规划解决约瑟夫环问题

题目: 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号0,1,2,3…n-1分别表示)围坐在一张圆桌周围。从编号为0的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,求最后一个出列的人。

1.经典解法

可以用链表来模拟约瑟夫环,每次在链表中删除第m个节点,然后不断,直至链表中只剩下一个节点。最后一个这个节点就是我们要求的节点。 注意:当迭代器扫描到链表末尾时,将迭代器移至链表头。

int lastRemaining(unsigned int n, unsigned int m){
    if(n<1||m<1)
        return -1;

    list<int> numbers;          //单链表模拟约瑟夫环(Josephus Ring)
    for(int i=0;i<n;++i)
        numbers.push_back(i);
    list<int>::iterator cur=numbers.begin(); //从第一个节点开始报数
    while(numbers.size()!=1){                //循环迭代至约瑟夫环只剩最后一个元素
        for(int i=0;i<m-1;++i){              //迭代m-1次找到需要移出环的元素
            ++cur;
            if(cur==numbers.end())           //迭代器扫描到链表末尾时,将迭代器移至链表头
                cur=numbers.begin();
        }
        list<int>::iterator next=++cur;
        if(next==numbers.end())
            next=numbers.begin();
        --cur;
        numbers.erase(cur);
        cur=next;
    }
    return *cur;
}

分析:经典解法易于理解,实现简单。但是重复遍历降低效率,没删除一个元素需要m步移动,对n个元素,时间复杂度为O(mn)。

2.动态规划求解

动态规划重点是要确定状态和状态转移方程。状态就是确定问题的解的表达式,状态转移方程就是上一阶段问题的解推出当前阶段问题解的递推式。

针对约瑟夫环问题,n个元素的环可以定义为f(n,m),m表示每次移动的步数。则状态就是f(n,m)。那么对于n-1个元素的环,其最后一个被移除的元素就是f(n-1,m)。当环中只有一个元素时,f(1,m)=0。那么这里的重点和难点就是找出f(n,m)和f(n-1,m)之间的关系。也就是状态转移方程。

那么看如下分析: (1)第一个被删除的数为 (m - 1) % n,设下标为k。 (2)假设第二轮的开始元素下标为k+1,那么这n - 1个数构成的约瑟夫环为k + 1, k + 2, k +3, …..,k - 3, k - 2,k-1。做一个简单的映射。 k+1 —> 0 k+2 —> 1 … n-1 —> n-k-2 0 —> n-k-1 … k-1 —>n-2 可见,映射关系为p(x)=(x-k-1)%n,那么其从右到左的映射关系是p−1(x)=(x+k+1)%np^{-1}(x)=(x+k+1)\%n。因为右边最后出列的元素下标是f(n-1,m),映射到左边就是p−1(f(n−1,m))=(f(n−1,m)+k+1)%np^{-1}(f(n-1,m))=(f(n-1,m)+k+1)\%n,又因为k=(m-1)%n,代入上面式中得: p−1(f(n−1,m))=(f(n−1,m)+k+1)%n=(f(n−1,m)+m)%np^{-1}(f(n-1,m))=(f(n-1,m)+k+1)\%n=(f(n-1,m)+m)\%n,即:

f(n,m)={0(f(n−1,m)+m)%nn=1n>1

f(n,m)=\begin{cases} 0&\text{n=1}\\ (f(n-1,m)+m)\%n & \text{n>1}\end{cases}

有了状态转移方程,我们可以使用迭代或者递归来完成问题求解。建议迭代,以免对不同阶段的问题重复求解。

下面以迭代方式实现:

int lastRemainingDP(unsigned int n, unsigned int m){
    if(n<1||m<1)
        return -1;

    int last=0; //n=1,最后移出环的元素
    for(int i=2;i<=n;++i)
        last=(last+m)%i;
    return last;
}

参考文献

[1]剑指Offer.何海涛.电子工业出版社. [2]解题笔记(10)——约瑟夫环问题.

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

入门 | 一文介绍机器学习中基本的数学符号

选自Machine Learning Mastery 作者:Jason Brownlee 机器之心编译 参与:Edison Ke、黄小天 本文介绍了机器学习中的...

3579
来自专栏ml

错排公式

错排公式 百科名片 pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题: n个有...

4079
来自专栏CDA数据分析师

开工大吉:几个让你月薪3万+的excel神技能

来源:运营圈信息流广告 职场中经常会用到哪些函数? IF函数、SUMIF函数、VLOOKUP函数、SUMPRODUCT函数...... 小编总结了8个在工作中常...

3946
来自专栏数据结构与算法

BZOJ3687: 简单题(dp+bitset)

Description 小呆开始研究集合论了,他提出了关于一个数集四个问题: 1.子集的异或和的算术和。 2.子集的异或和的异或和。 3.子集的算术和的算术和...

3496
来自专栏java一日一条

我是如何击败Java自带排序算法的

Java 8 对自带的排序算法进行了很好的优化。对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个...

1141
来自专栏Duncan's Blog

回溯法笔记

为了应用回溯法,所要求的解必须能表示成一个n-元组(x1,x2,…,xn),其中xi是取自某个有穷集Si。通常,所求解的问题需要求取一个使某一规范函数P(x1,...

1072
来自专栏自然语言处理

程序员眼中的统计学5

定义:若具有性质A的事件有m个,具有性质B的事件有n个,则具有性质A或性质B的事件有m+n个。

853
来自专栏落影的专栏

程序员进阶之算法练习(十五)

前言 有朋友推荐一个新的算法练习网站leetcode,说北美的公司招人都是400题起步,国内公司招聘也经常用到,上海的尤其多。 很有意思,可以花点时间做做le...

3965
来自专栏大数据

概率数据结构简介

在处理大型的数据集时,我们常常进行一些简单的检查,如稀有项(Unique items)的数量、最常见的项,以及数据集中是否存在某些指定的项。通常的做法是使用某种...

5226
来自专栏逸鹏说道

码农眼中的数学之~数学基础

1维直线、2维平面(长宽)、3维空间(长宽高 | xyz轴)、4维时空(xyz轴+时间轴)

1273

扫码关注云+社区

领取腾讯云代金券