吴江那里有做公司网站的,注册页面模板,原则网站设计版式,虚拟商城wordpressPDF文档公众号回复关键字:20240605
1 2023 CSP-J 完善程序1
完善程序#xff08;单选题#xff0c;每小题 3 分#xff0c;共计 30 分#xff09;
原有长度为 n1,公差为1等升数列#xff0c;将数列输到程序的数组时移除了一个元素#xff0c;导致长度为 n 的开序数组…PDF文档公众号回复关键字:20240605
1 2023 CSP-J 完善程序1
完善程序单选题每小题 3 分共计 30 分
原有长度为 n1,公差为1等升数列将数列输到程序的数组时移除了一个元素导致长度为 n 的开序数组可能不再连续除非被移除的是第一个或最后之个元素。需要在数组不连续时找出被移除的元素。试补全程序。
源程序
01 #include iostream
02 #include vector
03
04 using namespace std;
05
06 int find_missing(vectorint nums){
07 int left 0, right nums.size() - 1;
08 while (left right){
09 int mid left (right-left) / 2;
10 if (nums[mid]mid ①){
11 ②;
12 }else{
13 ③
14 }
15 }
16 return ④;
17 }
18
19 int main(){
20 int n;
21 cin n;
22 vectorint nums(n);
23 for (int i 0; i n; i) cin nums[i];
24 int missing_number find_missing(nums);
25 if(missing_number ⑤) {
26 cout Sequence is consecutive endl;
27 }else{
28 cout Missing number is missing_number endl;
29 }
30 return 0;
31 }33 ①处应填
A 1 B nums[0] C right D left
34 ②处应填
A leftmid1 B rightmid-1 C rightmid D leftmid
35 ③处应填
A leftmid1 B rightmid-1 C rightmid D leftmid
36 ④处应填
A leftnums[0] B rightnums[0] C midnums[0] D right1
37 ⑤处应填
A nums[0]n B nums[0]n-1 C nums[0]n1 D nums[n-1]
2 相关知识点
1) vector 参数传递-值传递
函数内形参改变对调用实参无影响
#includebits/stdc.h
using namespace std;/*值传递 函数内增量了副本 函数内修改 对实参无影响
*/
void testVector(vectorint vec){vec.push_back(4); /*输出vec数组中每个元素,main函数实参传递过来3个2函数内增加了1个4输出 2 2 2 4 */ for(int i0;ivec.size();i){cout vec[i] ;}
}int main(){vectorint vec(3,2);//声明一个vector数组初始化3个2 testVector(vec);//调用函数输出 coutendl; //testVector 增加的4 对main函数的vec没影响/*输出vec数组中每个元素3个2输出 2 2 2 */ for(int i0;ivec.size();i){cout vec[i] ;}return 0;
}
2) vector 参数传递-指针传递
函数内形参改变改变了调用的实参
#includebits/stdc.h
using namespace std;/*指针传递 函数操作的是vector指针通过指针对vector数组修改后vector被改变
*/
void testVector(vectorint *vec){(*vec).push_back(4); /*输出vec数组中每个元素,main函数实参传递过来3个2函数内增加了1个4输出 2 2 2 4 */ for(int i0;i(*vec).size();i){cout (*vec)[i] ;}
}int main(){vectorint vec(3,2);//声明一个vector数组初始化3个2 testVector(vec);//调用函数输出 coutendl; //testVector 增加了4 /*输出vec数组中每个元素3个2和 4输出 2 2 2 4*/ for(int i0;ivec.size();i){cout vec[i] ;}return 0;
}3) vector 参数引用传递
函数内形参改变改变了调用的实参
#includebits/stdc.h
using namespace std;/*指针传递 形参相当于是实参的别名对形参的操作其实就是对实参的操作形参vector改变实参也会改变
*/
void testVector(vectorint vec){vec.push_back(4); /*输出vec数组中每个元素,main函数实参传递过来3个2函数内增加了1个4输出 2 2 2 4 */ for(int i0;ivec.size();i){cout vec[i] ;}
}int main(){vectorint vec(3,2);//声明一个vector数组初始化3个2 testVector(vec);//调用函数输出 coutendl; //testVector 增加了4 /*输出vec数组中每个元素3个2和 4输出 2 2 2 4*/ for(int i0;ivec.size();i){cout vec[i] ;}return 0;
}4) 二分查找中间值
/* 向右逼近如果找到满足条件的数会继续向右找更大的数mid(leftright)/2 left和right都接近最大值时可能溢出可以使用下面写法替换midleft (right-left) / 2;
*//* 向左逼近如果找到满足条件的数会继续向左找更小的数mid(leftright1)/2 left和right都接近最大值时可能溢出可以使用下面写法替换midleft (right-left1) / 2;
*/5) 二分找边界
//左闭右闭 while left right 最终leftright1
while(leftright) left mid 1; right mid-1;
//左闭右开 while left right 最终leftright
while(leftright) left mid 1; right mid;
//左开右闭 while left right 最终leftright
while(leftright) leftmid; rightmid1;
//左开右开 while left right 最终leftright-1
while(left1right) leftmid; rightmid;3 思路分析
二分法在本程序中find_missing函数就是利用二分法来找到一个长度为n的数组中不连续的位置从而找出被移除 元素的值。只需通过二分找到从左往右第一处使得nums[i]不为nums[0]i的的位置那么在数组中被移除的数就是nums[0]i
33 ①处应填
A 1 B nums[0] C right D left
答案 B
分析
/*
若数组连续 一定有nums[i]nums[0]i所以只需通过二分找到第一处使得nums[i]不为nums[0]i的的位置即可。因此二分的判断条件是nums[mid]midnums[0]所以选B
*/34 ②处应填
A leftmid1 B rightmid-1 C rightmid D leftmid
答案 A
分析
//由判断条件 nums[mid]midnums[0] 可知mid的左半部分是满足顺序的继续往右找//由于mid计算是向下取整需要向右靠近 所以leftmid1
//int mid left (right-left) / 2; mid计算是向下取整 需要leftmid1向右逼近
int find_missing(vectorint nums){int left 0, right nums.size() - 1;while (left right){int mid left (right-left) / 2;if (nums[mid]midnums[0]){leftmid1;//找到满足条件的继续向右找}else{rightmid;}}return leftnums[0];
}
//nums{0,1,3,4,5} 下面模拟具体细节
/*
left 0 right4
mid(04)/22 nums[2]3,midnums[0]202 不等 rgihtmid2 left0 满足 while(leftright)
mid(02)/21 nums[1]1,midnums[0]101 相等 leftmid11 right2 不满足 while(leftright)
退出循环
返回leftnums[0]2
*///int mid left (right-left) / 2; mid计算是向下取整 如果leftmid 可能会死循环
int find_missing(vectorint nums){int left 0, right nums.size() - 1;while (left right){int mid left (right-left) / 2;if (nums[mid]midnums[0]){leftmid;//如果改成leftmid 会死循环}else{rightmid;}}return leftnums[0];
}
//nums{0,1,3,4,5}时会死循环 下面模拟具体细节
/*
left 0 right4
mid(04)/22 nums[2]3,midnums[0]202 不等 rgihtmid2 left0 满足 while(leftright)
mid(02)/21 nums[1]1,midnums[0]101 相等 leftmid1 right2 满足 while(leftright)
mid(12)/21 nums[1]1,midnums[0]101 相等 leftmid1 right2 满足 while(leftright)
*/35 ③处应填
A leftmid1 B rightmid-1 C rightmid D leftmid
答案 C
分析
/*
由于退出条件是 while (left right) 最终退出时leftright 前面又 leftmid1所以rightmid即可while(leftright) 对应 二分区间是前闭后开或者前开后闭
*/36 ④处应填
A leftnums[0] B rightnums[0] C midnums[0] D right1
答案 A
分析
//如果序列从0开始最后1个找到的连续数字再找一个就是被移除的前面示例
//nums{0,1,3,4,5} 下面模拟具体细节
/*
left 0 right4
mid(04)/22 nums[2]3,midnums[0]202 不等 rgihtmid2 left0 满足 while(leftright)
mid(02)/21 nums[1]1,midnums[0]101 相等 leftmid11 right2 不满足 while(leftright)
退出循环
返回leftnums[0]2
移除的数是2
*///如果不从0开始
//nums{2,3,5,6,7}
/*
left 0 right4
mid(04)/22 nums[2]5,midnums[0]224 不等 rgihtmid2 left0 满足 while(leftright)
mid(02)/21 nums[1]3,midnums[0]123 相等 leftmid12 right2 不满足 while(leftright)
退出循环
返回leftnums[0]224
移除的数是4
*/
//退出条件是while(leftright) 最终leftright
//所以答案A和B都对一般习惯返回left37 ⑤处应填
A nums[0]n B nums[0]n-1 C nums[0]n1 D nums[n-1]
答案 D
分析
找到数组的最后一个无论最后一个是否相等都说明前面都是连续的
