最近想学习Libra数字货币的MOVE语言,发现它是用Rust编写的,所以先补一下Rust的基础知识。学习了一段时间,发现Rust的学习曲线非常陡峭,不过仍有快速入门的办法。
学习任何一项技能最怕没有反馈,尤其是学英语、学编程的时候,一定要“用”,学习编程时有一个非常有用的网站,它就是“欧拉计划”,网址:https://projecteuler.net
英文如果不过关,可以到中文翻译的网站:http://pe-cn.github.io/
这个网站提供了几百道由易到难的数学问题,你可以用任何办法去解决它,当然主要还得靠编程,编程语言不限,论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法,当然如果你直接用google搜索答案就没任何乐趣了。
学习Rust最好先把基本的语法和特性看过一遍,然后就可以动手解题了,解题的过程就是学习、试错、再学习、掌握和巩固的过程,学习进度会大大加快。
问题描述:
可以看出,125874和它的两倍251748拥有同样的数字,只是排列顺序不同。
有些正整数x满足2x、3x、4x、5x和6x都拥有相同的数字,求其中最小的正整数。
解题思路:
没写程序的时候我已经知道答案了,因为我以前写过《吉利数字》这样一篇文章。
fn main() {
for x in 100000..=999999 {
if is_permuted(x) {
println!("{}", x);
break;
}
}
}
fn is_permuted(x: u32) -> bool {
// 拆成6个数字
let vx: Vec<u32> = x
.to_string()
.chars()
.map(|c| c.to_digit(10).unwrap())
.collect();
for i in 2..=6 {
let m = i * x;
let vm: Vec<u32> = m
.to_string()
.chars()
.map(|c| c.to_digit(10).unwrap())
.collect();
// 每个数字都在原来的集合里出现过
for e in vm {
if !vx.contains(&e) {
return false;
}
}
}
return true;
}
问题描述:
解题步骤:
利用大整数函数库,很容易计算阶乘,再计算组合数。
extern crate num_bigint;
use num_bigint::BigUint;
fn main() {
// 先把一些阶乘计算好,保存起来
let mut fact = vec![BigUint::from(1 as u64); 101];
let mut a = BigUint::from(1 as u64);
for n in 2..=100 {
a *= BigUint::from(n as u64);
fact[n] = a.clone();
}
//println!("{:?}", fact);
let mut count = 0;
for n in 1..=100 {
for r in 1..=n {
let comb = &fact[n] / &fact[r] / &fact[n - r];
if comb > BigUint::from(1_000_000 as u64) {
println!("{} {} {}", n, r, comb.to_string());
count += 1;
}
}
}
println!("{}", count);
}
优化:
再仔细研究一下这些组合数,可以发现一个规律:C(90, 1), C(90, 2), C(90, 3)都小于1百万,当C(90, 4)时,值大于1百万。
根据组合数的性质,C(90, 86) 一定也肯定大于1百万,这样不用进行大量的计算,可以知道C(90, *)这样的情况中,大于1百万的组合有 86 - 4 + 1 = 83 组。
把上面的 count += 1;
换成下面两行,可以大幅提升性能:
count += n - r - r + 1;
break;
在projecteuler中注册一个账号,可以添加好友,一起讨论学习,我的Key是:
1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj
最新的源代码同步更新在github上。
https://github.com/slofslb/rust-project-euler