用欧拉计划学Rust编程(第55~59题)
最近想学习Libra数字货币的MOVE语言，发现它是用Rust编写的，所以先补一下Rust的基础知识。学习了一段时间，发现Rust的学习曲线非常陡峭，不过仍有快速入门的办法。
学习任何一项技能最怕没有反馈，尤其是学英语、学编程的时候，一定要“用”，学习编程时有一个非常有用的网站，它就是“欧拉计划”，网址：https://projecteuler.net
英文如果不过关，可以到中文翻译的网站：http://pe-cn.github.io/
这个网站提供了几百道由易到难的数学问题，你可以用任何办法去解决它，当然主要还得靠编程，编程语言不限，论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法，当然如果你直接用google搜索答案就没任何乐趣了。
学习Rust最好先把基本的语法和特性看过一遍，然后就可以动手解题了，解题的过程就是学习、试错、再学习、掌握和巩固的过程，学习进度会大大加快。
第55题 利克瑞尔数
问题描述：
将47倒序并相加得到47 + 74 = 121，是一个回文数。
不是所有的数都能像这样迅速地变成回文数。例如，
349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337
也就是说，349需要迭代三次才能变成回文数。
尽管尚未被证实，但有些数，例如196，被认为永远不可能变成回文数。如果一个数永远不可能通过倒序并相加变成回文数，就被称为利克瑞尔数。出于理论的限制和问题的要求，在未被证否之前，我们姑且就认为这些数确实是利克瑞尔数。除此之外，已知对于任意一个小于一万的数，它要么在迭代50次以内变成回文数，要么就是没有人能够利用现今所有的计算能力将其迭代变成回文数。事实上，10677是第一个需要超过50次迭代变成回文数的数，这个回文数是 4668731596684224866951378664（53次迭代，28位数）。
令人惊讶的是，有些回文数本身也是利克瑞尔数数；第一个例子是4994。
小于一万的数中有多少利克瑞尔数？
注意：2007年4月24日，题目略作修改，以强调目前利克瑞尔数理论的限制。
解题思路：
需要用到大整数运算库，前后颠倒相加，再判断是否是回文数，逻辑并不复杂。
extern crate num_bigint;
use num_bigint::BigUint;
fn main() {
let mut count = 0;
for n in 1..10000 {
if is_lychrel_number(n) {
println!("{}", n);
count += 1;
}
}
println!("count: {}", count);
}
fn is_lychrel_number(n: u64) -> bool {
let mut x = BigUint::from(n);
for _i in 0..50 {
x = lychrel_transform(&x);
if is_palindromic(&x) {
return false;
}
}
// 永远变不成回文数，只判断了50次
true
}
use std::str::FromStr;
// 前后颠倒，求和
fn lychrel_transform(n: &BigUint) -> BigUint {
let rev_str = n.to_string().chars().rev().collect::<String>();
let rev_n = BigUint::from_str(&rev_str).unwrap();
n + rev_n
}
fn is_palindromic(n: &BigUint) -> bool {
let str_n = n.to_string();
let rev_str = str_n.chars().rev().collect::<String>();
str_n == rev_str
}
第56题 幂的数字和
问题描述：
解题步骤：
求各位的数字和，类似的问题出现过许多次。
extern crate num_bigint;
use num_bigint::BigUint;
fn main() {
let mut max_sum = 0;
for a in 1..100 {
for b in 1..100 {
let s = power(a, b).to_string();
let sum_digits = s.chars().map(|ch| ch.to_digit(10).unwrap()).sum::<u32>();
if sum_digits > max_sum {
max_sum = sum_digits;
println!(
"{} ^ {} len: {} sum of digits: {}",
a,
b,
s.len(),
sum_digits
);
}
}
}
println!("{}", max_sum);
}
fn power(a: u64, b: u64) -> BigUint {
let mut prod = BigUint::from(a as u64);
for _i in 0..b {
prod *= BigUint::from(a as u64);
}
prod
}
第57题 平方根逼近
问题描述：
解题步骤：
根据第i项，很容易推出第i+1项。
数字的位数很多，需要用到大整数计算。
extern crate num_bigint;
use num_bigint::BigUint;
fn main() {
let mut count = 0;
let mut a = BigUint::from(3 as u64);
let mut b = BigUint::from(2 as u64);
for _i in 2..=1000 {
let c = &a + &b;
a = &c + &b;
b = c;
if a.to_string().len() > b.to_string().len() {
count += 1;
//println!("{} {}", a, b);
}
}
println!("{}", count);
}
第58题 螺旋素数
问题描述：
解题步骤：
大量素数的判断时，用PrimeSet，比primes::is_prime()要快。每一圈右下角的数等于边长的平方，四角上的数的计算用了一点小技巧。
use primes::PrimeSet;
fn main() {
let mut pset = PrimeSet::new();
let mut count_prime = 0;
for n in (3..).step_by(2) { // 边长
let lower_right = n * n;
let prime_four_corner = (0..4)
.map(|x| lower_right - (n - 1) * x)
.filter(|&x| pset.is_prime(x));
count_prime += prime_four_corner.count();
let percent = (count_prime as f32) / ((2 * n - 1) as f32);
if percent < 0.1 {
println!("{} count: {} percent: {}", n, count_prime, percent);
break;
}
}
}
第59题 异或解密
问题描述：
计算机上的每个字符都被指定了一个独特的代码，其中被广泛使用的一种是ASCII码（美国信息交换标准代码）。例如，大写字母A = 65，星号（*） = 42，小写字母k = 107。
一种现代加密方法是将一个文本文档中的符号先转化为ASCII码，然后将每个字节异或一个根据密钥确定的值。使用异或进行加密的好处在于，只需对密文使用相同的密钥再加密一次就能得到明文，例如，65 XOR 42 = 107，而107 XOR 42 = 65。
为了使加密难以破解，密钥要和明文一样长，由随机的字节构成。用户会把加密过的信息和密钥放置在不同的地方，解密时二者缺一不可。
不幸的是，这种方法对大多数人来说并不实用，因此一个略有改进的方法是使用一个密码作为密钥。密码的长度很有可能比信息要短，这时候就循环重复使用这个密码进行加密。这种方法需要达到一种平衡，一方面密码要足够长才能保证安全，另一方面需要充分短以方便记忆。
你的破解任务要简单得多，因为密钥只由三个小写字母构成。文本文档cipher.txt（右击并选择“目标另存为……”）中包含了加密后的ASCII码，并且已知明文包含的一定是常见的英文单词，解密这条消息并求出原文的ASCII码之和。
解题步骤：
1）读文件，保存在数组中
cipher.txt文件中是ASCII码数值，转换成u8类型存储。
let data = std::fs::read_to_string("cipher.txt").expect("文件无法打开");
let xs: Vec<&str> = data.split(",").collect();
let letters: Vec<u8> = xs.iter().map(|x| x.parse::<u8>().unwrap()).collect();
2）统计
解密的文本是常见的英文单词，而且密钥是小写字母，只需用这26个小写字母分别与这些文本进行XOR，统计分别得到的英文单词的个数，哪个最多哪个就最可能是正确的密码。
3个小写字母密钥针对不同的位置进行XOR操作，index取0，1，2，表示位置索引。
fn guess_pass(letters: &Vec<u8>, index: usize) -> char {
let mut key = '*';
let mut max_count = 0;
for pass in ('a' as u8)..=('z' as u8) {
let mut count = 0;
for (i, ch) in letters.iter().enumerate() {
if i % 3 == index {
let a = (ch ^ pass) as char;
if ('A'..='Z').contains(&a) || ('a'..='z').contains(&a) {
count += 1;
}
}
}
if count > max_count {
max_count = count;
key = pass as char;
}
}
key
}
3）猜三个位置上的密码
let key = [
guess_pass(&letters, 0),
guess_pass(&letters, 1),
guess_pass(&letters, 2),
];
println!("key: {:?}", key);
4）解码，求和
let mut sum: u32 = 0;
for (i, ch) in letters.iter().enumerate() {
let a = ch ^ (key[i % 3] as u8);
sum += a as u32;
print!("{}", a as char);
}
println!("\n");
println!("{}", sum);
在projecteuler中注册一个账号，可以添加好友，一起讨论学习，我的Key是：
1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj
最新的源代码同步更新在github上。
https://github.com/slofslb/rust-project-euler