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

申龙斌

发布于 2019-09-25 14:32:13

58300

代码可运行

文章被收录于专栏：申龙斌的程序人生申龙斌的程序人生

运行总次数：0

代码可运行

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

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

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

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

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

•第1~6题•第7~12题•第13~16题•第17~21题•第22~25题•第26题•第27~31题•第32~34题

第35题旋转素数

问题描述：

数字197称为旋转素数，因为它的几个数字经过轮转之后，197、971和719也都是素数，在100以内共有13个这样的素数：2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97，问100万之内有几个旋转素数？

解题思路：

1）旋转一个数

最容易想到的思路是取出最左边的数字，放到字符串的最右侧。

fn rotate_v1(n:u64) -> u64 {
    let mut s = n.to_string();
    let ch = s.chars().next().unwrap();
    s = s[1..].to_string();
    s.push(ch);
    s.parse::<u64>().unwrap()
}

因为remove()函数在移除最左侧的字符时，存储了该字符，直接放在右侧即可，代码更简洁和高效一些。

fn rotate(n: u64) -> u64 {
    let mut s = n.to_string();
    let ch = s.remove(0);
    s.push(ch);
    s.parse::<u64>().unwrap()
}

2）判断是否为旋转素数

这里不再重复发明轮子，直接使用了别人写好的primes函数库，需要在toml文件中增加一行依赖项。

[dependencies]
primes = "0.2"

另外，要注意处理一下数字里带0的特殊情况。

fn is_rotate_prime(n: u64) -> bool {
    if n.to_string().contains('0') {
        return false;
    }
    let mut r = n;
    for _i in 0..n.to_string().len() {
        if !primes::is_prime(r) {
            return false;
        }
        r = rotate(r);
    }
    true
}

3）主程序就非常容易了。

let mut count_primes = 0;
for n in 2..1_000_000 {
    if is_rotate_prime(n) {
        println!("{}", n);
        count_primes += 1;
    }
}
println!("{}", count_primes);

// 另外一种写法
let count_primes = (2..1_000_000)
        .filter(|&x| is_rotate_prime(x)).count();
println!("{}", count_primes);

语法知识点：

1）字符串的remove()函数和push()函数。

2）字符串的parse()函数可以转换成数值类型。

第36题两种进制的回文数

问题描述：

数字585是回文数，即从左向右、从右向左读都是一样的，其二进制表示为1001001001，也是回文数。

请找出100万以下的所有回文数，并求和。注意，转换成二进制之后，左侧的0不计算在内。

解题步骤：

1）转换成二进制表示

费劲写了一个转换成二进制的函数。

fn to_radix2_string(n: u64) -> String {
    let mut d = n;
    let mut s:String = "".to_string();
    while d != 0 {
        let m = d % 2;
        s.push_str(&m.to_string());
        d /= 2;
    }
    s
}

发现又在重复造轮子，直接用format!宏就可以搞定。

let s = format!("{:b}", n);

2）判断是否回文

比较简单的写法。

fn is_palindromic(s: String) -> bool {
    s == s.chars().rev().collect::<String>() 
}

这里用了collect()，效率比较低，实际上当发现了首尾不一样的字符时，就应该马上返回false，而且最多比较一半的字符就行，效率大幅提升。

fn is_palindromic(s: String) -> bool {
    let mut c1 = s.chars();
    let mut c2 = s.chars().rev();
    for _i in 0..s.len() / 2 {
        if c1.next().unwrap() != c2.next().unwrap() {
            return false;
        }
    }
    true
    //    s == s.chars().rev().collect::<String>()
}

3）最后循环求和

这一步逻辑简单，就不放代码了。

第37题左截和右截素数

问题描述

3797有一个有趣的属性，它本身是素数，另外从左向右依次删除一个数字，得到：797, 97, 和7，仍是素数，依次从右向左删除一个数字，得到：379, 37, 和3，仍是素数。

总共只有11个这样的素数，请求它们的和。

注意：2, 3, 5和7不计算在内。

解题思路

判断是否为左截素数，循环调用remove()函数即可。

fn is_trun_left_prime(n: u64) -> bool {
    let mut s = n.to_string();
    while s.len() > 0 {
        let p = s.parse::<u64>().unwrap();
        if !primes::is_prime(p) {
            return false;
        }
        s.remove(0);
    }
    true
}

类似的，换成pop()函数，可以判断右截素数。

fn is_trun_right_prime(n: u64) -> bool {
    let mut s = n.to_string();
    while s.len() > 0 {
        let p = s.parse::<u64>().unwrap();
        if !primes::is_prime(p) {
            return false;
        }
        s.pop();
    }
    true
}

题目告诉了只有11个这样的素数，暴力搜索到11个即可，主程序从略。

第38题全数字的倍数

问题描述：

将192分别与1、2、3相乘：

192 × 1 = 192

192 × 2 = 384

192 × 3 = 576

连接这些乘积，我们得到一个1至9全数字的数192384576。我们称192384576为192和(1,2,3)的连接乘积。

同样地，将9分别与1、2、3、4、5相乘，得到1至9全数字的数918273645，即是9和(1,2,3,4,5)的连接乘积。

对于n > 1，所有某个整数和(1,2, … ,n)的连接乘积所构成的数中，最大的1至9全数字的数是多少？

解题步骤：

第32题与本题比较相似，有一个判断全数字（有且仅有一次1到9）的函数，可以直接利用。

fn exists_only_once_1_to_9(s: &str) -> bool {
    let mut has_digit: Vec<bool> = vec![false; 10];
    for ch in s.to_string().chars() {
        let c = ch.to_digit(10).unwrap() as usize;
        if c == 0 {
            return false;
        }
        if has_digit[c] {
            return false;
        }
        has_digit[c] = true;
    }
    true
}

主程序用2层循环就可以搞定，运算量不大，不需要优化。

fn main() {
    let mut max = "".to_string();
    for a in 1..=9876 {
        let mut s = String::from("");
        for n in 1..=9 {
            let prod = a * n;
            s.push_str(&prod.to_string());
            if !exists_only_once_1_to_9(&s) {
                break;
            }
            if s.len() == 9 && s > max {
                println!("{} x {:?} = {}", a, [1..n], s);
                max = s.clone();
            }
        }
    }
}

第39题直角三角形

问题描述：

周长p的120的整数直角三角形共有3个：{20,48,52}, {24,45,51}, {30,40,50}，如果周长p<=1000，当p取何整数值时，满足条件的直角三角数个数最多？

解题思路

先对给定的周长，把所有的直角三角形求出来。为了不输出重复项，第二重循环的取值范围要注意。

fn count_right_triangles(p: isize) -> isize {
    let mut count = 0;
    for a in 1..p {
        for b in a..p {
            let c = p - a - b;
            if c > 0 && a * a + b * b == c * c {
                count += 1;
                print!("{{{}, {}, {}}}, ", a, b, c)
            }
        }
    }
    count
}

主程序比较简单。

let mut max_count = 1;
let mut max_p = 0;
for p in 2..1000 {
    let count = count_right_triangles(p);
    if count > max_count {
        max_count = count;
        max_p = p;
        println!("p: {} max: {}", p, max_count);
    }
}
println!("p: {}", max_p);

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

1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj

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

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

欢迎加我微信讨论解题技术，暗号：RUST。

当然用C，JAVA，Go，Haskell，Python，甚至Excel，我可以讨论。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-09-23，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自申龙斌的程序人生微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度