专栏首页申龙斌的程序人生用欧拉计划学Rust编程(第55~59题)

用欧拉计划学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

本文分享自微信公众号 - 申龙斌的程序人生(slbGTD)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用欧拉计划学Rust编程(第35~38题)

    最近想学习Libra数字货币的MOVE语言,发现它是用Rust编写的,所以先补一下Rust的基础知识。学习了一段时间,发现Rust的学习曲线非常陡峭,不过仍有快...

    申龙斌
  • 用欧拉计划学习Rust编程(第40~45题)

    最近想学习Libra数字货币的MOVE语言,发现它是用Rust编写的,所以先补一下Rust的基础知识。学习了一段时间,发现Rust的学习曲线非常陡峭,不过仍有快...

    申龙斌
  • 通过欧拉计划学Rust编程(第686题)

    由于研究Libra等数字货币编程技术的需要,学习了一段时间的Rust编程,一不小心刷题上瘾。

    申龙斌
  • 1份sql注入学习资料,据说从入门到精通

    ------------------------------------------------------------------------

    用户1631416
  • REALM: Retrieval-Augmented Language Model Pre Training

    去年可以说是语言模型快速发展的一年,BERT、XLNET、Albert等等模型不断刷新各个NLP榜单。在NLP榜单中比较引人注目的应该属于阅读理解型的任务,例如...

    朴素人工智能
  • 【ICML 2020】REALM: Retrieval-Augmented Language Model PreTraining

    去年可以说是语言模型快速发展的一年,BERT、XLNET、Albert等等模型不断刷新各个NLP榜单。在NLP榜单中比较引人注目的应该属于阅读理解型的任务,例如...

    朴素人工智能
  • SAP Fiori UI上关于时区Timezone的一些问题和解决方案

    先说问题,我创建了一个Lead,创建时间14:21, TimeZone is UTC+8.

    Jerry Wang
  • vb.net 获取CPU序列号

    巴西_prince
  • VBA实用小程序54: 计算字符串中指定子字符串出现的次数

    下面的自定义函数iCountString可以用来统计子字符串在字符串中出现的次数:

    fanjy
  • GitHub日收7000星,Windows计算器项目开源即爆红!

    昨日,微软官宣在 MIT 许可证下开源了 Windows 10 操作系统自带的计算器应用,源代码已托管在 GitHub 上。该项目发布即蹿红,在 GitHub...

    AI科技大本营

扫码关注云+社区

领取腾讯云代金券