[HackerRank]函數和碎形─遞迴樹(Functions and Fractals - Recursive Trees - Bash!)

題目描述

請用文字符號建立出一個如上擁有Y型分支的碎形樹,不可以將排好的文字寫入程式碼內直接輸出。為了避免讓樹無限制增長,將會輸入一個數字表示樹成長和分支的次數。

輸入格式

輸入只有一行整數N,範圍在1到5之間(包含1和5)。

輸出格式

輸出一共有63行,且每行有100個字元,也就是說一共要輸出6300個字元。需使用「_」和「1」字元表示出空間和樹的圖形。

範例輸入1

1

範例輸出1

額外解釋1

第一次樹的成長和分支,會形成一個「Y」字,用字元「1」來表示。第一次的成長和分支,分別會讓樹長高16個字元。所以下一次,也就是第二次的成長和分支,分別會讓樹長高16/2=8個字元。

範例輸入2

2

範例輸出2

額外解釋2

第二次樹的成長和分支,會再比第一次多形成兩個「Y」字,同樣用字元「1」來表示整顆樹的圖形。第二次的成長和分支,分別會讓樹長高8個字元。所以下一次,也就是第三次的成長和分支,分別會讓樹長高8/2=4個字元。

解題概念

觀察題目提供的碎形樹後可以發現,該碎形樹在經過五次的成長和分支後,所有分支會碰在一起,而難以再有第6次的成長和分支。也可以發現到,碎形樹在每次成長和分支的高度都會是上次的一半,且最後一次成長和分支的高度都只有1。因此能夠成長五次的碎形樹,其第一次成長和分支的高度為2^4=16,第二次成長和分支的高度為2^3=8,第三次成長和分支的高度為2^2=8,第二次成長和分支的高度為2^1=2,第五次成長和分支的高度為2^0=1。了解碎形樹的高度關係後,接下來就只是要想辦法用文字排列出碎形樹的圖形了。

要用文字排列出碎形樹的圖形不算簡單,雖然我們已經知道碎形樹的高度關係,但並不太清楚碎形樹的Y型分支的距離。其實距離也是一樣,觀察碎形樹之後可以發現,每次碎形樹分支出來的樹枝,最後都或左或右偏移中心點該次成長或分支的高度。

至於枝幹數量和第幾次成長和分支的關係為:第一次的成長和分支產生出2^0=1個Y形枝幹,第二次的成長和分支產生出2^1=2個Y形枝幹,第三次的成長和分支產生出2^2=4個Y形枝幹,第四次的成長和分支產生出2^3=8個Y形枝幹,第五次的成長和分支產生出2^4=16個Y形枝幹。

在撰寫程式的時候,要從樹根開始,逐行去串接字元,描繪出於該次成長或分支和所達高度的每個Y形枝幹的位置。以下是筆者實作出來的Java程式:

fractals

上圖是以下程式的執行結果:

由於題目是要使用Bash腳本來產生固定空間大小且固定生長廣度的碎形樹,最後把Java程式移植成Bash腳本之後可得到以下的參考答案。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章