首页 > 代码库 > POJ 3517 And Then There Was One(约瑟夫环-递推or模拟)

POJ 3517 And Then There Was One(约瑟夫环-递推or模拟)

POJ 3517


题目: n  k m

            数字1到n成环,先叉数字m,往下数k个,直到最后只有一个数字,输出它。



链表模拟:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#define MAXN 200001
#define MOD  1000000007
#define INF  0x7fffffff
#define EPS  1e-8
#define PI acos(-1.0)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define bug(a) cout<<"bug---->"<<a<<endl;
#define FIN             freopen("datain.txt","r",stdin);
#define FOUT            freopen("dataout.txt","w",stdout);
#define mem(a,b)        memset(a,b,sizeof(a))
//#pragma comment         (linker,"/STACK:102400000,102400000")

typedef long long LL;
typedef unsigned long long ULL;
using namespace std;

struct Link{
    int data;
    Link* next;
    Link* pre;
}node[10001];

int main()
{
    int n,k,m;
    while(scanf("%d%d%d",&n,&k,&m),n||k||m)
    {
        for(int i=1;i<=n;i++)                            //构建双向循环链表
        {
            node[i].data=http://www.mamicode.com/i;>

递推:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define N
#define INF
#define ll __int64
#define eps 1e-12
#define PI 4.0*atan(1.0)
using namespace std;

int main()
{
    int n,m,k;
    while(~scanf("%d%d%d",&n,&k,&m))
    {
        if(n==0 && m==0 && k==0)
            break;
        int s=0;
        for(int i=2;i<=n-1;i++)
            s=(s+k)%i;
        printf("%d\n",(s+m)%n+1);
    }
    return 0;
}