http://poj.org/problem?id=3517
n个人,编号为1~n,每次数到m的人出圈,最后一个出圈的人的编号。
f[1] = 0; for(int i = 2; i <= n; i++) { f[i] = ( f[i-1] + m)%i; } printf("%d\n",f[n]+1);
这里第一次出圈的人的编号是m,然后从0开始数,每次数到k的人出圈,问最后出圈的人的编号。
注意递推顺序
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) #define C 240 #define S 20 using namespace std; const int maxn = 100010; int main() { int n,k,m; int f[10010]; while(~scanf("%d %d %d",&n,&k,&m)) { if(n == 0 && k == 0 && m == 0) break; int i; f[1] = 0; for(i = 2; i < n; i++) f[i] = (f[i-1]+k)%i; f[n] = (f[n-1]+m)%n; printf("%d\n",f[n]+1); } return 0; }
poj 3517 And Then There Was One(约瑟夫环问题),布布扣,bubuko.com
poj 3517 And Then There Was One(约瑟夫环问题)
原文:http://blog.csdn.net/u013081425/article/details/38443313