class="markdown_views prism-tomorrow-night">
题目类型:约瑟夫环模型, 函数的简单应用, 自顶向下编程
题目大意 : 输入n, k, m; n个人站成圆环,k,m, 分别代表停顿中间间隔的人数, 其中一个顺时针旋转,一个逆时针旋转, 直 至环中没有人。
注意 : 1次旋转的时候,只有顺逆都完成,所选出的两个人才都被cut到, 不能一个一个的cut,这样会少一个。
难点:怎么弄出来一个圈???
(pos+flag+n-1)%n+1 公式的妙用, 这样控制循环的下一个,不会跑出来。
例题代码:
int n, k, m, a[maxn];
int go(int p, int d, int t)
{
while(t--)
{
do{
p = (p+d+n-1) % n + 1;
}while(a[p] == 0);
}
return p;
}
int main()
{
while(scanf("%d %d %d", &n, &k, &m))
{
if(n == 0 && m == 0 && k == 0) break;
int i;
for(i = 1; i <= n; i++) a[i] = i;
int left = n;
int p1 = n, p2 = 1;
while(left)
{
p1 = go(p1, 1, k);
p2 = go(p2, -1, m);
printf("%3d", p1);
left--;
if(p2 != p1)
{
printf("%3d", p2);
left--;
}
a[p1] = a[p2] = 0;
if(left) printf(",");
}
printf("
");
}
return 0;
}