(Josephus 问题)有 n个人围成一个圈,依次标号 0 至n-1。从 0 号开始,依次 0, 1, 0, 1, … 交替报数,报到 1 的人会离开,直至圈中只剩下一个人。求最后剩下人的编号。
试补全模拟程序。
01 #include <iostream>
02
03 using namespace std;
04
05 const int MAXN = 1000000;
06 int F[MAXN];
07
08 int main() {
09 int n;
10 cin >> n;
11 int i = 0, p = 0, c = 0;
12 while (①) {
13 if (F[i] == 0) {
14 if (②) {
15 F[i] = 1;
16 ③;
17 }
18 ④;
19 }
20 ⑤;
21 }
22 int ans = -1;
23 for (i = 0; i < n; i++)
24 if (F[i] == 0)
25 ans = i;
26 cout << ans << endl;
27 return 0;
28 }
①处应填( )
i < n
c < n
i < n - 1
c < n - 1
②处应填( )
i % 2 == 0
i % 2 == 1
p
!p
③处应填( )
i++
i = (i + 1) % n
c++
p ^= 1
④处应填( )
i++
i = (i + 1) % n
c++
p^=1
⑤处应填( )
i++
i = (i + 1) % n
c++
p^=1