信息学奥赛初赛天天练-34-CSP-J2021完善程序-按位异或、模拟算法、数组模拟环、约瑟夫问题应用
PDF文档公众号回复关键字:20240624
2021 CSP-J 完善程序3
1 完善程序 (单选题 ，每小题3分，共30分)
（Josephus问题）有n个人围成一个圈，依次标号0至n-1。从0号开始，依次 0，1，0，1…交替报数，报到1的人会离开，直至只剩下一个人。求最后剩下人的编号
#include<stdio.h>const int MAXN=1000000;
int F[MAXN];int main(){int n;scanf("%d",&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;printf("%d\n",ans);return 0;
}
34.①处应填( )
A. i<n
B. c<n
C. i<n-1
D. c<n-1
35.②处应该填( )
A. i%2==0
B. i%2==1
C. p
D. !p
36.③处应该填( )
A. i++
B. i=(i+1)%n
C. c++
D. p^=1
37.④处应该填( )
A. i++
B. i=(i+1)%n
C. c++
D. p^=1
38.⑤处应该填( )
A. i++
B. i=(i+1)%n
C. c++
D. p^=1
2 相关知识点
1) 异或运算
异或运算（XOR）是一种基本的数学运算符，应用于逻辑运算，其数学符号为“⊕”，计算机符号为“xor”
异或运算的运算法则为：如果两个值不相同，则异或结果为1；如果两个值相同，则异或结果为0
//示例
2 xor 3 = 1
具体过程如下
2 对应二进制 0010
3 对应二进制 001100100011
xor
----------0001
C++语言中 异或符号为 ^
p^=1等价p=p^1p为0时 p^1=0^1=1
具体过程如下
0对应二进制为 0000
1对应二进制为 000100000001
xor
----------0001p为1时 p^1=1^1=0
具体过程如下
1对应二进制为 000100010001
xor
----------0000
2) 约瑟夫问题
约瑟夫问题特征是有环，到最大人数后重新数，因此使用数组模拟约瑟夫问题时，达到最大需要从头开始
一轮需要有一人出去，需要一个变量标识一轮的开始结束
需要保留1人，需要一个变量统计出去的人数，进而和总人数比较
3 思路分析
34.①处应填( D )
A. i<n
B. c<n
C. i<n-1
D. c<n-1
分析
/*模拟每个人的位置,到达最大位置，重新开始p表示2人出去1人的一轮对应的值，即0 1，由于只有2次，所以当前人p为0时，下一个人p就为1c出去的人数
*/
int i=0,p=0,c=0;while(①){if(F[i]==0){if(②){F[i]=1;③;}④}⑤;}
/*由于c的初始值为0，即c为0时可以出去1人，接着c为1时继续判定可以出去1人，加上前面c为0时出去1人，总共可以出去2人c为n-2时可以出去n-1人，c为n-1时可以出去n人目标需要出去n-1人，c最大为n-2，所以判定条件为c<n-1
*/
35.②处应该填( C )
A. i%2==0
B. i%2==1
C. p
D. !p
分析
/*模拟每个人的位置,到达最大位置，重新开始p表示2人出去1人的一轮对应的值，即0 1，由于只有2次，所以当前人p为0时，下一个人p就为1c出去的人数
*/
int i=0,p=0,c=0;while(①){if(F[i]==0){if(②){F[i]=1;③;}④}⑤;}
/*for(i=0;i<n;i++)if(F[i]==0)ans=i;根据上面代码可知，输出ans是剩余的人的编号，判定是F[i]==0，所以出去的人是F[i]==1F[i]==0 改为 F[i]=1; 说明是F[i]=1时标记为出去此处是判定出去条件成立，由于是0 1 中，1出去，p初始为0，所以只有p为true或为1时才出去因此选C
*/
36.③处应该填( C )
A. i++
B. i=(i+1)%n
C. c++
D. p^=1
分析
/*模拟每个人的位置,到达最大位置，重新开始p表示2人出去1人的一轮对应的值，即0 1，由于只有2次，所以当前人p为0时，下一个人p就为1c出去的人数
*/
int i=0,p=0,c=0;while(①){if(F[i]==0){if(②){F[i]=1;③;}④}⑤;}
/*c为出去的人数，符号出去的条件c累加所以选C
*/
37.④处应该填( D )
A. i++
B. i=(i+1)%n
C. c++
D. p^=1
分析
/*模拟每个人的位置,到达最大位置，重新开始p表示2人出去1人的一轮对应的值，即0 1，由于只有2次，所以当前人p为0时，下一个人p就为1c出去的人数
*/
int i=0,p=0,c=0;while(①){if(F[i]==0){if(②){F[i]=1;③;}④}⑤;}
/*p变量模拟01变化值，下1个为0，再下1个为1，只要数数，就会变化：0变1，1变0p^=1 等价 p = p^1; -- 0通过p^1可以变为1，1通过p^1可以变为0所以选D
*/
38.⑤处应该填( B )
A. i++
B. i=(i+1)%n
C. c++
D. p^=1
分析
/*模拟每个人的位置,到达最大位置，重新开始p表示2人出去1人的一轮对应的值，即0 1，由于只有2次，所以当前人p为0时，下一个人p就为1c出去的人数
*/
int i=0,p=0,c=0;while(①){if(F[i]==0){if(②){F[i]=1;③;}④}⑤;}
/*通过对n取余，保证出去下标不会超过n，用数组模拟环所以选B
*/