首页 > 代码库 > 主要的约瑟夫环问题
主要的约瑟夫环问题
解说
http://poj.org/problem?id=3517
n个人,编号为1~n。每次从1開始数,数到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,然后从1開始数,每次数到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; }
http://poj.org/problem?id=2244
与上题类似,第一个出圈的是第一个人,之后出圈的是报数为m的人。求最小的m使得最后一个人的编号为2。
直接枚举m就可以,当求得最后一个人的编号为2时,m就是答案。
#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; int f[155]; int n; int solve(int m) { f[1] = 0; for(int i = 2; i < n; i++) f[i] = (f[i-1]+m)%i; f[n] = (f[n-1]+1)%n; if(f[n]+1 == 2) return true; return false; } int main() { while(~scanf("%d",&n)&&n) { for(int m = 1; ; m++) { if(solve(m)) { printf("%d\n",m); break; } } } return 0; }
主要的约瑟夫环问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。