用欧拉计划学Rust编程(第35~38题)
- 2019 年 10 月 7 日
- 筆記
最近想学习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，我可以讨论。
