acm 约瑟夫环问题假设有2k个人围着一个圆桌坐着,前k个是好人,后k个是坏人 .现在开始,每m个人踢掉一个,比如有6个

来源：学生作业帮编辑：搜狗做题网作业帮分类：综合作业时间：2024/06/04 21:10:31

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

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

vb求约瑟夫问题的求解:有n个人围成一个圈,由第一个人开始报数,数到第k个人,这个人约瑟夫环已知n个人围坐在一张圆桌周围.从编号为k的人开始报数,数到m的那个人出列,m是什么一个数列{an}各项是1或3,首项为1,且在第k个1和第k＋1个1之间有2k-1个3,数列的前n项和为Sn. 1.5个人围着一个圆桌的5个位置坐,相对位置相同的坐法算1种,问有多少种不同的坐法? n个人,k个空位,n＜k,有多少种可能数据结构课程设计：设有n个人围坐在一个圆桌周围,编号为1,2,…,n.现在从第s个人开始逆序报数,即：第s个 C(k,4)（0.95）^k-4前N项和有公式吗?PS：C(k,4)是排列组合K个取4个某电影院的第一排有m个座位，后面每排比前一排多2个座位，则第k排的座位数是______个．已知一个数列{an}各项是1或2,首项为1,且在第k个1和第k+1个1之间有(2k-1﹚个2,即1,2,1,2,2,2, 一个树,结点的度最多为k(k>=2),试证至少有k个树叶采用链表解决约瑟夫问题：有n个人围坐在一起形成头尾相接的一个环,从第m个人开始报数,每次有人数到r时, 约瑟夫环问题：设编号为1,2,3,……,n的n(n>0)个人按顺时针方向围坐一圈,m为任意一个正整数.从第一个