Python面试算法：绘制谢尔宾斯基三角形
什么是谢尔宾斯基三角形呢？先看下面的图：
这里加上所有的三角形都是等边三角形
以上就是一个6级的谢尔宾斯基三角形。也就是三角形有6个尺寸，最大的是最外面的一个三角形，最大。再下一个级别的就是里面的4个三角形（中间的是粉色的）。如下图就是左下角的三角形。这是第2级（级别越大尺寸越小）。
再下一级就是更小的三角形，如下图，就是上图左下角的三角形，这是第3级三角形，以此类推，直到级别为6为止。
我们可以观察这个三角形，很明显，每一个三角形（除了最小的6级三角形外）中都有4个更小的三角形。而绘制三个角的小三角形，那么中间的三角形自然就形成了。所以我们只需要绘制除了6级三角形外的其他三角形中三个角的小三角形即可。由于每一个三角形都会重复同一个动作（绘制三个更小的三角形），这明显是递归动作。
递归的基本流程如下：
step1：绘制大三角形
step2：绘制大三角形中三个顶点的小三角形
step3：重复step1，将大三角形看做step2绘制的小三角形，继续绘制这个小三角形中三个顶点的小三角形，直到级别为6为止（最小的三角形），这是递归终止条件。
根据前面的算法描述，可以编写出如下的绘制谢尔宾斯基三角形。
# points表示当前绘制的大三角形的三个顶点，degree表示当前的度，或者级别，必须大于0，才继续绘制，myTurtle是还会作图对象
def sierpinski(points,degree,myTurtle):
colormap = ['blue','red','green','yellow','white','orange']
# 绘制大三角形，从颜色列表中根据degree选择一种颜色
draw_triangle(points,colormap[degree - 1], myTurtle)
if degree > 0:
# 绘制左下角三角形
sierpinski([points[0],get_middle(points[0],points[1]),get_middle(points[0],points[2])],degree - 1,myTurtle)
# 绘制上方的三角形
sierpinski([points[1], get_middle(points[0], points[1]), get_middle(points[1], points[2])],degree - 1,myTurtle)
# 绘制右下角三角形
sierpinski([points[2], get_middle(points[2], points[1]), get_middle(points[0], points[2])],degree - 1,myTurtle)上面的代码涉及到如下两个函数，其中get_middle函数用于获取三角形两个顶点的中间点，draw_triangle函数用于通过海龟对象绘图。海龟对象是Python内置的模块，需要导入turtle。使用方法请参阅相关的文档。这两个函数以及调用代码如下：
import turtle
# 绘制一个三角形
def draw_triangle(points, color,myTurtle):
myTurtle.fillcolor(color)
myTurtle.up()
myTurtle.goto(points[0][0],points[0][1])
myTurtle.down()
myTurtle.begin_fill()
# 绘制左边
myTurtle.goto(points[1][0],points[1][1])
# 绘制右边
myTurtle.goto(points[2][0], points[2][1])
# 绘制底边
myTurtle.goto(points[0][0], points[0][1])
myTurtle.end_fill()
# 用于获取两个点的中间点
def get_middle(p1,p2):
return ((p1[0] + p2[0])/2,(p1[1] + p2[1])/2)
# 调用代码
myTurtle = turtle.Turtle()
window = turtle.Screen()
# 最大三角形的3个顶点坐标
points = [[-200,-100],[0,200],[200,-100]]
# 开始绘制三角形，其实degree为5，直到减小到0为止
sierpinski(points,5,myTurtle)
# 将海龟画笔抬起，否则移动海龟画笔会一直绘制直线。
myTurtle.up()
# 将海龟画笔移动到200，200的位置，以便原理绘制好的三角形
myTurtle.setpos(200,200)
# 显示海龟绘图窗口，绘制完后，单击关闭窗口
window.exitonclick()本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-11-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读