用欧拉计划学习Rust编程(第40~45题)
最近想学习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题•第22~34题•第35~39题
第40题 钱珀瑙恩常数
问题描述：
将所有正整数连接起来构造的一个十进制无理数如下所示：
0.123456789101112131415161718192021...
可以看出小数点后第12位数字是1。如果dn表示上述无理数小数点后的第n位数字，求下式的值：d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
解题思路：
算法很简单，需要留意差1的BUG。
let max_digits = 1_000_001;
let mut digits: Vec<usize> = vec![0; max_digits];
let mut pos = 1;
'a: for i in 1.. {
for ch in i.to_string().chars() {
let d = ch.to_digit(10).unwrap() as usize;
if pos >= max_digits {
break 'a;
}
digits[pos] = d;
pos += 1;
}
}
println!(
"{}", digits[1]
* digits[10]
* digits[100]
* digits[1000]
* digits[10000]
* digits[100000]
* digits[1000000]
);最后的乘积计算，可以练习一下map()和fold()的写法。
let d: Vec<usize> = (0..=6).map(|x| digits[10_usize.pow(x)]).collect();
println!("{:?}", d);
let p: usize = (0..=6)
.map(|x| digits[10_usize.pow(x)])
.fold(1, |x, a| x * a);
println!("{}", p);第41题 全数字的素数
问题描述：
如果一个n位数恰好使用了1至n每个数字各一次，我们就称其为全数字的。例如，2143就是一个4位全数字数，同时它恰好也是一个素数。
最大的全数字的素数是多少？
解题步骤：
1）生成全排列
第24题中已经有一个全排列的生成算法，增加一个返回值，如果已经到达了最后的一个排列，就返回false，方便主程序退出循环。
fn next_perm(v: &mut [u64]) -> bool {
let mut i = v.len() - 2;
while v[i] > v[i + 1] {
if i == 0 {
return false;
}
i -= 1;
}
let mut j = v.len() - 1;
while i < j && v[i] > v[j] {
j -= 1;
}
swap(v, i, j);
i += 1;
j = v.len() - 1;
while i < j {
swap(v, i, j);
i += 1;
j -= 1;
}
true
}2）向量转换成数值
为了后面判断素数，需要将[1, 2, 3, 4, 5, 6, 7]这样的向量转换成 1234567。
我一开始的想法是把每个数字转换成字符串，拼在一起，再转换成数值。
let v_str = v.iter().map(|x| x.to_string()).collect::<String>();
let d = v_str.parse::<usize>().unwrap();后来发现，用一系列整数运算可以完成这个任务，代码比较简洁，但我没有比较两种办法的效率，初步估计整数运算的效率会更高一些。
let d = v.iter().fold(0, |x, a| 10 * x + a);3）主程序
准备工作完成后，主程序没有难度。我先用4位整数验证了程序的正确性，再跑9位、8位的情况，最后在7位的时候发现了答案。
let mut v = [1, 2, 3, 4, 5, 6, 7];
let mut max_prime = 0;
while next_perm(&mut v) {
let d = v.iter().fold(0, |x, a| 10 * x + a);
if primes::is_prime(d as u64) && d > max_prime {
println!("{}", d);
max_prime = d;
}
}4）不重新发明轮子
我以前为了练习算法，自己写了全排列的生成函数，实际上别人已经写好了这类函数库，直接拿来用就行。
use permutohedron::heap_recursive;
fn main() {
let mut max_prime = 0;
let mut data = [1, 2, 3, 4, 5, 6, 7];
heap_recursive(&mut data, |permutation| {
let v = permutation.to_vec();
let d = v.iter().fold(0, |x, a| 10 * x + a);
if primes::is_prime(d as u64) && d > max_prime {
println!("{}", d);
max_prime = d;
}
})
}5）更为高效的算法
因为题目要求最大的全排列素数，前面这些算法都要把所有的排列组合都尝试一遍，效率极低。
最高效的办法是修改最早的全排列生成算法，让next_perm_desc()降序生成，这样找到的第一个素数就是最终答案。
fn main() {
let mut v = [7, 6, 5, 4, 3, 2, 1];
loop {
let d = v.iter().fold(0, |x, a| 10 * x + a);
if primes::is_prime(d as u64) {
println!("{}", d);
break;
}
if !next_perm_desc(&mut v) {
break;
}
}
}
// 降序全排列
fn next_perm_desc(v: &mut [u64]) -> bool {
let mut i = v.len() - 2;
while v[i] < v[i + 1] {
if i == 0 {
return false;
}
i -= 1;
}
let mut j = v.len() - 1;
while i < j && v[i] < v[j] {
j -= 1;
}
swap(v, i, j);
i += 1;
j = v.len() - 1;
while i < j {
swap(v, i, j);
i += 1;
j -= 1;
}
true
}
fn swap(v: &mut [u64], i: usize, j: usize) {
let temp = v[i];
v[i] = v[j];
v[j] = temp;
}第42题 编码三角形数
问题描述
解题思路
1）读文件内容到数组中
let data = std::fs::read_to_string("words.txt").expect("读文件失败");
// 删除引号
let data2: String = data.chars().filter(|c| *c != '"').collect();
let names: Vec<&str> = data2.split(",").collect();2）准备足够的三角数，以备将来进行快速判断
let mut tri_numbers = vec![];
for i in 1..=100 {
tri_numbers.push(i * (i + 1) / 2);
}
//println!("{:?}", tri_numbers);3）字符在字母表中的顺序号
最早是用查找方式实现的。
let letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
letters.chars().position(|c| c == ch).unwrap() + 1在Rust中一个字符可以直接转换成u8类型，就是其ASCII编码值，'A'的编码为65，字符与'A'的差值就是编号，更加高效。
// 一个字符在字母表中分数，'A' -> 1，'B' -> 2
fn letter_number(ch: char) -> u8 {
(ch as u8) - 64
}4）单词的分数
常规的写法：
fn word_score(word: &str) -> usize {
let mut score = 0;
for ch in word.chars() {
score += letter_number(ch) as usize;
}
score
}可以用函数式编程的写法：
fn word_score(word: &str) -> usize {
word.chars().map(|ch| letter_number(ch) as usize).sum()
}5）主循环算分求和即可。
前面的函数都比较简单，可以写在一行，最后的主程序也可以很精炼。
let mut count = 0;
for name in names {
let word_score = name.chars().map(|ch| ch as usize - 64).sum();
if tri_numbers.contains(&word_score) {
//println!("{} {}", name, word_score);
count += 1;
}
}
println!("{}", count);第43题 子串的可整除性
问题描述：
问题分解：
1）找出0到9的所有全排列
2）找出三位数的子串
3）暴力循环求解
第一步，找全排列
在第24题和第41题已经了解了全排列的算法，这里直接利用nnext_perm()函数即可，需要注意0不能出现在最左边。
第二步：取出3位数字
这里以取d2 d3 d4三位数字为例：
let v_str = v.iter().map(|x| x.to_string()).collect::<String>();
let sub3 = &v_str[1..4];
let d = sub3.parse::<u32>().unwrap();第三步，可以写出主程序：
let mut v = [1, 0, 2, 3, 4, 5, 6, 7, 8, 9];
let primes = [2, 3, 5, 7, 11, 13, 17];
let mut sum: u64 = 0;
loop {
let v_str = v.iter().map(|x| x.to_string()).collect::<String>();
for i in 1..=7 {
let sub3 = &v_str[i..i + 3];
let d = sub3.parse::<u32>().unwrap();
if d % primes[i-1] != 0 {
break;
}
if i == 7 {
println!("{}", v_str);
sum += v_str.parse::<u64>().unwrap();
}
}
if !next_perm(&mut v) {
break;
}
}
println!("sum: {}", sum);第四步：优化
前面的算法中大量在字符串和数字之间进行转换，效率还有点低，实际上可以全部利用整数的运算，效率可以提高很多，最后的代码：
fn main() {
let mut v = [0, 9, 8, 7, 6, 5, 4, 3, 2, 1];
let mut sum: u64 = 0;
while next_perm(&mut v) {
let num = v.iter().fold(0, |x, a| 10 * x + a);
if is_divisibility(num) {
println!("{}", num);
sum += num;
}
}
println!("sum: {}", sum);
}
fn is_divisibility(num: u64) -> bool {
let primes = [2, 3, 5, 7, 11, 13, 17];
let mut n = num % 1_000_000_000;
for i in (0..=6).rev() {
let sub3 = n % 1000;
if sub3 % primes[i] != 0 {
return false;
}
n = n / 10;
}
true
}
fn next_perm(v: &mut [u64]) -> bool {
let mut i = v.len() - 2;
while v[i] > v[i + 1] {
if i == 0 {
return false;
} // 已经全部从大到小排列了
i -= 1;
}
let mut j = v.len() - 1;
while i < j && v[i] > v[j] {
j -= 1;
}
swap(v, i, j);
i += 1;
j = v.len() - 1;
while i < j {
swap(v, i, j);
i += 1;
j -= 1;
}
true
}
fn swap(v: &mut [u64], i: usize, j: usize) {
let temp = v[i];
v[i] = v[j];
v[j] = temp;
}第44题 五边形数
问题描述：
问题分解：
1）生成足够的五边形数，备用
一开始不知道最终答案的范围，先生成1万个备用。
let mut penta: Vec<u64> = vec![0];
for i in 1..10000 {
penta.push(i * (3 * i - 1) / 2);
}2）双重循环搜索
暴力搜索，判断和与差是否也是五边形数，竟然只找到一个满足条件的解，输入到projecteuler网站，发现竟然就是正确答案。
for k in 2..3000 {
for j in (1..k).rev() {
let d = penta[k] - penta[j];
let sum = penta[k] + penta[j];
if penta.contains(&d) && penta.contains(&sum) {
println!("j:{} k:{} pj:{} pk:{} diff:{}", j, k, penta[j], penta[k], d);
}
}
}3）优化
判断一个数是不是五边形数用contains()效率并不高，特别是集合的元素非常多时，得把高中的二次函数的求解公式翻出来。
如果p是五边形数，1+24*p应该是完全平方数，分子还要能被6整除。
fn is_penta(p: u64) -> bool {
let t = ((1 + 24 * p) as f64).sqrt() as u64; // sqrt(b*b - 4*a*c)
if t * t != (1 + 24 * p) {
return false;
}
(t + 1) % 6 == 0
}主程序仍用双重循环搜索。
let mut min_d = std::u64::MAX;
// 改为2.. 可以证明结果的正确性，但要运行相当长的时间
for k in 2..10000 {
let pk = penta(k);
if pk - penta(k-1) > min_d {break;}
for j in (1..k).rev() {
let pj = penta(j);
let d = pk - pj;
if d < min_d && is_penta(d) && is_penta(pk + pj) {
println!("j:{} k:{} pj:{} pk:{} diff:{}",j, k, pj, pk, d);
min_d = d;
break;
}
}
}这个题找到一个答案的速度非常快，但并不能充分地证明它就是最小的d，应该再继续向后搜索五边形数，当相邻的五边形数的差都大于min_d时，才证明了的确找到了最小的d，但需要运行相当长的时间。
第45题 三角形数、五边形数和六角形数
问题描述：
问题求解：
这个题我没有采用上一题的二次函数求解的公式，准备好10万个三角数和五边形数，暴力搜索找到了答案。
let mut tri: Vec<u64> = vec![];
for i in 1..100000 {
tri.push(i * (i + 1) / 2);
}
let mut penta: Vec<u64> = vec![];
for i in 1..100000 {
penta.push(i * (3 * i - 1) / 2);
}
for i in 2..30000 {
let hex = i * (2 * i - 1);
if tri.contains(&hex) && penta.contains(&hex) {
println!("i: {} hexagonal: {}", i, hex);
}
}在projecteuler中注册一个账号，可以添加好友，一起讨论学习，我的Key是：
1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj最新的源代码同步更新在github上。
https://github.com/slofslb/rust-project-euler欢迎加我微信讨论解题技术，暗号：RUST。
当然用C，JAVA，Go，Haskell，Python，甚至Excel，都可以讨论。