你将如何在 C 中生成谢尔宾斯基三角形（递归）

Question

我想知道如何在 C 中递归地生成一定深度的 Sierpinski 三角形。

我写这个函数是为了从顶点的坐标 (x,y) 生成一个由 * 组成的高度为 h 的三角形。

void triangle(char display[100][100],int x, int y, int h) {
    
    for (int row = y; row<=h-1+y; row++) {
        for (int column = x; column<=2*(row+1-y)+x-2; column++) {
            display[row][column-(row+1-y)+1] = '*';
        }
    }
    
    for (int i = 0 ; i<100 ; i++) {
        for (int j = 0; j<100; j++) {
            if (display[i][j]=='[=10=]')
                display[i][j]=' ';
        }
    }

    
    
}

使用此代码，我可以“手动”生成 Sierpinski 三角形。但我想递归地做，对于任何深度和高度（高度可被 2^(depth) 整除）。

int main()
{
    char display[100][100] = { {0} };

    triangle(display, 20, 0, 5);
    
    triangle(display, 15, 5, 5);
    triangle(display, 25, 5, 5);
    
    triangle(display, 10, 10, 5);
    triangle(display, 30, 10, 5);
    
    triangle(display,  5, 15, 5);
    triangle(display, 15, 15, 5);
    triangle(display, 25, 15, 5);
    triangle(display, 35, 15, 5);
    

    for (int i=0 ; i<100; i++) {
        printf("\n");
        for (int j=0; j<100; j++) {
            printf("%c", display[i][j]);
        }
    }
}

这是我上面代码的输出：

Answer 1

这不是谢尔宾斯基三角形，只是看起来很像。您正在绘制单独的小三角形（作为副作用，它在这些三角形之间有间隙 -> "...*** ***...".

想象如何创建这样一个三角形的最佳方法是拿一支铅笔和一张纸（有创建三角形的优化版本，但机械方法适合作为开始）：

选择一个深度（比如说：3）
画一个三角形（最好是等边的，谁都可以）
(if depth = 0 then RETURN from here, otherwise continue)
减少深度
将所有边减半并标记这些点（用于视觉辅助）
连接这些点，您将看到 4 个相等的较小三角形
Select 小三角形 #1
调用第 3 行
Select 小三角形 #2
调用第 3 行
Select 小三角形 #3
调用第 3 行
Select 小三角形 #4
调用第 3 行

在流程的某个地方，您需要管理从正整数开始的 depth 的状态。 “调用第 3 行”通常是一个子程序，它在输入时保存状态，并在 returned 时恢复状态。你必须减少递归调用之间的深度并检查它是否为 0，当你达到 0 时，你必须 RETURN。它可以是一个全局变量（更容易理解但丑陋），也可以是绘图函数的参数（nice）。

这个“select 较小的三角形 #x 和呼叫线 3。”是自递归调用。 Selecting一个三角形只是从大三角形计算小三角形的固有坐标。

如果深度大于 1，则递归性质开始。代码将检查深度（如果达到 0，则 return），细分原始三角形，在第一个较小的三角形上调用自身，有效处理这个较小的三角形，就好像它是原来的大三角形一样（函数本身没有“大”和“小”的概念）。

你将如何在 C 中生成谢尔宾斯基三角形（递归）

How would you generate a Sierpinski Triangle in C (recursively)

c

recursion

fractals