用歐拉計劃學習Rust編程(第32~34題)

2019 年 10 月 6 日
筆記

最近想學習Libra數字貨幣的MOVE語言，發現它是用Rust編寫的，所以先補一下Rust的基礎知識。學習了一段時間，發現Rust的學習曲線非常陡峭，不過仍有快速入門的辦法。

學習任何一項技能最怕沒有回饋，尤其是學英語、學編程的時候，一定要「用」，學習編程時有一個非常有用的網站，它就是「歐拉計劃」，網址：https://projecteuler.net

英文如果不過關，可以到中文翻譯的網站：http://pe-cn.github.io/

這個網站提供了幾百道由易到難的數學問題，你可以用任何辦法去解決它，當然主要還得靠編程，程式語言不限，論壇里已經有Java、C#、Python、Lisp、Haskell等各種解法，當然如果你直接用google搜索答案就沒任何樂趣了。

學習Rust最好先把基本的語法和特性看過一遍，然後就可以動手解題了，解題的過程就是學習、試錯、再學習、掌握和鞏固的過程，學習進度會大大加快。

全數字的乘積

問題描述：

如果一個n位數包含了1至n的所有數字恰好一次，我們稱它為全數字的；例如，五位數15234就是1至5全數字的。

7254是一個特殊的乘積，因為在等式39 × 186 = 7254 中，被乘數、乘數和乘積恰好是1至9全數字的。

找出所有被乘數、乘數和乘積恰好是1至9全數字的乘法等式，並求出這些等式中乘積的和。

注意：有些乘積可能從多個乘法等式中得到，但在求和的時候只計算一次。

解題思路：

1）判斷一個字元串中只能出現一次的1到9

2）循環嘗試，記錄每一個滿足要求的乘積

3）求和

第一步，先寫一個判斷字元串里只能出現一次1到9的函數。

n exists_only_once_1_to_9(s: &str) -> bool {      let mut has_digit = vec![false; 10];      for ch in s.to_string().chars() {          let c = ch.to_digit(10).unwrap() as usize;          if c == 0 { // 不允許0的存在              return false;          }          if has_digit[c] {              return false;          }          has_digit[c] = true;      }      true  }

第二步和第三步，比較簡單，循環的終止條件要考慮一下，被乘數和乘數都不能超過4位數，所以只需要試驗到9876。

let mut v: Vec<u32> = vec![];  for a in 2..9876 {      for b in 2..a {          let c = a * b;          let abc = a.to_string() + &b.to_string() + &c.to_string();          if abc.len() == 9 && exists_only_once_1_to_9(&abc) {              println!("{} x {} = {}", a, b, c);              if !v.contains(&c) {                  v.push(c);              }          }      }  }  println!("{}", v.iter().sum::<u32>());

程式到這裡已經可以跑起來了，但運行起來較慢，發現少了一條重要的優化語句，乘積在大於9876時，後面的數都不用試了。

在循環體加一條判斷語句，程式在1秒之內運行完成。

if c > 9876 {break;}

第33題消去數字的分數

問題描述：

49/98是一個有趣的分數，因為缺乏經驗的數學家可能在約簡時錯誤地認為，等式49/98 = 4/8之所以成立，是因為在分數線上下同時抹除了9的緣故。

我們也會想到，存在諸如30/50 = 3/5這樣的平凡解。

這類有趣的分數恰好有四個非平凡的例子，它們的分數值小於1，且分子和分母都是兩位數。

將這四個分數的乘積寫成最簡分數，求此時分母的值。

求解思路：

四個分數很容易求出，我這裡沒有進行通分運算，後面手算即可。

for ab in 10..=99 {      let a = ab / 10;      let b = ab % 10;      for cd in (ab+1)..=99 {          let c = cd / 10;          let d = cd % 10;          if b == c && ab * d == cd * a {              println!("{} / {} = {} / {}", ab, cd, a, d);          }      }  }

第34題各位數字的階乘

問題描述

145是個有趣的數，因為1! + 4! + 5! = 1 + 24 + 120 = 145。

找出所有各位數字的階乘和等於其本身的數，並求它們的和。

注意：因為1! = 1和2! = 2不是和的形式，所以它們並不在討論範圍內。

解題思路

1）求階乘

2）找出一個數的各位數字

3）循環求解

第一步，階乘可以用遞歸實現。

fn factorial(n: u32) -> u32 {      if n <= 1 {          return 1;      }      return n * factorial(n - 1);  }

1到9的階乘需要經常用到，用一個數組快取起來。

// [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]  let mut fac = vec![1; 10];  for i in 0..=9 {      fac[i] = factorial(i as u32);  }

上面幾行，等價於這樣一行：

let fac: Vec<u32> = (0..10).map(|x| factorial(x)).collect();

後面的邏輯比較簡單，我只搜索到了999999，後面好像不存在滿足條件的更大的解。

let mut sum = 0;  for n in 3..999999 {      // 各位數字的階乘之和      let mut sum_fac = 0;      for digit in n.to_string().chars().map(|x| x.to_digit(10).unwrap()) {          sum_fac += fac[digit as usize];      }      if n == sum_fac {          println!("{}! = {}", n, n);          sum += n;      }  }  println!("{}", sum);

求sum_fac那幾行還可以這樣寫：

let sum_fac: u32 = n      .to_string()      .chars()      .map(|x| fac[x.to_digit(10).unwrap() as usize])      .sum();

知識點：

學會使用map()函數

// 0-9的階乘  let fac: Vec<u32> = (0..10).map(|x| factorial(x)).collect();  // 取各個數字  n.to_string().chars().map(|x| x.to_digit(10).unwrap())

在projecteuler中註冊一個帳號，可以添加好友，一起討論學習，我的Key是：

1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj

最新的源程式碼同步更新在github上。

https://github.com/slofslb/rust-project-euler