2021-CSP-J1：完善程序题（Josephus问题）

2023年8月1日 | 分类: 【编程】

 (2021CSP入门级第一轮认证)

(Josephus 问题）有 n 个人围成一个圈，依次标号 0 至 n-1。从 0 号开始，依次 0, 1, 0, 1, … 交替报数，报到 1 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。
试补全模拟程序。

  1. #include <stdio.h>
  2.  
  3. const int MAXN = 1000000;
  4. int F[MAXN];
  5.  
  6. int main(){
  7.     int n;
  8.     scanf("%d", &n);
  9.     int i = 0, p = 0, c = 0;
  10.     while(①){
  11.         if (F[i] == 0){
  12.             if ( ② ){
  13.                 F[i] = 1;
  14.                 ③; 
  15.             }
  16.             ④; 
  17.         }
  18.         ⑤; 
  19.     } 
  20.     int ans = -1;
  21.     for (int i = 0; i < n; i++)
  22.         if (F[i] == 0)
  23.             ans = i;
  24.     printf("%d\n", ans);
  25.     return 0;
  26. }

①处应填（）

A.i < n
B.c < n
C.i < n - 1
D.c < n - 1
②处应填（）

A.i % 2 == 0
B.i % 2 == 1
C.p
D.!p
③处应填（）

A.i++
B.i = (i+1) % n
C.c++
D.p ^= 1
④处应填（）
A.i++
B.i = (i+1) % n
C.c++
D.p ^= 1
⑤处应填（）
A.i++
B.i = (i+1) % n
C.c++
D.p ^= 1

 解析 

       本题考查变量与数组作用。
       数组F：由第22,23行发现F与答案输出有关，当F[i]为0时输出答案，因此可知F为标记是否出圈的数组。F[i]=0代表未离开，为1代表已离开
       变量c：观察有c的选项。发现特殊的，第一空中可能填入c，而第一空为while的边界条件。由题意可知循环结束条件为出圈人数达到n-1，联系选项可得c代表出圈人数。
       变量i：根据日常使用习惯结合题目选项合理考虑，可以猜测i为当前进行判定的位置，实际上确实如此
       变量p：剩余一个变量为p不知道作用。阅读题面发现“交替出圈”还未实现，且p初始化为0。结合第二空的选项以及第二空决定F[i]是否等于1（即是否出圈）来看，可以得知p用于判断当前人是否应当出圈。p为0则不出， p为1则出圈。
       1.c代表出圈人数，由题面可知出圈n-1个则循环结束
       2.由上推导可得，此处用于决定是否出圈，则与p有关。若p为1则出圈
       3.有一人出圈，出圈人数c增加
       4.实现p的01交替，0变1,1变0，使用异或1实现
       至此只剩一个操作也就是移动当前考虑的位置，注意到人围成一个环，因此需要进行取模。

       本题答案为DCCDB。