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

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

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

学习任何一项技能最怕没有反馈,尤其是学英语、学编程的时候,一定要“用”,学习编程时有一个非常有用的网站,它就是“欧拉计划”,网址:https://projecteuler.net

英文如果不过关,可以到中文翻译的网站:http://pe-cn.github.io/

这个网站提供了几百道由易到难的数学问题,你可以用任何办法去解决它,当然主要还得靠编程,编程语言不限,论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法,当然如果你直接用google搜索答案就没任何乐趣了。

学习Rust最好先把基本的语法和特性看过一遍,然后就可以动手解题了,解题的过程就是学习、试错、再学习、掌握和巩固的过程,学习进度会大大加快。

第1~6题第7~12题第13~16题第17~21题第22~25题第26题第27~31题第32~34题

第35题 旋转素数

问题描述:

数字197称为旋转素数,因为它的几个数字经过轮转之后,197、971和719也都是素数,在100以内共有13个这样的素数:2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97,问100万之内有几个旋转素数?

解题思路:

1)旋转一个数

最容易想到的思路是取出最左边的数字,放到字符串的最右侧。

fn rotate_v1(n:u64) -> u64 {
    let mut s = n.to_string();
    let ch = s.chars().next().unwrap();
    s = s[1..].to_string();
    s.push(ch);
    s.parse::<u64>().unwrap()
}

因为remove()函数在移除最左侧的字符时,存储了该字符,直接放在右侧即可,代码更简洁和高效一些。

fn rotate(n: u64) -> u64 {
    let mut s = n.to_string();
    let ch = s.remove(0);
    s.push(ch);
    s.parse::<u64>().unwrap()
}

2)判断是否为旋转素数

这里不再重复发明轮子,直接使用了别人写好的primes函数库,需要在toml文件中增加一行依赖项。

[dependencies]
primes = "0.2"

另外,要注意处理一下数字里带0的特殊情况。

fn is_rotate_prime(n: u64) -> bool {
    if n.to_string().contains('0') {
        return false;
    }
    let mut r = n;
    for _i in 0..n.to_string().len() {
        if !primes::is_prime(r) {
            return false;
        }
        r = rotate(r);
    }
    true
}

3)主程序就非常容易了。

let mut count_primes = 0;
for n in 2..1_000_000 {
    if is_rotate_prime(n) {
        println!("{}", n);
        count_primes += 1;
    }
}
println!("{}", count_primes);

// 另外一种写法
let count_primes = (2..1_000_000)
        .filter(|&x| is_rotate_prime(x)).count();
println!("{}", count_primes);

语法知识点:

1)字符串的remove()函数和push()函数。

2)字符串的parse()函数可以转换成数值类型。

第36题 两种进制的回文数

问题描述:

数字585是回文数,即从左向右、从右向左读都是一样的,其二进制表示为1001001001,也是回文数。

请找出100万以下的所有回文数,并求和。注意,转换成二进制之后,左侧的0不计算在内。

解题步骤:

1)转换成二进制表示

费劲写了一个转换成二进制的函数。

fn to_radix2_string(n: u64) -> String {
    let mut d = n;
    let mut s:String = "".to_string();
    while d != 0 {
        let m = d % 2;
        s.push_str(&m.to_string());
        d /= 2;
    }
    s
}

发现又在重复造轮子,直接用format!宏就可以搞定。

let s = format!("{:b}", n);

2)判断是否回文

比较简单的写法。

fn is_palindromic(s: String) -> bool {
    s == s.chars().rev().collect::<String>() 
}

这里用了collect(),效率比较低,实际上当发现了首尾不一样的字符时,就应该马上返回false,而且最多比较一半的字符就行,效率大幅提升。

fn is_palindromic(s: String) -> bool {
    let mut c1 = s.chars();
    let mut c2 = s.chars().rev();
    for _i in 0..s.len() / 2 {
        if c1.next().unwrap() != c2.next().unwrap() {
            return false;
        }
    }
    true
    //    s == s.chars().rev().collect::<String>()
}

3)最后循环求和

这一步逻辑简单,就不放代码了。

第37题 左截和右截素数

问题描述

3797有一个有趣的属性,它本身是素数,另外从左向右依次删除一个数字,得到:797, 97, 和7,仍是素数,依次从右向左删除一个数字,得到:379, 37, 和3,仍是素数。

总共只有11个这样的素数,请求它们的和。

注意:2, 3, 5和7不计算在内。

解题思路

判断是否为左截素数,循环调用remove()函数即可。

fn is_trun_left_prime(n: u64) -> bool {
    let mut s = n.to_string();
    while s.len() > 0 {
        let p = s.parse::<u64>().unwrap();
        if !primes::is_prime(p) {
            return false;
        }
        s.remove(0);
    }
    true
}

类似的,换成pop()函数,可以判断右截素数。

fn is_trun_right_prime(n: u64) -> bool {
    let mut s = n.to_string();
    while s.len() > 0 {
        let p = s.parse::<u64>().unwrap();
        if !primes::is_prime(p) {
            return false;
        }
        s.pop();
    }
    true
}

题目告诉了只有11个这样的素数,暴力搜索到11个即可,主程序从略。

第38题 全数字的倍数

问题描述:

将192分别与1、2、3相乘:

192 × 1 = 192

192 × 2 = 384

192 × 3 = 576

连接这些乘积,我们得到一个1至9全数字的数192384576。我们称192384576为192和(1,2,3)的连接乘积。

同样地,将9分别与1、2、3、4、5相乘,得到1至9全数字的数918273645,即是9和(1,2,3,4,5)的连接乘积。

对于n > 1,所有某个整数和(1,2, … ,n)的连接乘积所构成的数中,最大的1至9全数字的数是多少?

解题步骤:

第32题与本题比较相似,有一个判断全数字(有且仅有一次1到9)的函数,可以直接利用。

fn exists_only_once_1_to_9(s: &str) -> bool {
    let mut has_digit: Vec<bool> = vec![false; 10];
    for ch in s.to_string().chars() {
        let c = ch.to_digit(10).unwrap() as usize;
        if c == 0 {
            return false;
        }
        if has_digit[c] {
            return false;
        }
        has_digit[c] = true;
    }
    true
}

主程序用2层循环就可以搞定,运算量不大,不需要优化。

fn main() {
    let mut max = "".to_string();
    for a in 1..=9876 {
        let mut s = String::from("");
        for n in 1..=9 {
            let prod = a * n;
            s.push_str(&prod.to_string());
            if !exists_only_once_1_to_9(&s) {
                break;
            }
            if s.len() == 9 && s > max {
                println!("{} x {:?} = {}", a, [1..n], s);
                max = s.clone();
            }
        }
    }
}

第39题 直角三角形

问题描述:

周长p的120的整数直角三角形共有3个:{20,48,52}, {24,45,51}, {30,40,50},如果周长p<=1000,当p取何整数值时,满足条件的直角三角数个数最多?

解题思路

先对给定的周长,把所有的直角三角形求出来。为了不输出重复项,第二重循环的取值范围要注意。

fn count_right_triangles(p: isize) -> isize {
    let mut count = 0;
    for a in 1..p {
        for b in a..p {
            let c = p - a - b;
            if c > 0 && a * a + b * b == c * c {
                count += 1;
                print!("{{{}, {}, {}}}, ", a, b, c)
            }
        }
    }
    count
}

主程序比较简单。

let mut max_count = 1;
let mut max_p = 0;
for p in 2..1000 {
    let count = count_right_triangles(p);
    if count > max_count {
        max_count = count;
        max_p = p;
        println!("p: {} max: {}", p, max_count);
    }
}
println!("p: {}", max_p);

在projecteuler中注册一个账号,可以添加好友,一起讨论学习,我的Key是:

1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj

最新的源代码同步更新在github上。

https://github.com/slofslb/rust-project-euler

欢迎加我微信讨论解题技术,暗号:RUST。

当然用C,JAVA,Go,Haskell,Python,甚至Excel,我可以讨论。

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

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

原始发表时间:2019-09-23

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用欧拉计划学Rust编程(第55~59题)

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

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

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

    申龙斌
  • 通过欧拉计划学习Rust编程(第17~21题)

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

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

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

    申龙斌
  • typescript里一些有趣的点

    在原生的JS里,null和undefined经常会导致BUG的产生, 在ts里,你又想用null,又担心出错的时候 你可以考虑用联合类型,当某值可能为 nu...

    liulun
  • 38.Swift学习之实用知识点

    Swift 中提供了很多实用的知识点,这些知识点极大提高了开发的效率。本章节主要罗列 Swift 中那些好用但未必人人都知道的知识点。

    YungFan
  • 【清华AI公开课】蚂蚁金服漆远:AI金融一秒核实2小时到账,99%准确率!

    清华大学“人工智能前沿与产业趋势”系列讲座的第五讲,由蚂蚁金服集团首席AI科学家与副总裁、达摩院金融智能负责人漆远亲临现场,与清华大学海峡研究院大数据AI中心专...

    新智元
  • 通过HTTP的HEADER完成各种骚操作

    作为一名专业的切图工程师,我从来不care网页的header,最多关心Status Code是不是200。但是HEADER真的很重要啊,客户端从服务器端获取内容...

    小美娜娜
  • Fiddler 高级用法:Fiddler Script 与 HTTP 断点调试

    之前在《关于 WEB/HTTP 调试利器 Fiddler 的一些技巧分享》中系统的介绍过 Fiddler 的原理与一些常见技巧,但那篇文章只是入门科普,并不深入...

    用户1177713
  • Swift学习笔记(一)

    Originalee

扫码关注云+社区

领取腾讯云代金券