用欧拉计划学Rust编程(第52~53题)
最近想学习Libra数字货币的MOVE语言，发现它是用Rust编写的，所以先补一下Rust的基础知识。学习了一段时间，发现Rust的学习曲线非常陡峭，不过仍有快速入门的办法。
学习任何一项技能最怕没有反馈，尤其是学英语、学编程的时候，一定要“用”，学习编程时有一个非常有用的网站，它就是“欧拉计划”，网址：https://projecteuler.net
英文如果不过关，可以到中文翻译的网站：http://pe-cn.github.io/
这个网站提供了几百道由易到难的数学问题，你可以用任何办法去解决它，当然主要还得靠编程，编程语言不限，论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法，当然如果你直接用google搜索答案就没任何乐趣了。
学习Rust最好先把基本的语法和特性看过一遍，然后就可以动手解题了，解题的过程就是学习、试错、再学习、掌握和巩固的过程，学习进度会大大加快。
第52题 重排的倍数
问题描述：
可以看出，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;
}
第53题 组合数选择
问题描述：
解题步骤：
利用大整数函数库，很容易计算阶乘，再计算组合数。
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