acm 约瑟夫环问题假设有2k个人围着一个圆桌坐着,前k个是好人,后k个是坏人 .现在开始,每m个人踢掉一个,比如有6个人,m=5,那么,被踢掉的人依次是5,4,6,2,3,1.现在要求,在踢掉第一个好人前,必需把
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/23 21:59:10
acm 约瑟夫环问题假设有2k个人围着一个圆桌坐着,前k个是好人,后k个是坏人 .现在开始,每m个人踢掉一个,比如有6个人,m=5,那么,被踢掉的人依次是5,4,6,2,3,1.现在要求,在踢掉第一个好人前,必需把
acm 约瑟夫环问题
假设有2k个人围着一个圆桌坐着,前k个是好人,后k个是坏人 .现在开始,每m个人踢掉一个,比如有6个人,m=5,那么,被踢掉的人依次是5,4,6,2,3,1.现在要求,在踢掉第一个好人前,必需把所有的坏人踢掉,问,给定一个k,求满足这个要求的最小的m.
设 a[n] 为第n次踢掉的人,则
a(n) = [a(n-1)+m-1]mod(2k-n+1)
这儿为什么是a(n-1)+m-1而不是a(n-1)+m
acm 约瑟夫环问题假设有2k个人围着一个圆桌坐着,前k个是好人,后k个是坏人 .现在开始,每m个人踢掉一个,比如有6个人,m=5,那么,被踢掉的人依次是5,4,6,2,3,1.现在要求,在踢掉第一个好人前,必需把
a(n) = [a(n-1)+m-1]mod(2k-n+1)这个公式给出的a(n),是当次的序号,而不是总序号.用这个公式推导出的被踢掉的人依次是5,4,4,2,2,1.和总序号5,4,6,2,3,1是相符合的.
多减1,是因为,这个人被踢走了后,后面的人会补上来.如果不减这个1,则导致多数1个人.例如,第一次5号被踢掉,然后6号就变成了新5号,总人数从6变成5,此时,如果还向后数5的话,就数到了10,[]mode 5 后得到5,显然不正确.减去1的话,则第2轮数到新4号.
下面的代码,对k从1到100,求满足条件的最小的m.结论是：
k = 1, m = 2
k = 3, m = 5
其他的k,都无满足条件的m.
#include
// 给定k,m,返回第n轮出局的人的序号
int a( int k, int m, int n )
{
if ( n == 0 )
return 1;
else
{
int pre = a( k, m, n - 1 );
int now = ( pre + m - 1 ) % ( 2 * k - n + 1 );
if ( now == 0 )
now = 2 * k - n + 1;
return now;
}
}
// 给定k,测试m是否合格（是否能保证坏人先出局）
bool is_m_good( int k, int m )
{
for ( int n = 1; n