題目描述

____________________________________________________________________________________________________
__________________1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1___________________
___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________
___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________
____________________1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
______________________1_____1_________1_____1_________1_____1_________1_____1_______________________
_______________________1___1___________1___1___________1___1___________1___1________________________
________________________1_1_____________1_1_____________1_1_____________1_1_________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
__________________________1_____________1_________________1_____________1___________________________
___________________________1___________1___________________1___________1____________________________
____________________________1_________1_____________________1_________1_____________________________
_____________________________1_______1_______________________1_______1______________________________
______________________________1_____1_________________________1_____1_______________________________
_______________________________1___1___________________________1___1________________________________
________________________________1_1_____________________________1_1_________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
__________________________________1_____________________________1___________________________________
___________________________________1___________________________1____________________________________
____________________________________1_________________________1_____________________________________
_____________________________________1_______________________1______________________________________
______________________________________1_____________________1_______________________________________
_______________________________________1___________________1________________________________________
________________________________________1_________________1_________________________________________
_________________________________________1_______________1__________________________________________
__________________________________________1_____________1___________________________________________
___________________________________________1___________1____________________________________________
____________________________________________1_________1_____________________________________________
_____________________________________________1_______1______________________________________________
______________________________________________1_____1_______________________________________________
_______________________________________________1___1________________________________________________
________________________________________________1_1_________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________

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



原題網址

https://www.hackerrank.com/challenges/fractal-trees-all

輸入格式

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

輸出格式

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

範例輸入1

1

範例輸出1

____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_________________________________1_______________________________1__________________________________
__________________________________1_____________________________1___________________________________
___________________________________1___________________________1____________________________________
____________________________________1_________________________1_____________________________________
_____________________________________1_______________________1______________________________________
______________________________________1_____________________1_______________________________________
_______________________________________1___________________1________________________________________
________________________________________1_________________1_________________________________________
_________________________________________1_______________1__________________________________________
__________________________________________1_____________1___________________________________________
___________________________________________1___________1____________________________________________
____________________________________________1_________1_____________________________________________
_____________________________________________1_______1______________________________________________
______________________________________________1_____1_______________________________________________
_______________________________________________1___1________________________________________________
________________________________________________1_1_________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________

額外解釋1

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

範例輸入2

2

範例輸出2

____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_________________________1_______________1_______________1_______________1__________________________
__________________________1_____________1_________________1_____________1___________________________
___________________________1___________1___________________1___________1____________________________
____________________________1_________1_____________________1_________1_____________________________
_____________________________1_______1_______________________1_______1______________________________
______________________________1_____1_________________________1_____1_______________________________
_______________________________1___1___________________________1___1________________________________
________________________________1_1_____________________________1_1_________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
__________________________________1_____________________________1___________________________________
___________________________________1___________________________1____________________________________
____________________________________1_________________________1_____________________________________
_____________________________________1_______________________1______________________________________
______________________________________1_____________________1_______________________________________
_______________________________________1___________________1________________________________________
________________________________________1_________________1_________________________________________
_________________________________________1_______________1__________________________________________
__________________________________________1_____________1___________________________________________
___________________________________________1___________1____________________________________________
____________________________________________1_________1_____________________________________________
_____________________________________________1_______1______________________________________________
______________________________________________1_____1_______________________________________________
_______________________________________________1___1________________________________________________
________________________________________________1_1_________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________

額外解釋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

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

final StringBuilder sb = new StringBuilder();  final String[] rows = makeFractalsTree(255, 300, 7, 6); for (final String row : rows) {     sb.insert(0, '\n').insert(0, row); }  System.out.println(sb);

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

參考答案

#!/bin/bash rows=63 cols=100 expend=4 read maxLevel  output=  ((halfCols_dec = cols / 2 - 1)) level=1 repeat=$(echo "2^${expend}" | bc) repeatCounter=${repeat} separate=0 r=${rows} while [ ${r} -gt 0 ] do     line=     p=0     branchNumber=$(echo "2^(${level}-1)" | bc)     endP=${halfCols_dec}     d=$(echo "2^(${expend}+1)" | bc)     for (( i = 1; i < level; i += 1 ))     do         (( d /= 2 ))         (( endP -= d ))     done     if [ ${separate} -eq 1 ] ; then         (( dd = repeat - repeatCounter + 1 ))         (( endP += d - dd ))         for (( ; p < endP; p += 1 ))         do             line=${line}_         done         line=${line}1         ((p += 1))         for (( i = 1; i < branchNumber; i += 1 ))         do             if (( i % 2 == 1 )) ; then                 (( endP = p + dd * 2 - 1 ))             else                 (( endP = p + d * 4 - 1 - dd * 2))             fi             for (( ; p < endP; p += 1 ))             do                 line=${line}_             done             line=${line}1             ((p += 1))         done     else         for (( ; p < endP; p += 1 ))         do             line=${line}_         done         line=${line}1         ((p += 1))         for (( i = 1; i < branchNumber; i += 1 ))         do             (( endP = p + dd * 2 - 1 ))             for (( ; p < endP; p += 1 ))             do                 line=${line}_             done             line=${line}1             ((p += 1))         done     fi          for (( ; p < cols; p += 1 ))     do         line=${line}_     done     output="${line}\n${output}"     ((repeatCounter -= 1))     if [ ${repeatCounter} -eq 0 ] ; then         if [ ${separate} -eq 0 ] ; then             separate=1             ((level += 1))         else             separate=0             if (( level == maxLevel + 1)) ; then                 break;             fi             (( repeat /= 2 ))             if [ ${repeat} -eq 0 ] ; then                 break;             fi         fi         repeatCounter=${repeat}     fi          ((r -= 1)) done ((r -= 1)) while [ ${r} -gt 0 ] do     line=     for (( i = 0; i < cols; i += 1 ))     do         line=${line}_     done     output="${line}\n${output}"     ((r -= 1)) done  printf ${output}