LA-4727 Jump(递推)

题意：给定n和k，问每隔k人的n人约瑟夫游戏中最后出局的三个人的编号。

分析:设f(i,j)表示共i个人的约瑟夫环中出局的第j个人的编号，我们每出局一个人重新编号后有f(i,j) = (f(i-1,j-1) + k) % i.

#include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<queue> #define INF 2147483640 #define eps 1e-9 #define MAXN 30010 using namespace std; int t,n,k; int f(int i,int j) { if(j == 1) return k % i ? k % i : i; int temp = (f(i-1,j-1) + k) % i; return temp ? temp : i; } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); cout<<f(n,n-2)<<" "<<f(n,n-1)<<" "<<f(n,n)<<endl; } }