今天复习OJ上的数据结构题,有一题用循环链表解决约瑟夫环,不想写循环链表了,然后百度找了些资料总结了下,如下:

假设有10个人做成一圈,报数1 2 3.报到3的人自己退出,过程如下:

初始状态10个人 1 2 3 4 5 6 7 8 9 10

第一次 10个人 报到3退出
状态:4 5 6 7 8 9 10 1 2

第二次 9个人 报到6退出
状态:7 8 9 10 1 2 4 5

第三次 8个人 报到9退出
状态 10 1 2 4 5 7 8 9

第四次 7个人 报到2掏出
状态 4 5 7 8 9 10 1
…………

直到报到 1个人,结束

分析一下过程:
每次那个人报完后,总人数少1,然后报完的人的下一个就是头。
可以有如下递推等式。

f(n,m) = (f(n-1,m)+m) % n

解释:
f(n,m)意思是 当总人数是n个,报到m的退出。
f(n-1,m)意思是 总人数n-1,报到m的退出。

f(n-1,m)+m 意思就是n-1个人,报到m的那个那个人退出之后,往后报再报m个,就是n个人的结果了。

%n是怕下标越界。

代码如下:

#include <iostream>
using namespace std;

int solve(int n, int m)
{
    if (n == 0)
    {
        return 0;
    }
    return (solve(n - 1, m) + m) % n;
}

int main()
{
    int n;
    int m;
    cin >> n >> m;
    cout << solve(n, m) + 1;
    return 0;
}
最后修改:2019 年 04 月 15 日 11 : 01 PM
如果觉得我的文章对你有用,请随意赞赏