2022CCF認證第一輪（CSP-J）真題

三、完善程序題

第一題?枚舉因數

從小到大打印正整數n的所有正因數。試補全枚舉程序

#include <iostream>
using namespace std;int main(){int n;cin >> n;vector<int> fac;fac.reserve((int)ceil(sqrt(n)));int i;for (i= 1;i*i< n; ++i){if (①) {fac.push back(i);}}for (int k = 0; k< fac.size();++k){cout << ② << " ";}if (③) {cout <<④<<" ";}for (int k= fac.size()-1; k >= 0; --k){cout <<⑤<<;}
}

程序分析：此程序的功能是找出一個給定數n的所有因子。程序的思路是，遍歷從1到sqrt(n)的所有數，如果n能被該數整除，則將該數添加到一個vector中。然后再遍歷vector，輸出所有的因子，同時輸出n除以該因子的結果，即另一個因子。 具體分析如下：

• 首先，程序通過cin讀取一個整數n。
• 然后，定義一個vector<int>類型的變量fac來保存因子。
• 使用一個for循環，從1開始遍歷到sqrt(n)。
• 表達式i*i < n保證了i的取值范圍在[1, sqrt(n))之間。
• 在循環中，使用if條件判斷n是否能被i整除。
• 如果能整除，則將i添加到fac vector中。
• 循環結束后，通過一個for循環遍歷fac vector，按順序輸出所有的因子。
• 如果i*i等于n，說明n是一個完全平方數，此時只需要輸出一個因子即可。
• 最后，通過一個逆向的for循環遍歷fac vector，輸出n除以每個因子的結果，即另一個因子。

單選題

①處應該填

A.?n%i== 0
B.?n%i== 1
C.?n % (i-1)== 0
D.?n % (i-1)== 1

答案：A

答案分析：從程序分析中可以得知此處應該是A

②處應該填

A.?n / fac[k]
B.?fac[k]
C.?fac[k]-1
D.?n / (fac[k]-1)

答案：B

答案分析：從程序分析中可以得知此處應該是B

③處應該填

A.?(i-1)*(i-1)== n
B.?(i-1)*i==n
C.?i*i== n
D.?i*(i-1)== n

答案：C

答案分析：從程序分析中可以得知此處應該是C

④處應該填

A. n-i
B.?n-i+1
C. i-1
D. i

答案：D

答案分析：從程序分析中可以得知此處應該是D

⑤處應該填

A.?n / fac[k]
B.?fac[k]
C.?fac[k]-1
D.?n / (fac[k]-1)

答案：A

答案分析：從程序分析中可以得知此處應該是A

第二題?洪水填充

現有用字符標記像素顏色的 8x8 圖像。顏色填充的操作描述如下：給定起始像素的位置和待填充的顏色將起始像素和所有可達的像素(可達的定義：經過一次或多次的向上、下、左、右四個方向移動所能到達且終點和路徑上所有像素的顏色都與起始像素顏色相同)，替換為給定的顏色。試補全程序。

#include<iostream>
using namespace std;
const int ROWS = 8;
const int COLS = 8;struct Point {int r, c;Point(int r, int c): r(r), c(c){}
};bool is_valid(char image[ROWS][COLS], Point pt,int prev_color, int new_color){int r= pt.r;int c = pt.c;return (0 <= r && r < ROWS && 0 <=c && c < COLS && ① && image[r][c] != new_color);
}void flood_fill(char image[ROWS][COLS], Point cur, int new_color){queue<Point> queue;queue.push(cur);int prev_color = image[cur.r][cur.c];②;while (!queue.empty()){Point pt = queue.front();queue.pop();Point points[4]={③,Point(pt.r - 1, pt.c),Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};for (auto p : points){if (is_valid(image, p, prev_color, new_color)){④;⑤;}}}
}int main(){char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},{'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},{'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},{'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},{'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},{'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},{'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},{'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};Point cur(4, 4);char new_color ='y';flood_fill(image, cur, new_color);for (int r= 0;r< ROWS; r++){for (int c = 0; c< COLS; c++){cout << image[r][c] << " ";}cout << endl;}return 0;
}
//輸出
//g g g g g g g g
//g g g g g g r r
//g r r g g r g g
//g y y y y r g r
//g g g y y r g r
//g g g y y y y r
//g g g g g y g g
//g g g g g y y g

程序分析：此程序實現了一個基于隊列的洪泛填充算法（BFS），用于填充一個8x8的字符矩陣。該算法從給定的起始點開始，將起始點的顏色替換為新的顏色，并向該點的上下左右四個鄰居點進行遍歷，如果鄰居點的顏色與起始點顏色相同且不等于新的顏色，則將鄰居點的顏色替換為新的顏色，并將鄰居點添加到隊列中繼續遍歷。 具體的步驟如下：

• 定義一個結構體Point，用于表示矩陣中的一個點，包含行號r和列號c。
• 定義一個函數is_valid，用于判斷一個點是否是有效的，即在矩陣范圍內，顏色與起始點顏色相同且不等于新的顏色。
• 定義一個函數flood_fill，接受矩陣、起始點和新的顏色作為參數。
• 首先創建一個隊列，并將起始點添加到隊列中。
• 獲取起始點的顏色，并將起始點的顏色替換為新的顏色。
• 使用while循環遍歷隊列，直到隊列為空。
• 在每次循環中，取出隊列中的第一個點，并獲取其鄰居點。
• 遍歷鄰居點，如果鄰居點是有效的，將其顏色替換為新的顏色，并將鄰居點添加到隊列中。
• 在主函數main中，定義一個8x8的字符矩陣image，并初始化。
• 創建一個起始點cur，坐標為(4, 4)。
• 定義一個新的顏色new_color為'y'。
• 調用flood_fill函數，將矩陣image從起始點cur開始進行洪泛填充。
• 遍歷矩陣image，并輸出每個點的顏色。

單選題

①處應該填

A.?image[r][c]== prev_color
B.?image[r][c] != prev color
C.?image[r][c] == new_color
D.?image[r][c] != new_color

答案：A

答案分析：從程序分析中可以得知此處應該是起始點，答案A

②處應該填

A.?image[cur.r+1][cur.c]= new_color
B.?image[cur.r][cur.c]= new_color
C.?image[cur.r][cur.c+1]= new_color
D.?image[cur.r][cur.c]= prev_color

答案：B

答案分析：從程序分析中可以得知此處應該是起始點的顏色替換為新的顏色，答案B

③處應該填

A.?Point(pt.r, pt.c)
B.?Point(pt.r, pt.c+1)
C.?Point(pt.r+1, pt.c)
D.?Point(pt.r+1, pt.c+1)

答案：C

答案分析：從程序分析中可以得知此處應該是獲取相應的4個鄰居點，答案C

④處應該填

A.?prev_color = image[p.r][p.c]

B.?new_color = image[p.r][p.c]

C.?imagelp.r][p.c]= prev_color

D.?image[p.r][p.c]= new_color

答案：D

答案分析：從程序分析中可以得知此處應該是鄰居點替換為新的顏色，答案D

⑤處應該填

A.?queue.push(p)
B.?queue.push(pt)
C.?queue.push(cur)
D.?queue.push(Point(Rows,COLS))

答案：A

答案分析：從程序分析中可以得知此處應該是將鄰居點加入隊列中，答案A