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