#cspjc2021w1. 2021csp-j初赛完善程序1

2021csp-j初赛完善程序1

2021csp-j初赛完善程序1

每小题3 分

1.第一题

(Josephus 问题)有 𝑛 个人围成一个圈,依次标号 0 至 𝑛 − 1。从 0 号开始,依次 0, 1, 0, 1, … 交替报数,报到 1 的人会离开,直至圈中只剩下一个人。求最后剩下人的编号。

​ 试补全模拟程序。

#include <iostream>

using namespace std;

const int MAXN = 1000000;
int F[MAXN];

int main() {
	int n;
	cin >> n;
	int i = 0, p = 0, c = 0;
	while (①) {
		if (F[i] == 0) {
			if (②) {
				F[i] = 1;
				③;
			}
			④;
		}
		⑤;
	}
	int ans = -1;
	for (i = 0; i < n; i++)
		if (F[i] == 0)
			ans = i;
	cout << ans << endl;
	return 0;
}

1.①处应填( ){{ select(1) }}

  • i < n
  • c < n
  • i < n- 1
  • c < n-1

2.②处应填( ){{ select(2) }}

  • i % 2 == 0
  • i % 2 == 1
  • p
  • !p

3.③处应填( ) {{ select(3) }}

  • i++
  • i = (i + 1) % n
  • c++
  • p ^= 1

4.④处应填( ) {{ select(4) }}

  • i++
  • i = (i + 1) % n
  • c++
  • p ^= 1

5.⑤处应填( ) {{ select(5) }}

  • i++
  • i = (i + 1) % n
  • c++
  • p ^= 1