约瑟夫环问题

2019-01-19  本文已影响0人  ffffffffffffly

编号1~n
报数 k 的人死
某一阶段的人数 i
特殊报数 m

思路

先编号n-1来算,再逆推,记得结果都要+1

变形

  1. 先杀死第m个人,再报数k的人死。
    poj 3517 And Then There Was One
#include <iostream>
using namespace std;
int main()
{
    int n, k, m;
    int ans;
    while(cin >> n >> k >> m && (n || m || k))
    {
        ans = 0;
        for(int i=2; i<=n-1; i++)
            ans = (ans+k)%i;
        ans = (ans + m)%n; //最后换成+m
        cout << ans + 1 << endl;
    }
    return 0;
}
  1. 第1轮,报1的人死,
    第2轮,报2的人死,
    ……
    ……
    第n-1轮,报n-1的人死。
    hdu 5643 King's Game
#include <iostream>
using namespace std;

int main()
{
    int t, n;
    int ans;
    while(cin >> t)
    {
        while(t--)
        {
            cin >> n;
            ans =0;
            for(int i=2, j=n-1; i<=n; i++,j--)
                ans = (ans + j)%i; //换成+j
            cout << ans+1 << endl;
        }
    }
    return 0;
}
  1. 编号1~n,要保留编号为x的人,求k的值(暴力求解)
    ZOJ1088——System Overload
#include <iostream>
using namespace std;
//第一轮第m死,之后为了保留x,求k的最小值
int  joseph(int n, int k)
{
    int ans =0;
    for(int i=2; i<n; i++)
        ans = (ans+k)%i;
    ans = (ans + 1)%n;
    return ans+1;
}

int main()
{
    int n, i;
    while(cin >> n && n)
    {
        for(i=1; ; i++)  //没有限制条件,可以大于n!!!
        {
            if(joseph(n, i) == 2)  //保留第2个
                break;
        }
        cout << i << endl;
    }
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读