前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >圆圈中最后剩下的数字

圆圈中最后剩下的数字

作者头像
猿人谷
发布2018-01-17 09:52:16
7030
发布2018-01-17 09:52:16
举报
文章被收录于专栏:猿人谷猿人谷

题目:0,1,...,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

这就是有名的约瑟夫(Josephuse)环问题。可以用环形链表模拟圆圈的经典解法。

分析:用模板库中的std::list来模拟一个环形链表。由于std::list本身不是一个环形结构,因此每当迭代器扫描到链表末尾的时候,要记得把迭代器移到链表的头部,这样就相当于按照顺序在一个圆圈里遍历了。

这种思路的代码如下:

代码语言:javascript
复制
int LastRemaining(unsigned int n, unsigned int m)
{
    if(n < 1 || m < 1)
        return -1;
    
    unsigned int i = 0;
    
    list<int> numbers;
    for(i = 0; i < n; ++i)
        numbers.push_back(i);
    list<int>::iterator current = numbers.begin();
    while(numbers.size() > 1)
    {
        for(int i = 1; i < m; ++i)
        {
            current++;
            if(current == numbers.end())
                current = numbers.begin();
        }
        
        list<int>::iterator next = ++current;
        if(next == numbers.end())
            next = numbers.begin();
        
        --current;
        numbers.erase(current);
        current = next;
    }
    
    return *(current);
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2014-04-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档