用欧拉计划学习Rust编程(第27~31题)
用欧拉计划学习Rust编程(第27~31题)
近想学习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