題目描述
____________________________________________________________________________________________________ __________________1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1___________________ ___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________ ___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________ ____________________1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____________________ _____________________1_______1_______1_______1_______1_______1_______1_______1______________________ _____________________1_______1_______1_______1_______1_______1_______1_______1______________________ _____________________1_______1_______1_______1_______1_______1_______1_______1______________________ ______________________1_____1_________1_____1_________1_____1_________1_____1_______________________ _______________________1___1___________1___1___________1___1___________1___1________________________ ________________________1_1_____________1_1_____________1_1_____________1_1_________________________ _________________________1_______________1_______________1_______________1__________________________ _________________________1_______________1_______________1_______________1__________________________ _________________________1_______________1_______________1_______________1__________________________ _________________________1_______________1_______________1_______________1__________________________ _________________________1_______________1_______________1_______________1__________________________ __________________________1_____________1_________________1_____________1___________________________ ___________________________1___________1___________________1___________1____________________________ ____________________________1_________1_____________________1_________1_____________________________ _____________________________1_______1_______________________1_______1______________________________ ______________________________1_____1_________________________1_____1_______________________________ _______________________________1___1___________________________1___1________________________________ ________________________________1_1_____________________________1_1_________________________________ _________________________________1_______________________________1__________________________________ _________________________________1_______________________________1__________________________________ _________________________________1_______________________________1__________________________________ _________________________________1_______________________________1__________________________________ _________________________________1_______________________________1__________________________________ _________________________________1_______________________________1__________________________________ _________________________________1_______________________________1__________________________________ _________________________________1_______________________________1__________________________________ _________________________________1_______________________________1__________________________________ __________________________________1_____________________________1___________________________________ ___________________________________1___________________________1____________________________________ ____________________________________1_________________________1_____________________________________ _____________________________________1_______________________1______________________________________ ______________________________________1_____________________1_______________________________________ _______________________________________1___________________1________________________________________ ________________________________________1_________________1_________________________________________ _________________________________________1_______________1__________________________________________ __________________________________________1_____________1___________________________________________ ___________________________________________1___________1____________________________________________ ____________________________________________1_________1_____________________________________________ _____________________________________________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型分支的碎形樹，不可以將排好的文字寫入程式碼內直接輸出。為了避免讓樹無限制增長，將會輸入一個數字表示樹成長和分支的次數。
原題網址
輸入格式
輸入只有一行整數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]);
}
上圖是以下程式的執行結果：
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}