PDF文檔公眾號回復關鍵字:20240605
1 2023 CSP-J 完善程序1
完善程序（單選題，每小題 3 分，共計 30 分）
原有長度為 n+1,公差為1等升數列，將數列輸到程序的數組時移除了一個元素，導致長度為 n 的開序數組可能不再連續，除非被移除的是第一個或最后之個元素。需要在數組不連續時，找出被移除的元素。試補全程序。
源程序
01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int find_missing(vector<int>& 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 vector<int> 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 left=mid+1 B right=mid-1 C right=mid D left=mid
35 ③處應填（ ）
A left=mid+1 B right=mid-1 C right=mid D left=mid
36 ④處應填（ ）
A left+nums[0] B right+nums[0] C mid+nums[0] D right+1
37 ⑤處應填（ ）
A nums[0]+n B nums[0]+n-1 C nums[0]+n+1 D nums[n-1]
2 相關知識點
1) vector 參數傳遞-值傳遞
函數內形參改變對調用實參無影響
#include<bits/stdc++.h>
using namespace std;/*值傳遞 函數內增量了副本 函數內修改 對實參無影響
*/
void testVector(vector<int> vec){vec.push_back(4); /*輸出vec數組中每個元素,main函數實參傳遞過來3個2，函數內增加了1個4輸出 2 2 2 4 */ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}
}int main(){vector<int> vec(3,2);//聲明一個vector數組，初始化3個2 testVector(vec);//調用函數輸出 cout<<endl; //testVector 增加的4 對main函數的vec沒影響/*輸出vec數組中每個元素3個2輸出 2 2 2 */ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}return 0;
}2) vector 參數傳遞-指針傳遞
函數內形參改變，改變了調用的實參
#include<bits/stdc++.h>
using namespace std;/*指針傳遞 函數操作的是vector指針，通過指針對vector數組修改后vector被改變
*/
void testVector(vector<int> *vec){(*vec).push_back(4); /*輸出vec數組中每個元素,main函數實參傳遞過來3個2，函數內增加了1個4輸出 2 2 2 4 */ for(int i=0;i<(*vec).size();i++){cout <<(*vec)[i]<< ' ';}
}int main(){vector<int> vec(3,2);//聲明一個vector數組，初始化3個2 testVector(&vec);//調用函數輸出 cout<<endl; //testVector 增加了4 /*輸出vec數組中每個元素3個2和 4輸出 2 2 2 4*/ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}return 0;
}
3) vector 參數引用傳遞
函數內形參改變，改變了調用的實參
#include<bits/stdc++.h>
using namespace std;/*指針傳遞 形參相當于是實參的別名，對形參的操作其實就是對實參的操作，形參vector改變，實參也會改變
*/
void testVector(vector<int> &vec){vec.push_back(4); /*輸出vec數組中每個元素,main函數實參傳遞過來3個2，函數內增加了1個4輸出 2 2 2 4 */ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}
}int main(){vector<int> vec(3,2);//聲明一個vector數組，初始化3個2 testVector(vec);//調用函數輸出 cout<<endl; //testVector 增加了4 /*輸出vec數組中每個元素3個2和 4輸出 2 2 2 4*/ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}return 0;
}
4) 二分查找中間值
/* 向右逼近，如果找到滿足條件的數，會繼續向右找更大的數mid=(left+right)/2 left和right都接近最大值時，可能溢出可以使用下面寫法替換mid=left + (right-left) / 2;
*//* 向左逼近，如果找到滿足條件的數，會繼續向左找更小的數mid=(left+right+1)/2 left和right都接近最大值時，可能溢出可以使用下面寫法替換mid=left + (right-left+1) / 2;
*/
5) 二分找邊界
//左閉右閉 while left right 最終left=right+1
while(left<=right) left = mid + 1; right =mid-1;
//左閉右開 while left right 最終left=right
while(left<right) left = mid + 1; right =mid;
//左開右閉 while left right 最終left=right
while(left<right) left=mid; right=mid+1;
//左開右開 while left right 最終left=right-1
while(left+1<right) left=mid; right=mid;
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]==mid+nums[0]所以選B
*/
34 ②處應填（ ）
A left=mid+1 B right=mid-1 C right=mid D left=mid
答案 A
分析
//由判斷條件 nums[mid]==mid+nums[0] 可知，mid的左半部分是滿足順序的，繼續往右找//由于mid計算是向下取整，需要向右靠近 所以left=mid+1
//int mid = left + (right-left) / 2; mid計算是向下取整 需要left=mid+1，向右逼近
int find_missing(vector<int>& nums){int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right-left) / 2;if (nums[mid]==mid+nums[0]){left=mid+1;//找到滿足條件的繼續向右找}else{right=mid;}}return left+nums[0];
}
//nums={0,1,3,4,5} 下面模擬具體細節
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 滿足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid+1=1 right=2 不滿足 while(left<right)
退出循環
返回left+nums[0]=2
*///int mid = left + (right-left) / 2; mid計算是向下取整 如果left=mid 可能會死循環
int find_missing(vector<int>& nums){int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right-left) / 2;if (nums[mid]==mid+nums[0]){left=mid;//如果改成left=mid 會死循環}else{right=mid;}}return left+nums[0];
}
//nums={0,1,3,4,5}時會死循環 下面模擬具體細節
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 滿足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid=1 right=2 滿足 while(left<right)
mid=(1+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid=1 right=2 滿足 while(left<right)
*/
35 ③處應填（ ）
A left=mid+1 B right=mid-1 C right=mid D left=mid
答案 C
分析
/*
由于退出條件是 while (left < right) 最終退出時left==right ，前面又 left=mid+1，所以right==mid即可while(left<right) 對應 二分區間是前閉后開或者前開后閉
*/
36 ④處應填（ ）
A left+nums[0] B right+nums[0] C mid+nums[0] D right+1
答案 A
分析
//如果序列從0開始，最后1個找到的連續數字再找一個就是被移除的，前面示例
//nums={0,1,3,4,5} 下面模擬具體細節
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 滿足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid+1=1 right=2 不滿足 while(left<right)
退出循環
返回left+nums[0]=2
移除的數是2
*///如果不從0開始
//nums={2,3,5,6,7}
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=5,mid+nums[0]=2+2=4 不等 rgiht=mid=2 left=0 滿足 while(left<right)
mid=(0+2)/2=1 nums[1]=3,mid+nums[0]=1+2=3 相等 left=mid+1=2 right=2 不滿足 while(left<right)
退出循環
返回left+nums[0]=2+2=4
移除的數是4
*/
//退出條件是while(left<right) 最終left==right
//所以答案A和B都對，一般習慣返回left
37 ⑤處應填（ ）
A nums[0]+n B nums[0]+n-1 C nums[0]+n+1 D nums[n-1]
答案 D
分析
找到數組的最后一個，無論最后一個是否相等都說明前面都是連續的
 與矩陣乘法)
】)
