通过欧拉计划学习Rust编程(第13~16题)
通过欧拉计划学习Rust编程(第13~16题)
最近想学习Libra数字货币的MOVE语言，发现它是用Rust编写的，所以先补一下Rust的基础知识。学习了一段时间，发现Rust的学习曲线非常陡峭，不过仍有快速入门的办法。
学习任何一项技能最怕没有反馈，尤其是学英语、学编程的时候，一定要“用”，学习编程时有一个非常有用的网站，它就是“欧拉计划”，网址：https://projecteuler.net
这个网站提供了几百道由易到难的数学问题，你可以用任何办法去解决它，当然主要还得靠编程，编程语言不限，论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法，当然如果你直接用google搜索答案就没任何乐趣了。
学习Rust最好先把基本的语法和特性看过一遍，然后就可以动手解题了，解题的过程就是学习、试错、再学习、掌握和巩固的过程，学习进度会大大加快。
第13题 大整数求和
问题描述：
有100个长达50位的大整数，求和，只取前10位数字。
各种编程语言都有大整数的函数库，直接使用就行了，不用自己造轮子。在Rust里一样也有大量的现成的库，称为crate，这个单词翻译为“柳条箱”，不知道官方的翻译是什么。大整数的官方实现是num_bigint。
需要修改Cargo.toml文件：
[dependencies]
num-bigint = "0.2.2"
文件头加上相关的引用：
extern crate num_bigint;
use num_bigint::BigUint;
100个大整数这里用字符串数组表示。
let numbers = [
"37107287533902102798797998220837590246510135740250",
"46376937677490009712648124896970078050417018260538",
"74324986199524741059474233309513058123726617309629",
"22918802058777319719839450180888072429661980811197",
// 省略了很多行
"77158542502016545090413245809786882778948721859617",
"72107838435069186155435662884062257473692284509516",
"20849603980134001723930671666823555245252804609722",
"53503534226472524250874054075591789781264330331690",
];这里只用到了正整数BigUint，由于Rust是强类型语言，所以想办法把字符串转换为BigUint。
let mut sum = BigUint::from(0 as u64);
for s in numbers.iter() {
sum += BigUint::parse_bytes(s.as_bytes(), 10).unwrap();
}
let full_str = sum.to_string();
println!("take 10 digits: {}", &full_str[..10]);
结果很长，只取前10个数字，用到字符串的切片函数 &full_str[..10]。
第14题
问题描述：
从100万之内挑一个数作为起始数，生成Collatz序列，哪个生成的链最长？
Collatz序列的意思是，当一个数n是偶数时，下一数为n/2；当n为奇数时，下一个数为3*n+1。
这种序列有一个猜想，最后都会收敛于4，2，1。例如：
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
用递归函数是比较简练的。
fn collatz_len(x: u64) -> u64 {
if x == 1 { return 1; }
let y;
if x % 2 == 0 {
y = x / 2;
} else {
y = x * 3 + 1;
}
collatz_len(y) + 1
}
里面有一个关于y的分支判断，可以利用类似C#中的三元表达式 "cond ? a : b"写在一行里，在Rust里可以直接用if语句。
fn collatz_len(x: u64) -> u64 {
if x == 1 { return 1; }
let y = if x % 2 == 0 { x / 2 } else { x * 3 + 1 };
collatz_len(y) + 1
}主程序用一个循环暴力搜索就行了：
fn main() {
let mut max = 0;
for num in 1..1_000_000 {
let c = collatz_len(num as u64);
if c > max {
max = c;
println!("start num: {} chain length: {}", num, max);
}
}
}
程序还可以优化一下性能，将一些运算的结果缓存起来，不用重复计算，这里不再展开。
第15题
问题描述：
已知2x2网格中从左上角到右下角共有6条可能路径，计算20x20网格中，有多少条可能的路径。
还是用递归的思路。对于m行n列的网格，可以利用其它网格的路径个数的结果，即：
P(m,n) = P(m-1,n) + P(m-1,n-1) + ... + P(m-1,1) + P(m-1,0)
对于0行或者0列的网格，路径只有1条。
程序就比较容易写出来了：
fn path_slow(m: usize, n: usize) -> u64 {
if m == 0 || n == 0 { return 1; }
let mut sum = 0;
for j in 0..=n {
sum += path_slow(m-1, j);
}
return sum;
}
fn main() {
println!("{}", path_slow(12, 12));
println!("{}", path_slow(20, 20));
}
可惜程序的性能很差，对于12x12的网格可以秒出，而20x20的网格估计20分钟也没反应，看来重复的运算量太大了。
可以把以前计算的结果缓存到一个一维向量中，速度则大幅提升，这里可以学到&mut传入向量地址的语法知识点，另外初始化10000万个零，用 vec![0; 10000]。
fn main() {
let mut v: Vec<u64> = vec![0; 10000];
println!("{}", path_fast(&mut v, 20, 20));
}
fn path_fast(v: &mut Vec<u64>, m: usize, n: usize) -> u64 {
if m == 0 || n == 0 {
return 1;
}
if v[m * 100 + n] > 0 {
return v[m * 100 + n];
} //缓存命中
let mut sum = 0;
for j in 0..=n {
sum += path_fast(v, m - 1, j);
}
v[m * 100 + n] = sum; // 加入缓存中
println!("({},{}) {}", m, n, sum);
return sum;
}
另外，这道题可以推导出一个排列组合的数学公式，当然就体会不到编程的乐趣了。
第16题
问题描述：
求2的1000次方的所有数字之和。
同样用到大整数的计算函数库num_bigint，注意添加依赖项。
extern crate num_bigint;
use num_bigint::BigUint;
大整数里没有power()函数，可以把2相乘1000次。
let mut prod = BigUint::from(1 as u64);
for _i in 0..1000 {
prod *= BigUint::from(2 as u64);
}
let full_str = prod.to_string();
println!("{}", full_str);
在for循环里变量i并没有使用，所有前面添加一个下划线，可以不出现编译警告。
还可以学习一下函数式编程里的fold()的写法，用一行语句，但理解起来比前面的4行语句难一些。
let pow2_1000 = (0..1000).fold(BigUint::from(1 as u64), |p, _a| p*BigUint::from(2 as u64));
println!("{}", pow2_1000);
在第8题里学过把字符串切成一个个的数字，这里相加即可。
let s = full_str
.chars()
.map(|c| c.to_digit(10).unwrap())
.sum::<u32>();
println!("{}", s);
在projecteuler中注册一个账号，可以添加好友，一起讨论学习，我的Key是：
1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj
腾讯云开发者
