约瑟夫环来源于犹太历史学家Josephus所讲述的一个故事。罗马人占领某地后，39个犹太人和Josephus以及他的朋友躲到了一个洞中。
他们决定围成一个圈，逐个自杀也不要被罗马人抓住。自杀规则是从第一个人开始，数到3的人就自杀，然后由下一个人重新报数。
Josephus和他的朋友不想自杀，他们自己选择了两个位置，活到了最后。

将这个问题抽象以后，在LeetCode上有这么一道题圆圈中最后剩下的数字
在我做笔试的经历中，出现了题目的变种，变化之处在于删除的数字间隔是变化的，随着删除个数而增长。

求解思路

循环数组（链表）

题中是一个圈，所以启发我们用一个循环数组或链表来解决这个问题。由于数组需要一整块的内存且删除操作不如链表，本文选则STL库容器list来实现
一个环形链表。只需要迭代器每次扫描到链表末尾时，将其移动到链表头部即可。

需要注意的点：

1) 扫描链表时，一定要注意走到list.end()要转移到begin()
2) list.erase()删除操作，迭代器移动到被删除节点的下一个位置，所以重点关注next节点
是否是尾部迭代器。

#include <list>

using namespace std;

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

    usigned int i = 0;
    list<int> r_list;

    for(int i = 0; i < n; ++i)
    {
        r_list.push_back(i);
    }

    list<int>::iterator it = list.begin();
    while(r_list.size() > 1)
    {
        for(int i = 1; i < m; ++i)
        {
            it++;
            if(it == r_list.end())
            {
                //m = m+1; 如果m是变化的，可以在这里修改m的数值
                it = r_list.begin();
            }
        }

        auto next = ++it;
        if(next == r_list.end())
        {
            next = r_list.begin();
        }

        it--;
        r_list.erase(it);
        it = next;
    }
    return *it;
}

数学思路

我们可以这样考虑

1）剩两个元素时，数数从0开始，是0->1->0，0这个位置会被删除，1保留下来；

2）剩下三个元素时，0->1->2，0->1->0，2和0被删掉，1保留下来；

3) 剩下四个元素，0->1->2，3->0->1，3->0->3，删掉顺序是2，1，3，0保留下来；

4) 剩下五个元素，…，删除顺序是2，0，4，1，3保留下来

乍一看是看不出来规律，但是我们动手算的过程中会发现：

假设剩余n个元素(2 <= n)，m个间隔，最终保留的下标是res1 = f(n,m)。
假设对于n+1个数，位置为res2 = f(n+1,m)的数保留；
那么在删除一个元素的过程中，res2的位置和res1有什么关系？

此时思路已经相对明显了，我们来尝试进行倒推。
f(2,3) = 1;
f(3,3) = (f(2,3) + m) % 3; //
f(4,3) = (f(3,3) + m) % 4;
…
f(n,m) = (f(n-1,m) + m) % n

人数	位置	间隔
2	1	3
3	1	3
4	0	3
5	3	3

My Personal Blog

约瑟夫环问题

求解思路

循环数组（链表）

数学思路