用欧拉计划学习Rust编程(第27~31题)
- 2019 年 10 月 4 日
- 笔记
近想学习Libra数字货币的MOVE语言，发现它是用Rust编写的，所以先补一下Rust的基础知识。学习了一段时间，发现Rust的学习曲线非常陡峭，不过仍有快速入门的办法。
学习任何一项技能最怕没有反馈，尤其是学英语、学编程的时候，一定要“用”，学习编程时有一个非常有用的网站，它就是“欧拉计划”，网址：https://projecteuler.net
英文如果不过关，可以到中文翻译的网站：http://pe-cn.github.io/
这个网站提供了几百道由易到难的数学问题，你可以用任何办法去解决它，当然主要还得靠编程，编程语言不限，论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法，当然如果你直接用google搜索答案就没任何乐趣了。
学习Rust最好先把基本的语法和特性看过一遍，然后就可以动手解题了，解题的过程就是学习、试错、再学习、掌握和巩固的过程，学习进度会大大加快。
第27题
问题描述：
先借鉴第7题中的素数算法，将2百万之内的素数都求出来，公式n*n+a*n+b 最大取值不会超过2百万。
let max_number_to_check = 2_000_000; let mut prime_mask = vec![true; max_number_to_check]; prime_mask[0] = false; prime_mask[1] = false; const FIRST_PRIME_NUMBER: usize = 2; for p in FIRST_PRIME_NUMBER..max_number_to_check { if prime_mask[p] { let mut i = 2 * p; while i < max_number_to_check { prime_mask[i] = false; i += p; } } }
求方程得到的连续素数的个数。这里要用isize，因为求值时可能会出现负数，如果用usize，运行时会发生溢出错误。
fn consecutive_primes(prime_mask: &[bool], a: isize, b: isize) -> u32 { for n in 0..1000 { let y: isize = n * n + a * n + b; if y < 0 || !prime_mask[y as usize] { return n as u32; } } 0 }
最后，进行暴力循环即可，能够连续生成71个素数，不可思议。
let mut max_prime_len = 0; for a in -999..=999 { for b in -1000..=1000 { let prime_series_len = consecutive_primes(&prime_mask, a, b); if prime_series_len > max_prime_len { max_prime_len = prime_series_len; println!( "primes: {} a: {} b: {} a * b = {}", prime_series_len, a, b, a * b ); } } }
第28题
问题描述：
求解思路：
找规律，右上角那个数是完全平方数，其它三个角的数正好递减。
fn main() { let mut sum = 1; for i in (3..=1001).step_by(2) { let upperright = i * i; sum += upperright; sum += upperright - (i - 1) * 1; sum += upperright - (i - 1) * 2; sum += upperright - (i - 1) * 3; } println!("{}", sum); }
知识点：
步长大于1的迭代器用step_by()。
第29题
问题描述
解题思路
利用大整数函数库，写一个power()函数，Debug模式下运行10秒，Release模式下不到1秒。
extern crate num_bigint; use num_bigint::BigUint; fn main() { let mut v: Vec<BigUint> = vec![]; for a in 2..=100 { for b in 2..=100 { let x = power(a, b); if !v.contains(&x) { v.push(x); } } } println!("{}", v.len()); } fn power(a: u64, b: u64) -> BigUint { let mut prod = BigUint::from(1 as u64); for _i in 0..b { prod *= BigUint::from(a); } prod }
第30题
问题描述
解题思路
一个关键的表达式，各位数字的5次方，再求和。
n.to_string() .chars() .map(|c| c.to_digit(10).unwrap().pow(5)) .sum::<u32>();
主程序就非常简单了。
let mut s = 0; for n in 2..999999 { let sum_pow = n .to_string() .chars() .map(|c| c.to_digit(10).unwrap().pow(5)) .sum::<u32>(); if sum_pow == n { println!("{}", n); s += n; } } println!("sum: {}", s);
也可以写一个函数is_power_number()，再利用filter函数一行完成。
fn is_power_number(n: u32) -> bool { n == n.to_string() .chars() .map(|c| c.to_digit(10).unwrap().pow(5)) .sum::<u32>() } fn main() { let sum_pow = (2..999999).filter(|&x| is_power_number(x)).sum::<u32>(); println!("{}", sum_pow); }
第31题
问题描述
求解
采取了一种丑陋无比的写法，暴力解决了问题。
fn main() { let mut count = 0; for a in 0..=200 { for b in 0..=100 { for c in 0..=40 { for d in 0..=20 { for e in 0..=10 { for f in 0..=4 { for g in 0..=2 { for h in 0..=1 { let price = a + b * 2 + c * 5 + d * 10 + e * 20 + f * 50 + g * 100 + h * 200; if price == 200 { count += 1; } } } } } } } } } println!("{}", count); }
在projecteuler中注册一个账号，可以添加好友，一起讨论学习，我的Key是：
1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj
最新的源代码已同步更新在github上。
https://github.com/slofslb/rust-project-euler
