hdu 1443 Joseph （约瑟夫环）

本文主要是介绍hdu 1443 Joseph （约瑟夫环），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1443

题意：给出k，2*k个人围成一个环，前k个人是好人，后k个人是坏人，现在我们需要每隔m个人把坏人挑出来，但是条件是最后一个坏人挑出来前不能有好人被挑出来。。问最小的m是多少。（从第一个开始数）

分析：约瑟夫问题的变形，暴力枚举+打表，先暴力求出所有情况的结果，用数组保存起来打表，否则会tl，m可能的最小值为k+1，依次递加，直到找到满足条件的m为止，递推公式为a[i]=(a[i-1]+m-1)%(2*k-i+1);a[i]表示被选中的人。

暴力代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 30;
int a[maxn];
int main(){int k=1;memset(a,0,sizeof(a));while(k<14){int m=k+1;for(int i=1;i<=k;i++){a[i]=(a[i-1]+m-1)%(2*k-i+1);if(a[i]<k){i=0;///坑啊，之前把i赋值成1了，一直报错，每次循环执行后有加了一次i就变成2了，语法不精！！！m++;}}cout<<m<<endl;k++;}
}

打表代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int ans[14]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};
int main(){int k;while(cin>>k&&k){cout<<ans[k]<<endl;}
}

这篇关于hdu 1443 Joseph （约瑟夫环）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---