首页 > 代码库 > 【hoj】1016 Joseph's problem I
【hoj】1016 Joseph's problem I
约瑟夫问题是一个很经典的问题,描述的是n的人围成一圈,每次数到第m个人就会被淘汰,之后在淘汰的人开始在数起第m个人,这样下去只带还剩下1个人为胜利者,这个题是约瑟夫问题的变形,它每次裁定的标准不再是一个恒定的m而是按照素数表中的第i次淘汰第i个人,所以我们需要求出素数表才能知道裁定的次序,也才能求出剩下的人的序号
首先,对于约瑟夫原本的问题是可以对每次淘汰使用逐个列举,将这n个人每个人都列举,没有出局的话就计1直到数到还没淘汰的第m个,但是这样下来对于n值很大的情况就会很耗时间,所以一定会有别的方式 :
设n个人是从0-(n-1)排列的则第一次淘汰就是第(m-1)%n个人,则剩下从 k = m%n;起重新数
k =>0
k+1 =>1
|
k-2 =>n-2;
这样该问题就变化为求解以上n-1个元素的子问题,设该子问题的解为:x‘,即为大的问题的解,然而我们需要恢复其在原问题中的位置序号,因为子问题的数是在原问题的基础上加了k所以原解应为 x = (x‘+k)%n;
所以可以递归 x‘ = (x‘‘+m)%n-1;
当还剩下一个时自己就是该问题的解序号为0,故f(1) = 0; f(2) = (f(1) + m)%2.。。。。。
1016 就是原问题的变型,所不同的是每一次的m都是动态的,所以我们可以先计算出每次递归时所需要的素数,因为要去掉n-1个人,所以肯定要n-1个素数,而当还剩2个人时使用的是第n-1个素数,3个人时是第n-2个素数。。。。。。n个人是第1个素数。。。这样每次都用特定的素数去取代m就可以把正确的解带回到原问题中
#include <iostream> #include <cstring> #define MAX 3600 using namespace std; int num; bool p[MAX]; int prim[MAX]; void findPrime() { int i,n = 0; memset(prim,0,sizeof(prim)); i = 2; prim[n++] = i; do{ for(int j = 2;j<i;j++){ if(i%j == 0) break; else if(j == i-1){ prim[n++] = i; break; } } i++; }while(n < MAX); return; } int main() { int a,i; int m; findPrime(); while(cin>>num){ if(num == 0) break; int s = 0; for(i = 2;i <= num;i++){ a = prim[num-i]; s = (s+a)%i; } cout<<s+1<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。