acm 约瑟夫环问题假设有2k个人围着一个圆桌坐着,前k个是好人,后k个是坏人 .现在开始,每m个人踢掉一个,比如有6个人,m=5,那么,被踢掉的人依次是5,4,6,2,3,1.现在要求,在踢掉第一个好人前,必需把
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/18 06:05:29
![acm 约瑟夫环问题假设有2k个人围着一个圆桌坐着,前k个是好人,后k个是坏人 .现在开始,每m个人踢掉一个,比如有6个人,m=5,那么,被踢掉的人依次是5,4,6,2,3,1.现在要求,在踢掉第一个好人前,必需把](/uploads/image/z/15234819-51-9.jpg?t=acm+%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF%E9%97%AE%E9%A2%98%E5%81%87%E8%AE%BE%E6%9C%892k%E4%B8%AA%E4%BA%BA%E5%9B%B4%E7%9D%80%E4%B8%80%E4%B8%AA%E5%9C%86%E6%A1%8C%E5%9D%90%E7%9D%80%2C%E5%89%8Dk%E4%B8%AA%E6%98%AF%E5%A5%BD%E4%BA%BA%2C%E5%90%8Ek%E4%B8%AA%E6%98%AF%E5%9D%8F%E4%BA%BA+.%E7%8E%B0%E5%9C%A8%E5%BC%80%E5%A7%8B%2C%E6%AF%8Fm%E4%B8%AA%E4%BA%BA%E8%B8%A2%E6%8E%89%E4%B8%80%E4%B8%AA%2C%E6%AF%94%E5%A6%82%E6%9C%896%E4%B8%AA%E4%BA%BA%2Cm%3D5%2C%E9%82%A3%E4%B9%88%2C%E8%A2%AB%E8%B8%A2%E6%8E%89%E7%9A%84%E4%BA%BA%E4%BE%9D%E6%AC%A1%E6%98%AF5%2C4%2C6%2C2%2C3%2C1.%E7%8E%B0%E5%9C%A8%E8%A6%81%E6%B1%82%2C%E5%9C%A8%E8%B8%A2%E6%8E%89%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%A5%BD%E4%BA%BA%E5%89%8D%2C%E5%BF%85%E9%9C%80%E6%8A%8A)
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