project euler 73

medie2005

farey sequence.

medie2005

很简单，因为我们本来就不需要最简形式。我们只需要遍历区间中的所有互异分数就可以了。
a/b<(a+c)/(b+d)<c/d.
(a/b,c/d)=(a/b,(a+c)/(b+d)) + (a+c)/(b+d) + ((a+c)/(b+d), c/d) .
于是, 得到了递归式.

[ 本帖最后由 medie2005 于 2009-4-23 21:43 编辑 ]

wayne

为了方便理解递归过程的具体细节，我用Mathematica实现了一下：

我有意把迭代的深度上限设成20。这个时候对于深度大于20的调用Mathematica会不运行，而直接返回调用函数的本身，即出现附件所示现象。