毕达哥拉斯树

今天的 Project Euler 是关于求毕达哥拉斯树的面积极限。鉴于现在还早,贴答案太不好了,不过还是可以看看这个东西。

毕达哥拉斯树 (Pythagoras Tree) 的构造过程,就是先给定一个单位正方形,把正方形的顶边作为一个直角三角形的斜边,然后两个直角边各扩展出一个正方形。接下来这两条直角边的正方形对边再作为斜边继续扩展,如此无穷迭代下去得到的。与其说是树,我觉得它倒更像一朵花菜…

很显然扩展出去的两个正方形的面积之和就等于斜边上这个正方形的面积,所以每扩展一次,总面积就会增加一个单位正方形,所以是会趋于无穷大。然而迭代到一定程度之后,这些枝干就开始互相重叠,到了最后这个总覆盖面积还是有限的。但是,似乎这个极限并没有简便的解法。

比如让两条直角边和斜边分别是 3、4、5,我们迭代 15 次之后得到的图形是这个样子的:

Pythagoras Tree

这个图是用 MetaPost 画的,代码很直观,就是旋转,画方形,然后迭代。我把代码放在这里,想要高清大图的可以看这个 PDF

def drawsq(expr a, b, n) =
  fill a -- 1[a,b] rotatedabout(a, 90) -- 1[b,a] rotatedabout(b, -90) -- b -- cycle withcolor (0.8-n/20) * white;
enddef;

def ptree(expr a, b, n) =
  begingroup
    drawsq (a,b,n);
    if n > 0:
      save na, nb, e; pair na, nb, e;
      na = 1 [a,b] rotatedabout(a, 90);
      nb = 1 [b,a] rotatedabout(b, -90);
      e = 0.8 [na,nb] rotatedabout(na, angle(4,3));
      ptree (na, e, n-1);
      ptree (e, nb, n-1);
    fi
  endgroup
enddef;

beginfig(0);
  ptree((9cm, 3cm), (10cm, 3cm), 15);
endfig;
end.

这看起来很简单哈,而用画好之后,只要用 eps2eps 取一下 BoundingBox,不就求出面积了吗?很遗憾,对于迭代十几层还可以操作,一旦到了几十层,这 ( 2^n) 个小方块可实在是算不过来啦。不光是 MetaPost 不行,别的语言也搞不定呀。

不过只要观察一下这个树,就知道其实很多枝叶根本不会扩展面积边界,那么对于这些就不用算了。只要选择一个比较好的条件来限制计算量,这个东西算起来还是很快的。代码见这里,怕剧透的同学就不要点开了。

2 thoughts on “毕达哥拉斯树

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据