POJ 1941 Sierpinski Fractal 遞歸繪製

題目概述

POJ 1941 要求繪製謝爾賓斯基三角形分形。給定階數 n，輸出由 /、\ 和 _ 組成的 ASCII 藝術圖形。圖形高度為 2^n，寬度為 2^(n+1)。

核心思路：遞歸構建

謝爾賓斯基三角形具有自相似性：階數 n 的圖形由三個階數 n-1 的子三角形組成，分別位於頂部、左下、右下。遞歸基礎情況 n=1 直接填充最小單元：

 /\
/__\

演算法詳解

1. 預計算 2 的冪次：pow2[i] = 2^i，用於快速定位子三角形的偏移量。
2. 遞歸函數 print(x, y, n)：
   • (x, y) 為當前三角形左上角坐標
   • 若 n==1，填充基本單元
   • 否則遞歸繪製三個子三角形：
     • 頂部：print(x, y + pow2[n-1], n-1)
     • 左下：print(x + pow2[n-1], y, n-1)
     • 右下：print(x + pow2[n-1], y + pow2[n], n-1)
3. 輸出：遍歷字符數組，逐行列印。

代碼實現（C++）

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_W = 2048;
const int MAX_H = 1024;
int pow2[32];
char canvas[MAX_H + 10][MAX_W + 10];

void draw(int x, int y, int n) {
    if (n == 1) {
        canvas[x][y+1] = '/';
        canvas[x][y+2] = '\\';
        canvas[x+1][y] = '/';
        canvas[x+1][y+1] = '_';
        canvas[x+1][y+2] = '_';
        canvas[x+1][y+3] = '\\';
        return;
    }
    draw(x, y + pow2[n-1], n-1);           // 頂部
    draw(x + pow2[n-1], y, n-1);           // 左下
    draw(x + pow2[n-1], y + pow2[n], n-1); // 右下
}

int main() {
    pow2[0] = 1;
    for (int i = 1; i < 30; ++i) pow2[i] = pow2[i-1] * 2;

    int n;
    while (cin >> n && n) {
        int H = pow2[n];
        int W = pow2[n+1];
        memset(canvas, ' ', sizeof(canvas));
        draw(0, 0, n);
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) cout << canvas[i][j];
            cout << '\n';
        }
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(4^n) —— 每階產生 3 個子問題，總單元數約為 3^n
• 空間複雜度：O(2^n × 2^(n+1)) —— 畫布大小

關鍵點總結

• 利用分形自相似性，遞歸分解問題
• 座標偏移計算需精確，pow2 陣列避免重複計算
• 畫布初始化為空格，避免輸出雜訊