四川蓉和建设公司网站,乡镇做电器网站能不能营运,网站建立免费,视频网站怎么做防盗链PDF文档公众号回复关键字:20240624 2021 CSP-J 完善程序3
1 完善程序 (单选题 #xff0c;每小题3分#xff0c;共30分)
#xff08;Josephus问题#xff09;有n个人围成一个圈#xff0c;依次标号0至n-1。从0号开始#xff0c;依次 0#xff0c;1#xff0c;0#…PDF文档公众号回复关键字:20240624 2021 CSP-J 完善程序3
1 完善程序 (单选题 每小题3分共30分)
Josephus问题有n个人围成一个圈依次标号0至n-1。从0号开始依次 0101…交替报数报到1的人会离开直至只剩下一个人。求最后剩下人的编号
#includestdio.hconst int MAXN1000000;
int F[MAXN];int main(){int n;scanf(%d,n);int i0,p0,c0;while(①){if(F[i]0){if(②){F[i]1;③;}④}⑤;}int ans-1;for(i0;in;i)if(F[i]0)ansi;printf(%d\n,ans);return 0;
} 34.①处应填( )
A. in
B. cn
C. in-1
D. cn-1
35.②处应该填( )
A. i%20
B. i%21
C. p
D. !p
36.③处应该填( )
A. i
B. i(i1)%n
C. c
D. p^1
37.④处应该填( )
A. i
B. i(i1)%n
C. c
D. p^1
38.⑤处应该填( )
A. i
B. i(i1)%n
C. c
D. p^1
2 相关知识点
1) 异或运算
异或运算XOR是一种基本的数学运算符应用于逻辑运算其数学符号为“⊕”计算机符号为“xor”
异或运算的运算法则为如果两个值不相同则异或结果为1如果两个值相同则异或结果为0
//示例
2 xor 3 1
具体过程如下
2 对应二进制 0010
3 对应二进制 001100100011
xor
----------0001C语言中 异或符号为 ^
p^1等价pp^1p为0时 p^10^11
具体过程如下
0对应二进制为 0000
1对应二进制为 000100000001
xor
----------0001p为1时 p^11^10
具体过程如下
1对应二进制为 000100010001
xor
----------00002) 约瑟夫问题
约瑟夫问题特征是有环到最大人数后重新数因此使用数组模拟约瑟夫问题时达到最大需要从头开始
一轮需要有一人出去需要一个变量标识一轮的开始结束
需要保留1人需要一个变量统计出去的人数进而和总人数比较
3 思路分析
34.①处应填( D )
A. in
B. cn
C. in-1
D. cn-1
分析
/*模拟每个人的位置,到达最大位置重新开始p表示2人出去1人的一轮对应的值即0 1由于只有2次所以当前人p为0时下一个人p就为1c出去的人数
*/
int i0,p0,c0;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所以判定条件为cn-1
*/35.②处应该填( C )
A. i%20
B. i%21
C. p
D. !p
分析
/*模拟每个人的位置,到达最大位置重新开始p表示2人出去1人的一轮对应的值即0 1由于只有2次所以当前人p为0时下一个人p就为1c出去的人数
*/
int i0,p0,c0;while(①){if(F[i]0){if(②){F[i]1;③;}④}⑤;}
/*for(i0;in;i)if(F[i]0)ansi;根据上面代码可知输出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(i1)%n
C. c
D. p^1
分析
/*模拟每个人的位置,到达最大位置重新开始p表示2人出去1人的一轮对应的值即0 1由于只有2次所以当前人p为0时下一个人p就为1c出去的人数
*/
int i0,p0,c0;while(①){if(F[i]0){if(②){F[i]1;③;}④}⑤;}
/*c为出去的人数符号出去的条件c累加所以选C
*/37.④处应该填( D )
A. i
B. i(i1)%n
C. c
D. p^1
分析
/*模拟每个人的位置,到达最大位置重新开始p表示2人出去1人的一轮对应的值即0 1由于只有2次所以当前人p为0时下一个人p就为1c出去的人数
*/
int i0,p0,c0;while(①){if(F[i]0){if(②){F[i]1;③;}④}⑤;}
/*p变量模拟01变化值下1个为0再下1个为1只要数数就会变化0变11变0p^1 等价 p p^1; -- 0通过p^1可以变为11通过p^1可以变为0所以选D
*/38.⑤处应该填( B )
A. i
B. i(i1)%n
C. c
D. p^1
分析
/*模拟每个人的位置,到达最大位置重新开始p表示2人出去1人的一轮对应的值即0 1由于只有2次所以当前人p为0时下一个人p就为1c出去的人数
*/
int i0,p0,c0;while(①){if(F[i]0){if(②){F[i]1;③;}④}⑤;}
/*通过对n取余保证出去下标不会超过n用数组模拟环所以选B
*/
