谢尔宾斯基三角形能用编程写出来么？该怎么写？

谢尔宾斯基三角形能用编程写出来么？该怎么写？

来个Haskell版本, 这个版本的特点是, 不需要开一个 n^2 的数组来表示画布的状态, 而是通过对 "图形" 做抽象, 并且实现几个基本的 图形上的 "组合运算", 最后通过图形的组合运算得到结果. 因此写这个代码的过程中, 没有太多的trick (不需要关心数组越界, 没有什么magic number).

另外由于图形的每个具体像素的值都是在输出的时候才产生 (通过 draw 这个函数), 所以相较于其它答主开一个n方的canvas数组来保存图形的 push 的方式来说, 这里用的是一种 pull 的模式. 因为用的是这种pull的模式, 我们能表达出无限大的图形, 而把所有具体的计算都留在了图形输出的时候.

也因为这种pull的方式, 这段代码的空间复杂度比较低 (这里对空间的需求取决于函数调用栈的深度, 空间复杂度为 O(log n)), 而时间复杂度则较高 (为 O(n^2 * log n)), 其中 n 为三角形的边长.

完整代码如下:

运行效果:

稍微说一下:

这里做了几个抽象:

1. 点 和 向量: type Point = (Int, Int), type Vec = (Int, Int); 为了简单直接用tuple表示点和向量.

2. 矩形: type Rect = (Point, Vec); 这里用矩形的左上角坐标表示位置, 用左上角到右下角的向量表示矩形的尺寸.

3. 图形: type Graph = Point -> Pixel; 注意这里把图形定义为了一个 "点到像素的函数".

4. 像素: type Pixel = String; 因为是在控制台上画图, 所以把像素定义为字符串.

然后基于上述抽象, 定义了几个图形上的运算:

1.. 图形上的平移运算: move :: Vec -> Graph -> Graph , 即把给定图形按照给定向量移动, 得到新图形

2. 图形上的嵌入运算: inset :: Rect -> Graph -> Graph -> Graph, 即把给定图形的指定部分嵌入到另一个图形中, 返回新的图形

3. 图形的绘制: draw :: Rect -> Graph -> IO () , 即绘制给定图形的给定区域

然后核心代码就是下面这几行:

其中第一行就是说, 0阶sierpinskiTriangle就是一个simpleTriangle.

第二行及后面就是计算了一些参数, 最后返回一个图形的表达式:

其中 t 是 n-1 阶的 sierpinskiTriangle,

h 是 n-1 阶 sierpinskiTriangle 的高度,

sz 是 n-1 阶 sierpinskiTriangle 的尺寸, 这里用一个图形的BBox左上角到右下角的向量表示.

lpos 和 rpos 分别是左下角三角形 和 右下角三角形的位置

整句话就是说, 在 最上方的 n-1 阶 sierpinskiTriangle 上嵌入右下角的 n-1 阶 sierpinskiTriangle, 然后嵌入左下角的 n-1 阶 sierpinskiTriangle . 然后就得到 n 阶 sierpinskiTriangle 了.