遞歸算法——BOX FRACTAL 盒分形（POJ2083）

遞歸算法——BOX FRACTAL 盒分形（POJ2083）

問題

盒分形定義如下：
1度的盒分形為：
X
2度的盒分形為：
X X
X
X X

如果B(n-1)表示n-1度的盒分形，則n度的盒分形遞歸定義如下：

B(n-1) B(n-1)
B(n-1)
B(n-1) B(n-1)

請畫出n度的盒分形的圖形

輸入

每行給出一個不大於7的正整數。輸入的最後一行以-1表示輸入結束

輸出

對於每個測試用例，出書用’X’標記的盒分形。在每個測試用例後輸出包含一個短劃線“-”的一行。

分析

n度的盒分形的規模為3^(n-1),即n度的盒分形圖為一個長寬為3^(n-1)的正方形。
設置遞歸函數printBox(n,x,y)生成以坐標（x,y）為左上角的n度盒分形。

1）遞歸邊界： 若n=1,則在（x,y）輸出‘X’
2）若n>1,則計算n-1度的盒子的規模 m = 3^(n-2),分別在左上方， 右上方，中間，左下方和右下方畫出5個n-1度的盒子。
對於左上方的n-1度的盒子，左上角的坐標為（x,y）,遞歸printBox(n-1,x,y)生成；
對於右上方的n-1度的盒子，左上角的坐標為（x+2m,y）,遞歸printBox(n-1,x+2m,y)生成；
對於中間的n-1度的盒子，左上角的坐標為（x+m,y+m）,遞歸printBox(n-1,x+m,y+m)生成；
對於左下方的n-1度的盒子，左上角的坐標為（x,y+2m）,遞歸printBox(n-1,x,y+2m)生成；
對於右上方n-1度的盒子，左上角的坐標為（x+2m,y+2m）,遞歸printBox(n-1,x+2m,y+2m)生成；

編碼實現

#include "stdafx.h"
#include 
#include 
using namespace std;
//7度盒分形 最大規模n=3^6=729
#define MAX 730

char maps[MAX][MAX];

void printBox(int n, int x, int y)
{
    //遞歸邊界
    if (n == 1){
        maps[x][y] = 'X';
    }
    else{
        //n-1度盒分形的規模m
        int m = pow(3, n - 2); 
        //左上方的n-1度盒分形
        printBox(n - 1, x, y);
        //右上方的n-1度盒分形
        printBox(n-1, x+2*m, y);
        //中間的n-1度盒分形
        printBox(n - 1, x , y + 2 * m);
        //左下方的n-1度盒分形
        printBox(n - 1, x + m, y + m);
        //右下方的n-1度盒分形
        printBox(n-1,x+2*m,y+2*m);


    }

}

int _tmain(int argc, _TCHAR* argv[])
{
    int n ;
    cin >> n;
    while (n != -1){
        int size = pow(3, n - 1);
        //初始化
        for (int i = 0; i < size; i++){
            for (int j = 0; j < size; j++){
                maps[i][j] = ' ';
                maps[i][size] = '\0';
            }
        }
        printBox(n, 0, 0);
        //輸出
        for (int i = 0; i < size; i++)
            printf("%s\n", maps[i]);
        cout << "-"<> n;
    }

    return 0;
}

測試