Koios1143的筆記

TOJ 104

發表於 分類於

TOJ 104

題目

https://toj.tfcis.org/oj/pro/104/

輸入一個正整數 $n$ ，輸出高度為 $n$ 的星星樹

想法

第一次接觸星星樹這類的題目可以藉由觀察來寫下迴圈

我們可以先把星星樹的每一層給一個數字

以下考慮 $n=4$ 的情況

1
2
3
4
0 |   *
1 |  ***
2 | *****
3 |*******

接下來觀察每一行內空格和數字的關係

1
2
3
4
第 0 行 有 3 個空格
第 1 行 有 2 個空格
第 2 行 有 1 個空格
第 3 行 有 0 個空格

因為空格的數量與 $n$ 息息相關，我們換成與 $n$ 相關的話來看看

1
2
3
4
第 0 行 有 n-1 個空格
第 1 行 有 n-2 個空格
第 2 行 有 n-3 個空格
第 3 行 有 n-4 個空格

再加上與行數的關係

1
2
3
4
第 0 行 有 (n-1)-0 個空格
第 1 行 有 (n-1)-1 個空格
第 2 行 有 (n-1)-2 個空格
第 3 行 有 (n-1)-3 個空格

發現到關係了嗎? 那麼我們也考慮星星的情況

1
2
3
4
第 0 行 有 1 個星星
第 1 行 有 3 個星星
第 2 行 有 5 個星星
第 3 行 有 7 個星星

星星的數量無論 $n$ 是多少，順序仍然相同，都是從 $1$ 開始，並且每次加上 $2$ ，所以接下來直接考慮與行數的關係

1
2
3
4
第 0 行 有 (0+1)*2-1 個星星
第 1 行 有 (1+1)*2-1 個星星
第 2 行 有 (2+1)*2-1 個星星
第 3 行 有 (3+1)*2-1 個星星

有了這些關係式，我們就可以輕易地寫出巢狀迴圈了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//By Koios1143
#include<iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
	// i 表示行數
    for(int i=0 ; i<n ; i++){
		// 先輸出空格
        for(int j=0 ; j<n-1-i ; j++){
            cout<<' ';
        }
		// 再輸出星星
        for(int j=0 ; j<2*(i+1)-1 ; j++){
            cout<<'*';
        }
        cout<<'\n';
    }
    return 0;
}

複雜度分析

總時間複雜度約為 $O(n^2)$