acm 约瑟夫环问题
发布网友
发布时间：2022-04-27 02:22
我来回答
共1个回答
热心网友
时间：2022-06-22 06:21
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 );
}
}
OJ约瑟夫环基础题“选猴王”代码求帮助!!!题目的网址是http://acm.ues...
//现在编译已经没有问题了，逻辑错误还要我帮你改吗？include <stdio.h> include <stdlib.h> typedef struct LNode { int data;struct LNode *next;}Node;Node* newnode(int value){ Node* u = (Node*) malloc(sizeof(Node));if(u != NULL){ u->data = value;u->next = NULL;} ...
c++练习题
1.if (a > b && a > c)max = a;else if (b > a && b > c)max = b;else max = c;2.while ( cin >> amount){ amt = amount / 10;switch (amt){ case 0: pay = amount * PRICE; cout << pay << endl; break;case 1: pay = amount * PRICE * 0.9; cout << ...
