信息学奥赛初赛天天练-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
*/