专栏首页申龙斌的程序人生通过欧拉计划学Rust编程(第684题)

通过欧拉计划学Rust编程(第684题)

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

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

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

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

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

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

题目描述:

定义s(n)是数字和为n的最小整数,例如s(10)=19。

记S(k) = s(1) + s(2) + ... + s(k),可以知道 S(20)=1074。

设斐波那契数列f(n)按如下方式定义:

求:

解题过程:

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

第一步:

题目中知道S(20)=1074,那就先求S(20)。

手算前20个,发现一个规律。每9个为一组,后面的数字是9,前面的数字从0到8。

可以推导出一个公式:s(n) = (a+1) * 10 ^ b - 1

S(20)很容易求出来:

let mut ss = 0;
for n in 1..=20 {
    let a = n % 9;
    let b = n / 9;
    let s = (a + 1) * 10_u32.pow(b) - 1;
    println!("{}", s);
    ss += s;
}
println!("S(20): {}", ss);

但求S(200)时就会溢出,因为 10 ^ b是一个超出u64范围的大整数。

第二步

把90个斐波那契数求出来,以后要用。

let mut fib = [0_u64; 91];
fib[1] = 1;
for i in 2..=90 {
    fib[i] = fib[i - 1] + fib[i - 2];
    println!("fib({}): {}", i, fib[i]);
}

运行一下,可以发现第90个数非常非常大。

fib(88): 1100087778366101931
fib(89): 1779979416004714189
fib(90): 2880067194370816120

第三步

首先能够想到的是用大整数库num-bigint优化算法。

fn fs(n: u64) -> u64 {
    let a = n % 9;
    let b = n / 9;
    let mut s = BigUint::from(a + 1);
    for i in 0..b {
        s = s * BigUint::from(10_u64);
    }
    s = s - BigUint::from(1_u64);
    let result = s % BigUint::from(1_000_000_007_u64);
    result.to_string().parse::<u64>().unwrap()
}

现在可以比较快地计算出s(20000)和S(20000),但离目标2880067194370816120还有相当大的距离,bigint这条路不通,还得改进算法。

第四步

看看S(n)的计算是否还有其它规律。每9个为一组,计算9个数之和,可以找到规律。

可以发现,当n = 9 * m - 1时,有公式:

S(n) = 5 * 10 ^ m - 5 - 9 * m

有了这个公式,在计算S(20)时,可以先快速计算出S(17),再加上s(18)+s(19)+s(20)就可以得到最终结果,算法复杂度相当于计算四次s(n)。

现在仍有一个关键问题没有解决,10 ^ m 是一个非常大的数,必须找到快速计算10 ^ m mod 1_000_000_007_u64 的办法。

这里要利用费马小定理,如果p是一个质数,而整数a不是p的倍数,则有a^(p-1) mod p = 1。

看一个特殊的例子,a=10, p=7时,有助于大致理解费马小定理的含义。

有个这个定理,10 ^ m mod 1_000_000_007_u64 = 10 ^ (m mod 1_000_000_006_u64) mod 1_000_000_007_u64,可以大大加速计算过程,25秒计算出结果。

最后的源代码:

use std::time::SystemTime;

const PRIME: u64 = 1_000_000_007_u64;

#[macro_use]
extern crate lazy_static;
lazy_static! {
    static ref ARRAY: Vec<u64> = {
        println!("initializing ARRAY ...");
        let mut arr = vec![1];
        let mut x = 1;
        for _i in 1..PRIME - 1 {
            x = x * 10 % PRIME;
            arr.push(x as u64);
        }
        arr
    };
}

fn main() {
    let start = SystemTime::now();
    let mut result = 0;
    let mut fib = vec![0_u64, 1];
    for i in 2..=90 {
        let n = fib[i - 1] + fib[i - 2];
        fib.push(n);
        let ss = fss(n);
        result = (result + ss) % PRIME;
        println!("n:{} S:{} result: {}", n, ss, result);
    }
    println!("{:?}", start.elapsed());
}

fn ten_power_mod(n: u64) -> u64 {
    let m = n % (PRIME - 1);
    ARRAY[m as usize]
}

fn fs(n: u64) -> u64 {
    let a = n % 9;
    let b = n / 9;
    let s = (a + 1) * ten_power_mod(b) - 1;
    s % PRIME
}

fn sum_group(m: u64) -> u64 {
    let temp = (9 * m) % PRIME;
    let s = 5 * ten_power_mod(m) + PRIME - temp - 5;
    s % PRIME
}

fn fss(n: u64) -> u64 {
    let m = n / 9;
    let mut s = sum_group(m);
    for i in 9 * m..=n {
        s += fs(i);
    }
    s % PRIME
}

你可能会错过:

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

本文分享自微信公众号 - 申龙斌的程序人生(slbGTD)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 通过欧拉计划学Rust编程:第100题

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

    申龙斌
  • 用欧拉计划学Rust编程(第79题)

    网上银行常用的一种密保手段是向用户询问密码中的随机三位字符。例如,如果密码是531278,询问第2、3、5位字符,正确的回复应当是317。

    申龙斌
  • 用欧拉计划学习Rust编程(第32~34题)

    最近想学习Libra数字货币的MOVE语言,发现它是用Rust编写的,所以先补一下Rust的基础知识。学习了一段时间,发现Rust的学习曲线非常陡峭,不过仍有快...

    申龙斌
  • TCL TV+量子点电视H9700会成爆款吗?

    2014年智能电视产业因为政策影响,被拖慢了脚步。不过这并未妨碍两大智能电视的火爆:一个是TCL TV+,一个是乐视系列电视,只有这两家的出货量进入了100万台...

    罗超频道
  • 互联网医疗健康产业联盟酝酿大动作 这八份礼物一定有你要的

    从2014年“春江水暖”,到2015年成为投资界“香饽饽”,到2016年“健康中国”成为国家战略,如今,互联网医疗健康产业正在逐步回归实质——借助互联网手段,实...

    企鹅号小编
  • 前端试题中的编程题2:Excel地址的相互转换 [2015南桥杯试题]

    Excel是最常用的办公软件。每个单元格都有唯一的地址表示。比如:第12行第4列表示为:“D12”,第5行第255列表示为“IU5”。  事实上,Excel提...

    Enjoy233
  • buffer busy waits引起的会话突增

    某天,客户反映其监控平台发现其一套数据库7月20日及24日在早晨7:03分和8:09分两个时间段节点1出现会话数突增情况,持续时间较短,问题时间段应用并未受到影...

    沃趣科技
  • CSS基础-引入方法,选择器,继承

        例子:<div style="background-color:red">行内式</div>

    bear_fish
  • Swift 5.1 新特性

    Swift 5.1 内置于 Xcode 11,新增了很多新特性,比较重要的有以下几个。

    YungFan
  • Linux与网卡相关的几个命名

    ifup - start a preconfigured net interface.

    一见

扫码关注云+社区

领取腾讯云代金券