1.问题描述
编号为1,2,...,100的100位小朋友依次排成一列。从1号开始1,2,3报数,凡报到3者出列,直到报数到队列尾部。此后,又从队列尾开始反向1,2,3报数,凡报到3者同样出列。这样反复顺逆报数,直到队列剩下2个小朋友为止。
问:最后两个小朋友编号为多少?第50个出列的是哪一个?
2.设计思路
为一般考虑,设总人数为n,报数从1,2,...报到m。求最后m-1个未出列进行与指定的第p个出列者的编号。
设置数组a(n),每一数组元素赋初值1.每报数一人,和变量s变量增1.当加a(i)后和变量s的值为m时,a(i)=0,标志编号为i者出列,设置ln统计出列人数。同时,s=0并重新向后作报数累加。至队尾后,和变量s=0,向前报数同样处理。
当出列人数ln为指定的数p时,x=i,x即为第p个出列者的编号。
当出列人数ln达n-m+1时,即未出列者只有m-1人,终止报数,打印这剩下的m-1编号。
3.代码实现
#include "stdafx.h" int main(void) { int ln, x, t, s, i, n, m, p; static int a[200]; printf("编号的n个人排一列,从前到后1,2,。。。,m报数,/n"); printf("报m的出列。接着从后到前1,2,。。。,m报数,类推。/n"); printf("求最后m-1个未出列者与第p个出列者。/n"); printf("请依次输入n,m,p:"); scanf("%d%d%d", &n, &m, &p); for (i = 1; i <= n; i++) a[i] = 1; ln = 0; x = 0; t = 0; while (1) { for (s = 0, i = 1; i <= n; i++) { // 从头到尾顺报数 s += a[i]; if (s == m) { // 报到指定的m者出列赋0 a[i] = 0; s = 0; ln++; } if (ln == p && !x) // 第p个出列者i号赋给x x = i; if (ln == n - m + 1) { t = 1; break; } } for (s = 0, i = n; i >= 1; i--) { s += a[i]; if (s == m) { a[i] = 0; s = 0; ln++; } if (ln == p && !x) x = i; if (ln == n-m + 1) { t = 1; break; } } if (t == 1) break; } printf("队列中最后剩下%d个人号码分别为: ", m- 1); for (i = 1; i <= n; i++) if (a[i]) printf("%d ", i); // 打印剩下m-1个未出列者 printf("/n第%d个出列者是:%d号/n", p, x); return 0; }