刷完欧拉计划中的63道基础题,能学会Rust编程吗?

我为什么学Rust

2019年6月18日,Facebook发布了数字货币Libra的技术白皮书,我也第一时间体验了一下它的智能合约编程语言MOVE,发现这个MOVE是用Rust编写的,看来想准确理解MOVE的机制,还需要对Rust有深刻的理解,所以又开始了Rust的快速入门学习。

欧拉计划

看了一下网上有关Rust的介绍,都说它的学习曲线相当陡峭,曾一度被其吓着,后来发现Rust借鉴了Haskell等函数式编程语言的优点,而我以前专门学习过Haskell,经过一段时间的入门学习,我现在已经喜欢上这门神奇的语言。

入门资料我用官方的《The Rust Programming Language》,非常权威,配合着《Rust by example》这本书一起学习,效果非常不错。

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

如果你的英文不过关,有人已经将几乎所有的题目翻译成了中文,网址:http://pe-cn.github.io,本书中的许多题目的描述都照搬了该网站的翻译。

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

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

题型介绍

欧拉计划中的各题都标出了难度系数,以百分数来表示,5%是其中难度最低的,难度最高的为100%,截止到2019年10月10日,难题系数为5%的题共有63道,可以作为Rust的入门练手题。

这些初级难度的题目,主要涉及整除性质、素数、因子、分数、回文数、阶乘、三角数、大整数、数字序列、路径计算、日期、全排列、组合数、初级密码学等方面,通过解这些题,可以了解Rust中的基本数据类型,向量用法,理解Rust中特有的所有权体系,体会函数式编程的思维等。

在欧拉计划的官网上注册账号后,如果得出了某题的正确答案,可以在论坛里参与相关的讨论,看看其他人的解题思路和源代码,获得一些灵感。

下面我把63道题分为几大类,通过研究这些题的解法,我学会了Rust的一些语法知识点和编程算法。

第一部分 小试牛刀

这一部分题型相对简单,可以了解Rust的基本数据类型,整数运算、文件读取和字符串操作。

  • 第1题 筛选整数
  • 第2题 偶斐波那契数
  • 第3题 最大质因数
  • 第4题 最大回文乘积
  • 第5题 最小倍数
  • 第6题 平方和与和的平方之差
  • 第8题 连续数字最大乘积
  • 第17题 表达数字的英文字母计数
  • 第22题 姓名得分

主要的语法知识点:

  • Rust的安装
  • cargo包管理器的使用
  • vscode中相关插件的安装,程序的调试
  • println!宏的使用
  • 循环语句for的写法,注意与C语言的不同之处
  • mut关键字,体会什么是可修改的变量
  • 向量Vec的基本用法,vec!宏的使用
  • 迭代器iter()和enumerate()的基本用法
  • 延迟评价的设计理念
  • 强类型特点,几种数据类型
  • 字符串的基本操作,字符串切片slice的理解
  • 字符与整型的转换

第二部分 序列

根据一定的规则,一个数字可以变换为另一个数字,但最后会收敛到一个特定的值。

  • 第14题 最长考拉兹序列
  • 第92题 平方数字链

主要的语法知识点:

  • 递归函数的写法
  • chars()、map()、sum()和count()等函数的应用
  • 如何优化程序的性能
  • if表达式

第三部分 因子

一个数有质因子,真因子等概念,然后引出了亲和数、盈数等有趣的数字。

  • 第12题 因子繁多的三角数
  • 第21题 亲和数
  • 第23题 非盈数之和
  • 第47题 不同的质因数

主要的语法知识点:

  • 因子、质因子的求法
  • 数组作为函数参数的写法:&[bool]
  • primes函数库的使用

第四部分 素数

欧拉是一个数学家,所以欧拉计划中题型以数学题为主,而其中与素数有关的问题特别多。

  • 第7题 第10001个素数
  • 第10题 素数的和
  • 第27题 二次多项式生成素数
  • 第35题 旋转素数
  • 第37题 左截和右截素数
  • 第50题 连续素数的和
  • 第58题 螺旋素数
  • 第97题 非梅森大素数

主要的语法或算法:

  • 筛子求素数的算法
  • const常量定义的写法
  • usize和isize的应用
  • 字符串的push()、remove()和parse()函数的应用
  • filter()和take()的使用

第五部分 数字游戏

勾股数、幂运算、阶乘、回文等一些数字游戏。

  • 第9题 特殊勾股数
  • 第11题 方阵中的最大乘积
  • 第28题 螺旋数阵对角线
  • 第30题 各位数字的五次幂
  • 第32题 全数字的乘积
  • 第34题 各位数字的阶乘
  • 第36题 两种进制的回文数
  • 第38题 全数字的倍数
  • 第40题 钱珀瑙恩常数
  • 第46题 哥德巴赫的另一个猜想
  • 第52题 重排的倍数
  • 第206题 被遮挡的平方数

主要的语法知识点:

  • 二维数组的写法
  • 步长大于1的迭代器用step_by()
  • chars()和map()的组合运用
  • 数字的二进制转换

第六部分 大整数

各种编程语言通常都提供64位的整数,表示的最大值为18446744073709551615,也只有20位数字。对于超过这个范围的整数,平常的数据类型就无法进行运算,这时需要用到大整数函数库num-bigint。

  • 第13题 大整数求和
  • 第16题 幂的数字和
  • 第20题 阶乘数字和
  • 第25题 一千位斐波那契数
  • 第29题 不同的幂
  • 第48题 自幂
  • 第53题 组合数选择
  • 第55题 利克瑞尔数
  • 第56题 幂的数字和
  • 第57题 平方根逼近
  • 第63题 幂次与位数

主要的语法知识点:

  • 字符串转换成BigUInt
  • 切片slice的使用
  • fold()函数的学习

第七部分 路径

求不同的路径或者最大路径,学习递归算法和改进算法。

  • 第15题 网格路径
  • 第18题 最大路径和I
  • 第67题 最大路径和II

主要的语法和算法:

  • 把一个可修改的向量当作函数参数的写法,&mut Vec<u64>
  • 递归中缓存一些运算结果
  • 读文件的操作
  • 路径中分层计算的算法优化

第八部分 日期

只有一道涉及日期的计算。

  • 第19题 数星期日

主要的语法知识点:

  • chrono函数库的使用
  • day()和weekday()的使用
  • 表示时间跨度的time::Duration

第九部分 排列组合

学习全排列的几种生成算法。

  • 第24题 字典序排列
  • 第31题 硬币求和
  • 第41题 全数字的素数
  • 第49题 素数重排
  • 第43题 子串的可整除性

主要的语法和算法:

  • 学写按字典生成全排列的算法
  • 不重新发明轮子,使用别人的库 permutohedron::heap_recursive

第十部分 分数

分数可以表示为无限循环小数,不断试除和取余来找循环节。

  • 第26题 倒数的循环节
  • 第33题 消去数字的分数

主要的语法知识点:

  • Option<T>、Some<T>和None的使用
  • match关键字如何匹配表达式

第十一部分 三角形数

根据一个函数可以生成一系列的整数。

  • 第39题 直角三角形
  • 第42题 编码三角形数
  • 第44题 五边形数
  • 第45题 三角形数、五边形数和六角形数

主要的语法或算法:

  • 字符与ASCII码的转换
  • 一元二次函数的求根公式

第十二部分 密码学

这里有两道初级的黑客问题。

  • 第59题 异或解密
  • 第79题 密码推断

主要的语法知识点:

  • 异或XOR
  • 字符串的split()函数的使用
  • graphviz工具的运用

小结

1、刷题容易上瘾

一开始解题是想快速掌握Rust的语法,前面进展较慢,因为语法不熟,需要边看Rust编程书,边google,边试验才能解决一道题。

在完成了30题左右之后,有点游戏闯关上瘾的感觉,有些题即使5%难度系数,解决起来也并不容易,需要不断找bug或优化算法的性能,当在projecteuler.net上输入答案得到正确反馈的一刻,有一种打怪升级的快感。

然后就想会把前50题,前70题全部攻克!

慢慢地就会忘了学Rust的初心,忘了做欧拉题的初心,我是想学MOVE编程语言,我是想学区块链的智能合约编程技术,所以就放慢了刷题的节奏。

写完这63道题的小结,也是将前面学习Rust的过程进行一次小结。后面可能会更新这本PDF书,也可能不会。

2、数学题并不是全部

欧拉计划以数学题为主,对数学或算法感兴趣的朋友,可以拿它练习,如果你学习JAVA、C#、Python等编程语言,拿它练练手,绝对蛮有用,一定要先自己试着做一下,直接看别人的源码什么也学不到。

但它的局限性也是显然的,实际的软件项目中几乎很难遇到素数判断、质因子、大整数以及全排列生成的这些算法。你更要学习模块的划分、单元测试的编写、程序的调试的基本技巧,字符串操作、数组排序、字典、哈希表的运用可能更加频繁。

3、函数式编程

现代的编程语言都结合了过程式编程和函数式编程的优点,通过这些例子的练习,你既可以掌握通常的过程式算法的写法,也要理解函数式编程的优美和简洁,但在实际项目中又不能为了函数式编程减少几行代码而去刻意地炫技,让程序失去了可维护性。

需要在过程式编程和函数式编程之间达到一种平衡。

4、还得结合其它编程书籍

程序完成了,得到了正确的答案,事情并没有结束,Rust背后的一些原理,仍需要深入地理解,字符串和切片的区别,iter()的背后机制,如何定义宏,所有权的借用关系,这些都还没有真正掌握。


内容太多,我直接把它写成了一本电子书,下载地址:

https://pan.baidu.com/s/1Py8rp4pqAQ5EU7vz6uLYxQ

提取码: 58zw

近期文章:

原文发布于微信公众号 - 可回收BUG(way-of-full-stack)

原文发表时间:2019-10-12

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券