NYOJ 191 && POJ 1012 Joseph（约瑟夫环问题）

NYOJ 191 && POJ 1012 Joseph（约瑟夫环问题）

链接：​​click here~~​​

题意：假设有2k个人围着一个圆桌坐着，前k个是好人，后k个是坏人 。现在开始，每m个人踢掉一个，比如有6个人，m=5，那么，被踢掉的人依次是5,4,6,2,3,1。现在要求，在踢掉第一个好人前，必需把所有的坏人踢掉，问，给定一个k，求满足这个要求的最小的m，现在希望你写一个程序，快速的帮助小珂，计算出来这个m。

思路：我们来回想一下最基本的约瑟夫环问题， n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求最后余下的人编号，我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:  k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2  并且从k开始报0，如果做一下转换：  k --> 0  k+1 --> 1  k+2 --> 2  ...  ...  k-2 --> n-2  k-1 --> n-1  变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终剩下的人，那么根据上面这个表把这个x带回去就是n个人情况的解，变回去的公式很简单，x'=(x+k)%n  如何知道(n-1)个人报数的问题--只要知道(n-2)个人的解，(n-2)个人的解--求(n-3)的情况 ---- 递推公式：  令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n] 。

f[1]=0;  f[i]=(f[i-1]+m)%i; (i>1)

代码：

#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};const double eps = 1e-6;const double Pi = acos(-1.0);static const int inf= ~0U>>2;static const int maxn = 502;int k;int f[] = {2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881,13482720};//bool check(int num)//{// for(int i = 1; i <= k; i++)// {// int pos = i;// for(int j = k+1; j <= 2*k; j++)// {// pos = (pos+num)%j;// if(pos == 0) pos = j;// }// if(pos > k) return 0;// }// return 1;//}int main(){ while(~scanf("%d", &k)&& k) { cout << f[k-1] << endl; } return 0;}

When you want to give up, think of why you persist until now!

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。