今天的 Project Euler 是关于求毕达哥拉斯树的面积极限。鉴于现在还早，贴答案太不好了，不过还是可以看看这个东西。
毕达哥拉斯树 (Pythagoras Tree) 的构造过程，就是先给定一个单位正方形，把正方形的顶边作为一个直角三角形的斜边，然后两个直角边各扩展出一个正方形。接下来这两条直角边的正方形对边再作为斜边继续扩展，如此无穷迭代下去得到的。与其说是树，我觉得它倒更像一朵花菜…
很显然扩展出去的两个正方形的面积之和就等于斜边上这个正方形的面积，所以每扩展一次，总面积就会增加一个单位正方形，所以是会趋于无穷大。然而迭代到一定程度之后，这些枝干就开始互相重叠，到了最后这个总覆盖面积还是有限的。但是，似乎这个极限并没有简便的解法。
比如让两条直角边和斜边分别是 3、4、5，我们迭代 15 次之后得到的图形是这个样子的：
这个实际上是上个星期的 Project Euler 题目——我也知道贴答案不好，但是这个问题实在很有意思：给定一个单位圆，在 [-1, 1] x [-1, 1] 里面插入 N 条线，如果小单元和单位圆重叠就标为红色，否则标为黑色。找出让红色区域最小的划分方法。我在 N = 16 时候的解是这个样子的：
Continue reading “最小误差的矩形网格”
This is a Python solution for Project Euler #96, to find the solution for sudokus.
The speed is modest (0.750s with pypy on Windows 7 @ i5 2.60GHz), but the code is relatively short and hopefully the idea is clear. Enjoy.
1. Find candidates for all items. If only one exists for a blank, fill it in.
2. Note down the blank with least but more than one candidates.
3. Copy the matrix and trial the candidates recursively until all blanks are filled.
Continue reading “Sudoku Solution – Project Euler #96”
