# [2019q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 9 週測驗題
:::info
目的: 檢驗學員對 C 語言程式設計的認知
:::

---

### 測驗 `1`

碎形是相當有趣的題材，參見影片 [隨機過程產生的完美圖騰](https://youtu.be/kfXl5fsVBVY)
。

考慮以下 [Sierpiński triangle](https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle) 的實作程式碼 (`tri.c`):

#include <stdio.h>
#define S 78
#define SPACE (char) 32

static int out[S][S] = {0};
int triangle(int i) {
    static int j = 0;
    out[0][S/2] = KK1;
    for (; i < S; i++)
        out[j + KK2][i + KK3] = putchar(SPACE | (out[j][i + KK4] ^ out[j][i]));
    if (++j < 31)
        return triangle(puts(""));
    return 0;
}

int main() {
    return triangle(1);
}

假設終端機至少寬 81 個字元，高 44 個字元，且字型都為等寬等高，上述程式碼在執行時期可輸出下方的 [ASCII Art](https://www.asciiart.eu/)，其中白色前景為 `!` (驚嘆號) 字元:

請補完程式碼。

參考資料:
1. [碎形專題 一 從 Cantor 集到碎形](https://web.math.sinica.edu.tw/math_media/d251/25101.pdf)
2. [碎形之 Sierpinski 三角形](https://openhome.cc/Gossip/OpenSCAD/Fractal.html)
3. [遞迴、碎形與數學](https://www.ithome.com.tw/voice/110732)
4. [碎形影像壓縮](https://activity.ntsec.gov.tw/activity/race-1/38/pdf/38h/222.pdf) / [圖像處理: 碎形壓縮](https://www.twblogs.net/a/5c224b1dbd9eee16b4a776b4)
> 人家高中就懂這麼多，我們繼續在學店有搞頭嗎？

==作答區==

KK1 = ?
* `(a)` (-2)
* `(b)` (-1)
* `(c)` 0
* `(d)` 1
* `(e)` 2

KK2 = ?
* `(a)` (-2)
* `(b)` (-1)
* `(c)` 0
* `(d)` 1
* `(e)` 2

KK3 = ?
* `(a)` (-2)
* `(b)` (-1)
* `(c)` 0
* `(d)` 1
* `(e)` 2

KK4 = ?
* `(a)` (-2)
* `(b)` (-1)
* `(c)` 0
* `(d)` 1
* `(e)` 2

:::success
延伸問題:
1. 解釋程式運作原理，指出原程式的缺失並強化;
2. 研讀 [碎形呈現演算法](http://rportal.lib.ntnu.edu.tw/bitstream/20.500.12235/93120/3/020903.pdf)，嘗試透過 PNG 或 SVG 輸出 [Sierpiński triangle](https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle) 連續延伸的圖片;
3. 改寫上述程式碼為非遞迴，即 iterative 形式;
:::

---