1

我遇到了一个用递归绘制谢尔宾斯基三角形的程序。我如何解释这段代码是调用 sierpinski1 直到 n == 0，然后只绘制 3 个小三角形（每次调用一个三角形），因为 n == 0 是绘制某些东西的唯一情况（panel.canvas.create_polygon） . 但是，这不是代码的工作方式，因为在运行时会绘制取决于 n 的三角形数量，而不仅仅是我认为会显示的 3 个小三角形。

有人可以向我解释当函数 sierpinski1 只有一个条件时可以绘制多少东西吗？这是我无法理解的程序的一部分。我在递归上查找了所有可能的信息，但没有任何信息可以解释为什么这种递归格式有效。

def sierpinski(n):
    x1 = 250
    y1 = 120
    x2 = 400
    y2 = 380
    x3 = 100
    y3 = 380
    panel = DrawingPanel(500,500)
    sierpinski1(n,x1,y1,x2,y2,x3,y3,panel)

def sierpinski1(n,x1,y1,x2,y2,x3,y3,panel):
    if n == 0:
        panel.canvas.create_polygon(x1,y1,x2,y2,x3,y3, fill = 'yellow', outline = 'black')
    else:
        sierpinski1(n-1,x1,y1,(x1+x2)/2,(y1+y2)/2,(x1+x3)/2,(y1+y3)/2, panel)
        sierpinski1(n-1,(x1+x3)/2,(y1+y3)/2,(x2+x3)/2,(y2+y3)/2,x3,y3,panel)
        sierpinski1(n-1,(x1+x2)/2,(y1+y2)/2,x2,y2,(x2+x3)/2,(y2+y3)/2,panel)
4

3 回答 3

3

这就是递归的工作原理：有一个基本情况，也有一个递归情况。由于递归使用 LIFO 结构（例如调用堆栈），我们必须知道何时停止向堆栈添加调用。

基本情况：

  • 发生时n == 0
  • 执行实际的绘图动作
  • 意味着没有更多的三角形要生成，所以开始绘制它们就可以了。

递归情况：

  • 发生在什么时候n > 0（严格来说，什么时候n < 0）
  • 对自身进行三个不同的调用，每个调用都有不同的 x1、x2、y1 和 y2 值。
  • 意味着还有更多的三角形要生成。

像这样想。要绘制的三角形的数量由以下公式 T 给出：

如果 n 大于 0，则 x = 3 到 n 的 T，否则为 0。

这适用于简单的三角形：如果 n = 1，则只绘制三个三角形。如果 n = 2，则绘制 9，依此类推。

为什么会起作用？调用堆栈在 其中起着重要作用。

为简洁起见，这里是 n = 1 的迹线：

sierpinski1(n,x1,y1,x2,y2,x3,y3,panel)
    condition n = 0 FAILS
    sierpinski1(n-1,x1,y1,(x1+x2)/2,(y1+y2)/2,(x1+x3)/2,(y1+y3)/2, panel)
        condition n = 0 PASSES
        panel.canvas.create_polygon(x1,y1,x2,y2,x3,y3, fill = 'yellow', outline = 'black')
    sierpinski1(n-1,(x1+x3)/2,(y1+y3)/2,(x2+x3)/2,(y2+y3)/2,x3,y3,panel)
        condition n = 0 PASSES
        panel.canvas.create_polygon(x1,y1,x2,y2,x3,y3, fill = 'yellow', outline = 'black')
    sierpinski1(n-1,(x1+x2)/2,(y1+y2)/2,x2,y2,(x2+x3)/2,(y2+y3)/2,panel)
        condition n = 0 PASSES
        panel.canvas.create_polygon(x1,y1,x2,y2,x3,y3, fill = 'yellow', outline = 'black')

因此，对于 n = 1，恰好绘制了三条线。对于更高的值n，在伪代码高级别的情况下会变得更棘手，但同样的原则也适用。

于 2013-08-11T23:40:47.150 回答
1

仅当 n = 0 时才绘制事物，但如果使用 n = 1 调用它，则使用 n = 0 对其进行三个单独的调用。类似地，如果使用 n = 2 调用它，则对其进行三个调用当 n = 1 时，每一个都会在 n = 0 的情况下对其进行 3 次调用，总共有 9 个绘图。一般来说，随着调用次数每层乘以3，用n调用时会画出3^n个小三角形。

于 2013-08-11T23:27:41.590 回答
1

有人可以向我解释当函数 sierpinski1 只有一个条件时可以绘制多少东西吗？

因为该函数在每个非零步骤中进行三个递归调用。这意味着对于每一个n大于 0 的值，函数都会分支到三个不同的路径，其值n小于 1。您最终将达到3 n次n=0的总数。

于 2013-08-11T23:28:44.350 回答