題目描述

____________________________________________________________________________________________________
__________________1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1___________________
___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________
___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________
____________________1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
______________________1_____1_________1_____1_________1_____1_________1_____1_______________________
_______________________1___1___________1___1___________1___1___________1___1________________________
________________________1_1_____________1_1_____________1_1_____________1_1_________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
__________________________1_____________1_________________1_____________1___________________________
___________________________1___________1___________________1___________1____________________________
____________________________1_________1_____________________1_________1_____________________________
_____________________________1_______1_______________________1_______1______________________________
______________________________1_____1_________________________1_____1_______________________________
_______________________________1___1___________________________1___1________________________________
________________________________1_1_____________________________1_1_________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
__________________________________1_____________________________1___________________________________
___________________________________1___________________________1____________________________________
____________________________________1_________________________1_____________________________________
_____________________________________1_______________________1______________________________________
______________________________________1_____________________1_______________________________________
_______________________________________1___________________1________________________________________
________________________________________1_________________1_________________________________________
_________________________________________1_______________1__________________________________________
__________________________________________1_____________1___________________________________________
___________________________________________1___________1____________________________________________
____________________________________________1_________1_____________________________________________
_____________________________________________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程式:

/**
 * 製造碎形樹(從底部開始長)。
 *
 * @param rows 傳入總共有多少高度空間
 * @param cols 傳入總共有多少寬度空間
 * @param maxLevel 傳入樹要成長並分叉幾次
 * @param expand 傳入樹成長的廣度(從0開始,影響著樹可以成長和分叉的次數)
 * @return 回傳碎形樹字串陣列,每個元素代表一行字串。由於碎形樹是從底部開始長的,索引0是樹的根部
 */
public static String[] makeFractalsTree(final int rows, final int cols, final int maxLevel, final int expand) {
    final ArrayList<String> output = new ArrayList<>();

    final int halfCols_dec = cols / 2 - 1;
    int level = 1;
    int repeat = (int) Math.pow(2, expand);
    int repeatCounter = repeat;
    boolean separate = false;
    int r = rows;
    while (--r >= 0) {
        final StringBuilder sb = new StringBuilder();
        int p = 0;
        final int branchNumber = (int) Math.pow(2, level - 1);
        int endP = halfCols_dec;
        int d = (int) Math.pow(2, expand + 1);
        for (int i = 1; i < level; ++i) {
            d /= 2;
            endP -= d;
        }
        if (separate) {
            final int dd = repeat - repeatCounter + 1;
            endP += d - dd;
            for (; p < endP; ++p) {
                sb.append('_');
            }
            sb.append('1');
            ++p;
            for (int i = 1; i < branchNumber; ++i) {
                if (i % 2 == 1) {
                    endP = p + dd * 2 - 1;
                } else {
                    endP = p + d * 4 - 1 - dd * 2;
                }
                for (; p < endP; ++p) {
                    sb.append('_');
                }
                sb.append('1');
                ++p;
            }
        } else {
            for (; p < endP; ++p) {
                sb.append('_');
            }
            sb.append('1');
            ++p;
            for (int i = 1; i < branchNumber; ++i) {
                endP = p + d * 2 - 1;
                for (; p < endP; ++p) {
                    sb.append('_');
                }
                sb.append('1');
                ++p;
            }
        }
        for (; p < cols; ++p) {
            sb.append('_');
        }
        output.add(sb.toString());
        if (--repeatCounter == 0) {
            separate = !separate;
            if (separate) {
                ++level;
            } else {
                if (level == maxLevel + 1) {
                    break;
                }
                repeat /= 2;
                if (repeat == 0) {
                    break;
                }
            }
            repeatCounter = repeat;
        }
    }
    while (--r >= 0) {
        final StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cols; ++i) {
            sb.append('_');
        }
        output.add(sb.toString());
    }

    return output.toArray(new String[rows]);
}

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}