约瑟夫环问题的动态规划解法

约瑟夫环问题

已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为0的人开始报数,数到k的那个人出列;他的下一个人又从1开始报数,数到k的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列,求出最后一个出列的人。

链表模拟解法

今天上数据结构课,讲到约瑟夫环问题,手动实现的方法不再赘述。对于STL,可以直接只用list,使用迭代器实现查找和删除操作,但是这种方法的复杂度是O(N×K)的,非常耗时

动态规划解法

设dp[i]为当前还剩i个人,重新从[0, i)编号后,出列第k个人后,下一个开始报数的人的编号。容易发现dp[1]=0,那么直接从dp[i-1]递推出dp[i]即可。递推的过程类似于数列的左右滑动,递推式为dp[i] = (dp[i-1] + k) % i。这种方法的时间复杂度为O(N)

STL链表实现代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    while(cin >> n >> k) {
        list<int> v;
        for(int i = 1; i <= n; ++i)
            v.push_back(i);
        auto pos = v.begin();
        while(v.size() > 1) {
            for(int i = 1; i < k; ++i) {
                ++pos;
                if(pos == v.end())
                    pos = v.begin();
            }
            pos = v.erase(pos);
            if(pos == v.end())
                pos = v.begin();
        }
        cout << v.front() << endl;
    }
    return 0;
}

C++动态规划实现代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024;
int n, k, dp[maxn];  //n为初始总人数,k为出列的数

int main() {
    while(cin >> n >> k) {
        dp[1] = 0;   //初始化
        for(int i = 2; i <= n; ++i)
            dp[i] = (dp[i-1] + k) % i;  //递推
        cout << dp[n] << endl;   //最后出列人数的‘下标’
    }
    return 0;
}

OJ真题演练(HDU2925)

点击打开题目链接

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024000;
int n, k, dp[maxn];

int main() {
    while(scanf("%d%d", &n, &k), n||k) {
        dp[1] = 0;
        for(int i = 2; i <= n; ++i)
            dp[i] = (dp[i-1] + k) % i;
        printf("%d %d %d\n", n, k, dp[n]+1);
    }
    return 0;
}

 

欢迎留言