acm 约瑟夫环问题

发布网友

我来回答

共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 <stdio.h>
// 给定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 <= k; n++ )
{
int now = a( k, m, n );
if ( now <= k )
return false;
}
return true;
}
// 根据k，计算出最小的合适的m。如果没有合适的m，则返回0
int calc_the_best_m( int k )
{
int m;
for( m = k + 1; m <= 2 * k; m++ )
if ( is_m_good( k, m ) )
break;
if ( m > 2 * k )
m = 0;
return m;
}
void main()
{
// 对k从1到100考察，结论是只有k=1,3的时候，才有合适的m。
for( int k = 1; k <= 100; k++ )
{
int m = calc_the_best_m( k );
if ( m != 0 )
printf( "k=%d, best m=%d\n", k, m );
else
printf( "k=%d, no right m\n", k, m );
}
}