通過歐拉計劃學習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
