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

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

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

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

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

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

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

题目描述：

2 ^ 7 = 128，在2的n次方中，首次遇到前2位数字为“12”，下一次再遇到“12”的情况是2 ^ 80。

考虑2 ^ j 用10进制表示，定义p(L, n)为第n个满足前导数字为L的最小 j 值。

即有：

p(12,1)=7

p(12,2)=80

我们已知 p(123,45)=12710，求p(123, 678910)。

请

先

不

要

直

接

看

答

案

，

最

好

自

己

先

尝

试

一

下

。

解题过程：

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

第一步：

首先用excel演算一下。

能够很快找到规律，前导的两位数字可以比较容易的计算出来。

第二步：

最近，看了吴军的《格局》这本书，他说草稿纸别用烂乎乎的已经写满内容的废纸，严重干扰作题思路，得不偿失。选用干净整洁的稿纸，把演算过程写清楚，方便备查。于是就从网上找了一款比较便宜的方格本，尽量把字迹写得不那么潦草。

数学推导的过程并不复杂，需要一点点对数方面的知识。

先用已知的2个答案检查算法的正确性。

let mut count = 0;
for n in 7..100 {
    let t = (n as f64) * 2_f64.log10();
    let m = t - t.floor() + 1.0;
    let m = 10_f64.powf(m).floor() as u64;
    if m == 12 {
        count += 1;
        println!("p(12, {}) = {} ", count, n);
        if count == 1 {
            assert_eq!(n, 7, "p(12,1) = 7");
        }
        if count == 2 {
            assert_eq!(n, 80, "p(12,2) = 80");
        }
    }
}

第三步

前导数字为123，公式稍微有一点点变化，t - t.floor() + 1 变成t - t.floor() + 2，然后暴力求解最终的问题即可，根据机器性能，需要几秒到几十秒的时间。

let mut count = 0;
for n in 7.. {
    let t = (n as f64) * 2_f64.log10();
    let m = t - t.floor() + 2.0;
    let head = 10_f64.powf(m) as u64;
    if head == 123 {
        count += 1;
        println!("p(123, {}) = {} ", count, n);
        if count == 45 {
            assert_eq!(n, 12710, "p(123, 45) = 12710");
        }
        if count == 678910 {
            break;
        }
    }
}