专栏首页申龙斌的程序人生用欧拉计划学习Rust编程(第32~34题)

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

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

学习任何一项技能最怕没有反馈,尤其是学英语、学编程的时候,一定要“用”,学习编程时有一个非常有用的网站,它就是“欧拉计划”,网址:https://projecteuler.net

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

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

学习Rust最好先把基本的语法和特性看过一遍,然后就可以动手解题了,解题的过程就是学习、试错、再学习、掌握和巩固的过程,学习进度会大大加快。

全数字的乘积

问题描述:

如果一个n位数包含了1至n的所有数字恰好一次,我们称它为全数字的;例如,五位数15234就是1至5全数字的。

7254是一个特殊的乘积,因为在等式39 × 186 = 7254 中,被乘数、乘数和乘积恰好是1至9全数字的。

找出所有被乘数、乘数和乘积恰好是1至9全数字的乘法等式,并求出这些等式中乘积的和。

注意:有些乘积可能从多个乘法等式中得到,但在求和的时候只计算一次。

解题思路:

1)判断一个字符串中只能出现一次的1到9

2)循环尝试,记录每一个满足要求的乘积

3)求和

第一步,先写一个判断字符串里只能出现一次1到9的函数。

n exists_only_once_1_to_9(s: &str) -> bool {
    let mut has_digit = vec![false; 10];
    for ch in s.to_string().chars() {
        let c = ch.to_digit(10).unwrap() as usize;
        if c == 0 { // 不允许0的存在
            return false;
        }
        if has_digit[c] {
            return false;
        }
        has_digit[c] = true;
    }
    true
}

第二步和第三步,比较简单,循环的终止条件要考虑一下,被乘数和乘数都不能超过4位数,所以只需要试验到9876。

let mut v: Vec<u32> = vec![];
for a in 2..9876 {
    for b in 2..a {
        let c = a * b;
        let abc = a.to_string() + &b.to_string() + &c.to_string();
        if abc.len() == 9 && exists_only_once_1_to_9(&abc) {
            println!("{} x {} = {}", a, b, c);
            if !v.contains(&c) {
                v.push(c);
            }
        }
    }
}
println!("{}", v.iter().sum::<u32>());

程序到这里已经可以跑起来了,但运行起来较慢,发现少了一条重要的优化语句,乘积在大于9876时,后面的数都不用试了。

在循环体加一条判断语句,程序在1秒之内运行完成。

if c > 9876 {break;}

第33题 消去数字的分数

问题描述:

49/98是一个有趣的分数,因为缺乏经验的数学家可能在约简时错误地认为,等式49/98 = 4/8之所以成立,是因为在分数线上下同时抹除了9的缘故。

我们也会想到,存在诸如30/50 = 3/5这样的平凡解。

这类有趣的分数恰好有四个非平凡的例子,它们的分数值小于1,且分子和分母都是两位数。

将这四个分数的乘积写成最简分数,求此时分母的值。

求解思路:

四个分数很容易求出,我这里没有进行通分运算,后面手算即可。

for ab in 10..=99 {
    let a = ab / 10;
    let b = ab % 10;
    for cd in (ab+1)..=99 {
        let c = cd / 10;
        let d = cd % 10;
        if b == c && ab * d == cd * a {
            println!("{} / {} = {} / {}", ab, cd, a, d);
        } 
    }
}

第34题 各位数字的阶乘

问题描述

145是个有趣的数,因为1! + 4! + 5! = 1 + 24 + 120 = 145。

找出所有各位数字的阶乘和等于其本身的数,并求它们的和。

注意:因为1! = 1和2! = 2不是和的形式,所以它们并不在讨论范围内。

解题思路

1)求阶乘

2)找出一个数的各位数字

3)循环求解

第一步,阶乘可以用递归实现。

fn factorial(n: u32) -> u32 {
    if n <= 1 {
        return 1;
    }
    return n * factorial(n - 1);
}

1到9的阶乘需要经常用到,用一个数组缓存起来。

// [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
let mut fac = vec![1; 10];
for i in 0..=9 {
    fac[i] = factorial(i as u32);
}

上面几行,等价于这样一行:

let fac: Vec<u32> = (0..10).map(|x| factorial(x)).collect();

后面的逻辑比较简单,我只搜索到了999999,后面好像不存在满足条件的更大的解。

let mut sum = 0;
for n in 3..999999 {
    // 各位数字的阶乘之和
    let mut sum_fac = 0;
    for digit in n.to_string().chars().map(|x| x.to_digit(10).unwrap()) {
        sum_fac += fac[digit as usize];
    }
    if n == sum_fac {
        println!("{}! = {}", n, n);
        sum += n;
    }
}
println!("{}", sum);

求sum_fac那几行还可以这样写:

let sum_fac: u32 = n
    .to_string()
    .chars()
    .map(|x| fac[x.to_digit(10).unwrap() as usize])
    .sum();

知识点:

学会使用map()函数

// 0-9的阶乘
let fac: Vec<u32> = (0..10).map(|x| factorial(x)).collect();
// 取各个数字
n.to_string().chars().map(|x| x.to_digit(10).unwrap())

在projecteuler中注册一个账号,可以添加好友,一起讨论学习,我的Key是:

1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj

最新的源代码同步更新在github上。

https://github.com/slofslb/rust-project-euler

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

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

原始发表时间:2019-09-21

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用欧拉计划学Rust编程(第35~38题)

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

    申龙斌
  • 通过欧拉计划学Rust编程(第684题)

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

    申龙斌
  • 通过欧拉计划学习Rust编程(第17~21题)

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

    申龙斌
  • jzy3D从入门到弃坑_2 使用jzy3D0.9画2D散点图

    DrawSky
  • 网站可用性检测工具 - uptime

    uptime 是一个远程监控应用,使用 Node.js MongoDB Bootstrap 实现 ? 特点 性能好,可以监控上千个网站 监控信息全面,如 可用性...

    dys
  • 2016-05-09的POC Yaas Open Event的代码审查

    Jerry: One phone number is only allow for registration once, right? How to maint...

    Jerry Wang
  • 在线票务哪家强?数据图解告你知!

    近日,第一财经CBNData发布了《2016上半年中国在线票务平台大数据报告》,报告对2016年上半年的在线票务市场做了数据分析。数据显示,目前已经形成“BAT...

    华章科技
  • 「R」回归和相关分析

    线性回归,当datx是预测变量时,daty为响应变量。这可以使用一个数据框的两列,或者是直接使用数值向量。

    王诗翔呀
  • TCP三次握手

    传输控制协议TCP,Transmission Control Protocol是一种面向连接的、可靠的、基于字节流的传输层通信协议,其是运行在OSI七层模型中的...

    WindrunnerMax
  • 「R」数据可视化9: 金字塔图和偏差图

    这几张图乍一看和我们之前看到的很不一样,但是仔细一看其所用的基本元素不就是我们的条形图吗?

    王诗翔呀

扫码关注云+社区

领取腾讯云代金券