k516 - P4.根號 (Sqrt)
題目描述
題目要求輸出一個特定形狀的星號圖案，圖案的結構類似於一個根號，並且圖案的大小由輸入的整數 n 決定。圖案由星號 * 和空格組成，需要精確地按照題目示例輸出。
解題思路
這道題的解題思路是直接模擬題目要求的圖案。程式碼使用一個二維布林陣列 a 來表示圖案，其中 a[i][j] = 1 表示在第 i 行第 j 列輸出星號，a[i][j] = 0 表示輸出空格。程式碼首先初始化陣列，然後根據題目示例的圖案結構，將相應位置的元素設為 1。最後，程式碼遍歷陣列，根據 a[i][j] 的值輸出星號或空格。
程式碼的邏輯可以分為幾個部分：
- 初始化陣列
a和ma。 - 根據
n的值，設定圖案的中心位置和邊界。 - 根據題目示例，設定陣列
a中星號的位置。 - 遍歷陣列
a，輸出星號或空格。
ma 陣列用於記錄每一行最遠的星號位置，以便控制輸出範圍。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n^2)
程式碼
#include <iostream>
using namespace std;
int n,i,j,ma[505];
bool a[505][25005];
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(i=0;i<n;++i){
a[n/2][i]=1;
ma[n/2]=max(ma[n/2],i);
}
for(i=n/2,j=n-1;i<n;++i,++j){
a[i][j]=1;
ma[i]=max(ma[i],j);
}
for(i=n-1,--j;i>=0;--i,++j){
a[i][j]=1;
ma[i]=max(ma[i],j);
}
for(i=0,--j;i<n*2;++i,++j){
a[0][j]=1;
ma[0]=max(ma[0],j);
}
for(int i=0;i<n;++i){
for(int j=0;j<=ma[i];++j){
if(a[i][j]){
cout << "*";
}
else{
cout << " ";
}
}
cout << "\n";
}
}