通过欧拉计划学Rust编程（第73题）

由于研究Libra等数字货币编程技术的需要，学习了一段时间的Rust编程，一不小心刷题上瘾。

刷完欧拉计划中的63道基础题，能学会Rust编程吗？

“欧拉计划”的网址：https://projecteuler.net

英文如果不过关，可以到中文翻译的网站：http://pe-cn.github.io/

这个网站提供了几百道由易到难的数学问题，你可以用任何办法去解决它，当然主要还得靠编程，编程语言不限，论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法，当然如果你直接用google搜索答案就没任何乐趣了。

这次解答的是第73题：https://projecteuler.net/problem=73

题目描述：

统计一定范围内的分数

考虑形如n/d的分数，其中n和d均为正整数。如果n < d且其最大公约数为1，则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出，我们得到：

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 可以看出在1/3和1/2之间有3个分数。

将d ≤ 12,000的最简真分数构成的集合排序后，在1/3和1/2之间有多少个分数？

请

先

不

要

直

接

看

答

案

，

最

好

自

己

先

尝

试

一

下

。

解题过程：

遇到一个复杂的问题，可以先尝试解决简单的情况，然后慢慢逼近最终的问题。

第一步： 直接根据题意，暴力求解

1/3 < n/d < 1/2

可以推导出 2 * n < d && d < 3 * n

找到最大公约数后，求出真分数，放在一个集合里。

let mut count = 0;
let mut v:Vec<(usize, usize)> = vec![];
for d in 2..=1200 {
    for n in 1..d {
        if 2 * n < d && d < 3 * n {
            let g = num::integer::gcd(n, d);
            let r = (n / g, d / g);
            if !v.contains(&r) {
                v.push(r);
                count += 1;
            }
        }
    }
}
println!("{}", count);

当d为1000时，可以很容易地计算出结果。但当d逐渐增大时，求解速度越来越慢，主要原因是数组中元素越来越多，判断一个元素是否在数组中，速度越来越慢。

第二步：

找最大公约数，并且维护一个庞大的数组，代价较大，当找到一个真分数时，可以排除掉很多(n,d)，比如找到2/5时，可以排除4/10, 6/15, ... , 4800/12000。

针对[1, 12000]中的每一个d，维护一个exclude_list数组，其中的元素约分后都已经统计过了，可以直接忽略掉。

let mut exclude_list = vec![vec![]; 12001];

let mut count = 0;
for d in 2..=12000 {
    for n in 1..d {
        if 2 * n < d && d < 3 * n
            && !exclude_list[d].contains(&n) {
            count += 1;
            for i in 2..=12000 / d {
                exclude_list[d * i].push(n * i);
            }
        }
    }
}
println!("{}", count);

4秒得到结果。

当d更大时，还可以进一步优化算法，这里不再讨论。

--- END ---