用歐拉計劃學Rust編程(第35~38題)
- 2019 年 10 月 7 日
- 筆記
最近想學習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題•第32~34題
第35題 旋轉素數
問題描述：
數字197稱為旋轉素數，因為它的幾個數字經過輪轉之後，197、971和719也都是素數，在100以內共有13個這樣的素數：2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97，問100萬之內有幾個旋轉素數？
解題思路：
1）旋轉一個數
最容易想到的思路是取出最左邊的數字，放到字符串的最右側。
fn rotate_v1(n:u64) -> u64 { let mut s = n.to_string(); let ch = s.chars().next().unwrap(); s = s[1..].to_string(); s.push(ch); s.parse::<u64>().unwrap() }
因為remove()函數在移除最左側的字符時，存儲了該字符，直接放在右側即可，代碼更簡潔和高效一些。
fn rotate(n: u64) -> u64 { let mut s = n.to_string(); let ch = s.remove(0); s.push(ch); s.parse::<u64>().unwrap() }
2）判斷是否為旋轉素數
這裡不再重複發明輪子，直接使用了別人寫好的primes函數庫，需要在toml文件中增加一行依賴項。
[dependencies] primes = "0.2"
另外，要注意處理一下數字裡帶0的特殊情況。
fn is_rotate_prime(n: u64) -> bool { if n.to_string().contains('0') { return false; } let mut r = n; for _i in 0..n.to_string().len() { if !primes::is_prime(r) { return false; } r = rotate(r); } true }
3）主程序就非常容易了。
let mut count_primes = 0; for n in 2..1_000_000 { if is_rotate_prime(n) { println!("{}", n); count_primes += 1; } } println!("{}", count_primes); // 另外一種寫法 let count_primes = (2..1_000_000) .filter(|&x| is_rotate_prime(x)).count(); println!("{}", count_primes);
語法知識點：
1）字符串的remove()函數和push()函數。
2）字符串的parse()函數可以轉換成數值類型。
第36題 兩種進制的迴文數
問題描述：
數字585是迴文數，即從左向右、從右向左讀都是一樣的，其二進制表示為1001001001，也是迴文數。
請找出100萬以下的所有迴文數，並求和。注意，轉換成二進制之後，左側的0不計算在內。
解題步驟：
1）轉換成二進制表示
費勁寫了一個轉換成二進制的函數。
fn to_radix2_string(n: u64) -> String { let mut d = n; let mut s:String = "".to_string(); while d != 0 { let m = d % 2; s.push_str(&m.to_string()); d /= 2; } s }
發現又在重複造輪子，直接用format!宏就可以搞定。
let s = format!("{:b}", n);
2）判斷是否迴文
比較簡單的寫法。
fn is_palindromic(s: String) -> bool { s == s.chars().rev().collect::<String>() }
這裡用了collect()，效率比較低，實際上當發現了首尾不一樣的字符時，就應該馬上返回false，而且最多比較一半的字符就行，效率大幅提升。
fn is_palindromic(s: String) -> bool { let mut c1 = s.chars(); let mut c2 = s.chars().rev(); for _i in 0..s.len() / 2 { if c1.next().unwrap() != c2.next().unwrap() { return false; } } true // s == s.chars().rev().collect::<String>() }
3）最後循環求和
這一步邏輯簡單，就不放代碼了。
第37題 左截和右截素數
問題描述
3797有一個有趣的屬性，它本身是素數，另外從左向右依次刪除一個數字，得到：797, 97, 和7，仍是素數，依次從右向左刪除一個數字，得到：379, 37, 和3，仍是素數。
總共只有11個這樣的素數，請求它們的和。
注意：2, 3, 5和7不計算在內。
解題思路
判斷是否為左截素數，循環調用remove()函數即可。
fn is_trun_left_prime(n: u64) -> bool { let mut s = n.to_string(); while s.len() > 0 { let p = s.parse::<u64>().unwrap(); if !primes::is_prime(p) { return false; } s.remove(0); } true }
類似的，換成pop()函數，可以判斷右截素數。
fn is_trun_right_prime(n: u64) -> bool { let mut s = n.to_string(); while s.len() > 0 { let p = s.parse::<u64>().unwrap(); if !primes::is_prime(p) { return false; } s.pop(); } true }
題目告訴了只有11個這樣的素數，暴力搜索到11個即可，主程序從略。
第38題 全數字的倍數
問題描述：
將192分別與1、2、3相乘：
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
連接這些乘積，我們得到一個1至9全數字的數192384576。我們稱192384576為192和(1,2,3)的連接乘積。
同樣地，將9分別與1、2、3、4、5相乘，得到1至9全數字的數918273645，即是9和(1,2,3,4,5)的連接乘積。
對於n > 1，所有某個整數和(1,2, … ,n)的連接乘積所構成的數中，最大的1至9全數字的數是多少？
解題步驟：
第32題與本題比較相似，有一個判斷全數字（有且僅有一次1到9）的函數，可以直接利用。
fn exists_only_once_1_to_9(s: &str) -> bool { let mut has_digit: Vec<bool> = vec![false; 10]; for ch in s.to_string().chars() { let c = ch.to_digit(10).unwrap() as usize; if c == 0 { return false; } if has_digit[c] { return false; } has_digit[c] = true; } true }
主程序用2層循環就可以搞定，運算量不大，不需要優化。
fn main() { let mut max = "".to_string(); for a in 1..=9876 { let mut s = String::from(""); for n in 1..=9 { let prod = a * n; s.push_str(&prod.to_string()); if !exists_only_once_1_to_9(&s) { break; } if s.len() == 9 && s > max { println!("{} x {:?} = {}", a, [1..n], s); max = s.clone(); } } } }
第39題 直角三角形
問題描述：
周長p的120的整數直角三角形共有3個：{20,48,52}, {24,45,51}, {30,40,50}，如果周長p<=1000，當p取何整數值時，滿足條件的直角三角數個數最多？
解題思路
先對給定的周長，把所有的直角三角形求出來。為了不輸出重複項，第二重循環的取值範圍要注意。
fn count_right_triangles(p: isize) -> isize { let mut count = 0; for a in 1..p { for b in a..p { let c = p - a - b; if c > 0 && a * a + b * b == c * c { count += 1; print!("{{{}, {}, {}}}, ", a, b, c) } } } count }
主程序比較簡單。
let mut max_count = 1; let mut max_p = 0; for p in 2..1000 { let count = count_right_triangles(p); if count > max_count { max_count = count; max_p = p; println!("p: {} max: {}", p, max_count); } } println!("p: {}", max_p);
在projecteuler中註冊一個賬號，可以添加好友，一起討論學習，我的Key是：
1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj
最新的源代碼同步更新在github上。
https://github.com/slofslb/rust-project-euler
歡迎加我微信討論解題技術，暗號：RUST。
當然用C，JAVA，Go，Haskell，Python，甚至Excel，我可以討論。
