问题链接:。可以说是双向约瑟夫环问题,用C语言编写程序。
问题简述:输入n、k和m,n为人数,逆时针序号为1~n,A从1按逆时针数到第k个人停下来,B从n开始按顺时针数到第m个人停下来,输出被数到的人,并且让这些人出局。输出出局人的序号(输出格式参见原题说明)。
解题思路:用模拟法来解决。
程序中,带参数的宏定义next()用于计算下一个位置。函数go()用于找到下一个位置。
AC的C语言程序如下:
/* UVA133 The Dole Queue */#include#define MAXN 20#define next(p, d, n) (p + d + (n -1)) % n + 1int circle[MAXN];int go(int start, int direct, int k, int n){ while(circle[start] == 0) start = next(start, direct, n); while(--k) { start = next(start, direct, n); while(circle[start] == 0) start = next(start, direct, n); } return start;}int main(void){ int n, k, m, residue, pa, pb, i; while(scanf("%d%d%d", &n, &k, &m) != EOF) { if(n == 0 && k == 0 && m == 0) break; for(i=1; i<=n; i++) circle[i] = i; residue = n; pa = 1; pb = n; while(residue) { pa = go(pa, 1, k, n); pb = go(pb, -1, m, n); circle[pa] = circle[pb] = 0; if(pa == pb) { printf("%3d", pa); residue--; } else { printf("%3d%3d", pa, pb); residue -= 2; } if(residue) printf(","); } printf("\n"); } return 0;}