用歐拉計劃學習Rust編程(第40~45題)
- 2019 年 10 月 10 日
- 筆記
最近想學習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題•第22~34題•第35~39題
第40題 錢珀瑙恩常數
問題描述：
將所有正整數連接起來構造的一個十進位無理數如下所示：
0.123456789101112131415161718192021…
可以看出小數點後第12位數字是1。如果dn表示上述無理數小數點後的第n位數字，求下式的值：d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
解題思路：
演算法很簡單，需要留意差1的BUG。
let max_digits = 1_000_001; let mut digits: Vec<usize> = vec![0; max_digits]; let mut pos = 1; 'a: for i in 1.. { for ch in i.to_string().chars() { let d = ch.to_digit(10).unwrap() as usize; if pos >= max_digits { break 'a; } digits[pos] = d; pos += 1; } } println!( "{}", digits[1] * digits[10] * digits[100] * digits[1000] * digits[10000] * digits[100000] * digits[1000000] );
最後的乘積計算，可以練習一下map()和fold()的寫法。
let d: Vec<usize> = (0..=6).map(|x| digits[10_usize.pow(x)]).collect(); println!("{:?}", d); let p: usize = (0..=6) .map(|x| digits[10_usize.pow(x)]) .fold(1, |x, a| x * a); println!("{}", p);
第41題 全數字的素數
問題描述：
如果一個n位數恰好使用了1至n每個數字各一次，我們就稱其為全數字的。例如，2143就是一個4位全數字數，同時它恰好也是一個素數。
最大的全數字的素數是多少？
解題步驟：
1）生成全排列
第24題中已經有一個全排列的生成演算法，增加一個返回值，如果已經到達了最後的一個排列，就返回false，方便主程式退出循環。
fn next_perm(v: &mut [u64]) -> bool { let mut i = v.len() - 2; while v[i] > v[i + 1] { if i == 0 { return false; } i -= 1; } let mut j = v.len() - 1; while i < j && v[i] > v[j] { j -= 1; } swap(v, i, j); i += 1; j = v.len() - 1; while i < j { swap(v, i, j); i += 1; j -= 1; } true }
2）向量轉換成數值
為了後面判斷素數，需要將[1, 2, 3, 4, 5, 6, 7]這樣的向量轉換成 1234567。
我一開始的想法是把每個數字轉換成字元串，拼在一起，再轉換成數值。
let v_str = v.iter().map(|x| x.to_string()).collect::<String>(); let d = v_str.parse::<usize>().unwrap();
後來發現，用一系列整數運算可以完成這個任務，程式碼比較簡潔，但我沒有比較兩種辦法的效率，初步估計整數運算的效率會更高一些。
let d = v.iter().fold(0, |x, a| 10 * x + a);
3）主程式
準備工作完成後，主程式沒有難度。我先用4位整數驗證了程式的正確性，再跑9位、8位的情況，最後在7位的時候發現了答案。
let mut v = [1, 2, 3, 4, 5, 6, 7]; let mut max_prime = 0; while next_perm(&mut v) { let d = v.iter().fold(0, |x, a| 10 * x + a); if primes::is_prime(d as u64) && d > max_prime { println!("{}", d); max_prime = d; } }
4）不重新發明輪子
我以前為了練習演算法，自己寫了全排列的生成函數，實際上別人已經寫好了這類函數庫，直接拿來用就行。
use permutohedron::heap_recursive; fn main() { let mut max_prime = 0; let mut data = [1, 2, 3, 4, 5, 6, 7]; heap_recursive(&mut data, |permutation| { let v = permutation.to_vec(); let d = v.iter().fold(0, |x, a| 10 * x + a); if primes::is_prime(d as u64) && d > max_prime { println!("{}", d); max_prime = d; } }) }
5）更為高效的演算法
因為題目要求最大的全排列素數，前面這些演算法都要把所有的排列組合都嘗試一遍，效率極低。
最高效的辦法是修改最早的全排列生成演算法，讓next_perm_desc()降序生成，這樣找到的第一個素數就是最終答案。
fn main() { let mut v = [7, 6, 5, 4, 3, 2, 1]; loop { let d = v.iter().fold(0, |x, a| 10 * x + a); if primes::is_prime(d as u64) { println!("{}", d); break; } if !next_perm_desc(&mut v) { break; } } } // 降序全排列 fn next_perm_desc(v: &mut [u64]) -> bool { let mut i = v.len() - 2; while v[i] < v[i + 1] { if i == 0 { return false; } i -= 1; } let mut j = v.len() - 1; while i < j && v[i] < v[j] { j -= 1; } swap(v, i, j); i += 1; j = v.len() - 1; while i < j { swap(v, i, j); i += 1; j -= 1; } true } fn swap(v: &mut [u64], i: usize, j: usize) { let temp = v[i]; v[i] = v[j]; v[j] = temp; }
第42題 編碼三角形數
問題描述
解題思路
1）讀文件內容到數組中
let data = std::fs::read_to_string("words.txt").expect("讀文件失敗"); // 刪除引號 let data2: String = data.chars().filter(|c| *c != '"').collect(); let names: Vec<&str> = data2.split(",").collect();
2）準備足夠的三角數，以備將來進行快速判斷
let mut tri_numbers = vec![]; for i in 1..=100 { tri_numbers.push(i * (i + 1) / 2); } //println!("{:?}", tri_numbers);
3）字元在字母表中的順序號
最早是用查找方式實現的。
let letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; letters.chars().position(|c| c == ch).unwrap() + 1
在Rust中一個字元可以直接轉換成u8類型，就是其ASCII編碼值，'A'的編碼為65，字元與'A'的差值就是編號，更加高效。
// 一個字元在字母表中分數，'A' -> 1，'B' -> 2 fn letter_number(ch: char) -> u8 { (ch as u8) - 64 }
4）單詞的分數
常規的寫法：
fn word_score(word: &str) -> usize { let mut score = 0; for ch in word.chars() { score += letter_number(ch) as usize; } score }
可以用函數式編程的寫法：
fn word_score(word: &str) -> usize { word.chars().map(|ch| letter_number(ch) as usize).sum() }
5）主循環算分求和即可。
前面的函數都比較簡單，可以寫在一行，最後的主程式也可以很精鍊。
let mut count = 0; for name in names { let word_score = name.chars().map(|ch| ch as usize - 64).sum(); if tri_numbers.contains(&word_score) { //println!("{} {}", name, word_score); count += 1; } } println!("{}", count);
第43題 子串的可整除性
問題描述：
問題分解：
1）找出0到9的所有全排列
2）找出三位數的子串
3）暴力循環求解
第一步，找全排列
在第24題和第41題已經了解了全排列的演算法，這裡直接利用nnext_perm()函數即可，需要注意0不能出現在最左邊。
第二步：取出3位數字
這裡以取d2 d3 d4三位數字為例：
let v_str = v.iter().map(|x| x.to_string()).collect::<String>(); let sub3 = &v_str[1..4]; let d = sub3.parse::<u32>().unwrap();
第三步，可以寫出主程式：
let mut v = [1, 0, 2, 3, 4, 5, 6, 7, 8, 9]; let primes = [2, 3, 5, 7, 11, 13, 17]; let mut sum: u64 = 0; loop { let v_str = v.iter().map(|x| x.to_string()).collect::<String>(); for i in 1..=7 { let sub3 = &v_str[i..i + 3]; let d = sub3.parse::<u32>().unwrap(); if d % primes[i-1] != 0 { break; } if i == 7 { println!("{}", v_str); sum += v_str.parse::<u64>().unwrap(); } } if !next_perm(&mut v) { break; } } println!("sum: {}", sum);
第四步：優化
前面的演算法中大量在字元串和數字之間進行轉換，效率還有點低，實際上可以全部利用整數的運算，效率可以提高很多，最後的程式碼：
fn main() { let mut v = [0, 9, 8, 7, 6, 5, 4, 3, 2, 1]; let mut sum: u64 = 0; while next_perm(&mut v) { let num = v.iter().fold(0, |x, a| 10 * x + a); if is_divisibility(num) { println!("{}", num); sum += num; } } println!("sum: {}", sum); } fn is_divisibility(num: u64) -> bool { let primes = [2, 3, 5, 7, 11, 13, 17]; let mut n = num % 1_000_000_000; for i in (0..=6).rev() { let sub3 = n % 1000; if sub3 % primes[i] != 0 { return false; } n = n / 10; } true } fn next_perm(v: &mut [u64]) -> bool { let mut i = v.len() - 2; while v[i] > v[i + 1] { if i == 0 { return false; } // 已經全部從大到小排列了 i -= 1; } let mut j = v.len() - 1; while i < j && v[i] > v[j] { j -= 1; } swap(v, i, j); i += 1; j = v.len() - 1; while i < j { swap(v, i, j); i += 1; j -= 1; } true } fn swap(v: &mut [u64], i: usize, j: usize) { let temp = v[i]; v[i] = v[j]; v[j] = temp; }
第44題 五邊形數
問題描述：
問題分解：
1）生成足夠的五邊形數，備用
一開始不知道最終答案的範圍，先生成1萬個備用。
let mut penta: Vec<u64> = vec![0]; for i in 1..10000 { penta.push(i * (3 * i - 1) / 2); }
2）雙重循環搜索
暴力搜索，判斷和與差是否也是五邊形數，竟然只找到一個滿足條件的解，輸入到projecteuler網站，發現竟然就是正確答案。
for k in 2..3000 { for j in (1..k).rev() { let d = penta[k] - penta[j]; let sum = penta[k] + penta[j]; if penta.contains(&d) && penta.contains(&sum) { println!("j:{} k:{} pj:{} pk:{} diff:{}", j, k, penta[j], penta[k], d); } } }
3）優化
判斷一個數是不是五邊形數用contains()效率並不高，特別是集合的元素非常多時，得把高中的二次函數的求解公式翻出來。
如果p是五邊形數，1+24*p應該是完全平方數，分子還要能被6整除。
fn is_penta(p: u64) -> bool { let t = ((1 + 24 * p) as f64).sqrt() as u64; // sqrt(b*b - 4*a*c) if t * t != (1 + 24 * p) { return false; } (t + 1) % 6 == 0 }
主程式仍用雙重循環搜索。
let mut min_d = std::u64::MAX; // 改為2.. 可以證明結果的正確性，但要運行相當長的時間 for k in 2..10000 { let pk = penta(k); if pk - penta(k-1) > min_d {break;} for j in (1..k).rev() { let pj = penta(j); let d = pk - pj; if d < min_d && is_penta(d) && is_penta(pk + pj) { println!("j:{} k:{} pj:{} pk:{} diff:{}",j, k, pj, pk, d); min_d = d; break; } } }
這個題找到一個答案的速度非常快，但並不能充分地證明它就是最小的d，應該再繼續向後搜索五邊形數，當相鄰的五邊形數的差都大於min_d時，才證明了的確找到了最小的d，但需要運行相當長的時間。
第45題 三角形數、五邊形數和六角形數
問題描述：
問題求解：
這個題我沒有採用上一題的二次函數求解的公式，準備好10萬個三角數和五邊形數，暴力搜索找到了答案。
let mut tri: Vec<u64> = vec![]; for i in 1..100000 { tri.push(i * (i + 1) / 2); } let mut penta: Vec<u64> = vec![]; for i in 1..100000 { penta.push(i * (3 * i - 1) / 2); } for i in 2..30000 { let hex = i * (2 * i - 1); if tri.contains(&hex) && penta.contains(&hex) { println!("i: {} hexagonal: {}", i, hex); } }
在projecteuler中註冊一個帳號，可以添加好友，一起討論學習，我的Key是：
1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj
最新的源程式碼同步更新在github上。
https://github.com/slofslb/rust-project-euler
歡迎加我微信討論解題技術，暗號：RUST。
當然用C，JAVA，Go，Haskell，Python，甚至Excel，都可以討論。
