通过欧拉计划学习Rust编程(第13~16题)
- 2019 年 10 月 6 日
- 笔记
最近想学习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题
问题描述：
已知2×2网格中从左上角到右下角共有6条可能路径，计算20×20网格中，有多少条可能的路径。
还是用递归的思路。对于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)); }
可惜程序的性能很差，对于12×12的网格可以秒出，而20×20的网格估计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
