时间限制:1 秒

内存限制:32 兆

特殊判题:否

提交:1891

解决:817

题目描述:

N个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。

    请按退出顺序输出每个退出人的原序号。

输入:

包括一个整数N(1<=N<=3000)及一个整数p。

输出:

测试数据可能有多组,对于每一组数据,

按退出顺序输出每个退出人的原序号。

样例输入:
7 3
样例输出:
3 6 2 7 5 1 4
来源:
2003-2005年华中科技大学计算机研究生机试真题

思路:

用数组链表模拟。计算过程中,p对当前圈中人数取模可减少搜索时间。

代码:

#include <stdio.h>
#include <string.h> #define N 3000 int n, p, cur, cur0;
int next[N+1]; void init()
{
for (int i=1; i<n; i++)
next[i] = i+1;
next[n] = 1;
cur0 = n;
cur = 1;
} int main(void)
{
int i; while (scanf("%d%d", &n, &p) != EOF)
{
init(); while (n > 1)
{
for (i=1; i<(p%n==0 ? n : p%n); i++)
{
cur0 = cur;
cur = next[cur];
}
n --;
printf("%d ", cur);
cur = next[cur];
next[cur0] = cur;
}
printf("%d\n", cur);
} return 0;
}
/**************************************************************
Problem: 1188
User: liangrx06
Language: C
Result: Accepted
Time:40 ms
Memory:924 kb
****************************************************************/

05-11 17:23