首页 > 技术相关 > 毕达哥拉斯树

毕达哥拉斯树

2012年9月23日 发表评论 阅读评论

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

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

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

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

Pythagoras Tree

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

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

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

  1. 111111
    2012年9月27日16:25 | #1

    你可以把代码移除吗? 任何人都可以搜寻到你的文章,,用这里的代码得到答案,这样等于让人作弊, 希望你可以把他移除, 谢谢

  2. 2012年9月28日01:02 | #2

    @111111 你好,网上也有一些其他收集 PE 答案的网站,如果照抄答案也可以得到论坛里的程序。我觉得是否拿来作弊是个人选择,交流一个想法并没有什么不好,你说呢

  1. 本文目前尚无任何 trackbacks 和 pingbacks.

%d 博主赞过: