算法学习

前言:

Any fool can write code that a computer can understand. 

Good programmers write code that humans can understand.

普通人能写出电脑能够理解的代码,而优秀的程序员却能写出人能够理解的代码。

                                 — Martin  Fowler

期末考试的成绩公布了,心急如焚的你想要知道你在班中的排名。经过一番努力,你收集了班里所有人的成绩。 

但是面对庞大的数据量,你不知所措,不知道应该从哪里下手, 这时你想到可以用计算能力强大的电脑来解决你的问题。 

可是要怎么让电脑帮你解决这个问题呢?你将成绩单拍在了电脑面前,说:“帮我算出我在班上的排名”,问题就解决了…

等等,似乎有什么不对。计算机并不能理解什么是“班上的排名”,也不明白成绩单是什么,所以选择忽视了你的问题。

你一拍脑袋,想起计算机似乎只能够理解它自身的语言。如果要让它帮助你解决这个问题,就要将问题翻译成对应的程序…

想到这里时,你已经在以模拟的形式思考问题了。而今天,我们将一同了解最基础的模拟算法,并通过一道题目来加深你的印象。

1. 什么是模拟?

将生活中的实际问题,通过一系列“抽象”与数学建模,“翻译”成计算机能够理解的问题。

这个过程就是模拟了。

举个例子

以上文提到的问题为例,你需要得到你的成绩在班上的排名。具体落实到计算机上,就是已知正序数组 score[],求x在其中的位置。其中 score数组 存储所有成绩,x变量 存储你的成绩。

2. 为什么要写模拟?

计算机无法理解人类眼中的世界与事件。而要让计算机帮我们解决具体的问题,就需要将我们的问题,用计算机语言翻译成一个程序,这样计算机就能够理解这个程序并求出我们想要的答案。

3. 为什么要学习基本模拟?

虽然简单,基本模拟却是你的算法生涯中必不可少的一课。

这是因为人类发明计算机的目的就是为了解决生活中的问题,为了解决和模拟更加复杂的实际问题,自然要首先掌握对简单事物的基础模拟。就像1+1=2 在数学中的地位一样,基本模拟将为你接下来的 算法学习 铺下第一块基石。

当然,模拟的关键点在于如何抽象与建模。在此我们不讨论涉及更高级算法的模拟,只涉及一些简单的问题转换。

那么下面就让我们来一起解决一道简单的模拟题吧。

例三 洛谷P1205 [USACO1.2] 方块转换 Transformations:

已知有一个由 ’@’ 和 ’-’ 组成的 n*n 的正方形,现在要求从一下几种方法中选出一种,通过一次操作将原正方形变换成新的图案。

  1. 旋转90°:图案按顺时针转 90°90°
  2. 旋转180°:图案按顺时针转 180°180°。
  3. 旋转270°:图案按顺时针转 270°270°。
  4. 反射:图案在水平方向翻转(以中央铅垂线为中心形成原图案的镜像)。
  5. 组合:图案在水平方向翻转,然后再按照 1∼31∼3 之间的一种再次转换。
  6. 不改变:原图案不改变。
  7. 无效转换:无法用以上方法得到新图案。

旧图案和新图案为已知条件,求所使用的变换方法的编号。

相信这时候聪明的你已经有了初步解题思路。

解:

典型的模拟题。我们依照顺序依次模拟7种转换方法,答案就出来了。

首先我们用二维数组去存储图形。二维数组就是能够存储方阵的一种数组。

设变换前数组为 origin[][],变换后数组为 transformed[][]

1. 顺时针旋转 90 度:我们列出 3*3 的正方形来探究原图形与变换后图形之间的关系。

设原图形为:

11 12 13

21 22 23

31 32 33

那么变换后图形为:

31 21 11

32 22 21

33 23 13

结合 n=3,稍微推敲一下,就可以发现规律:

transformed[j][n-i+1] = origin[i][j]

由此我们就解决了第一种变换的模拟。

2. 顺时针旋转 180 度:看到这里,你一定想到我们可以依照第一种方法去推敲规律吧。

可以是可以,但是不觉得再推敲一遍很费脑力吗。我们可不可以利用已经得到的结论来解决这个问题呢?

聪明的你一定想到了。我们将经过变换1的数组transformed,再旋转 90 度,不就能得到 180 度了吗?

这里建议落实到具体代码上面时,将“旋转 90 度”的变换写成一个具体函数 rotate(),用三次循环就能够分别解决 90 度,180 度与 270 度的变换了。

3. 顺时针旋转 270 度:  使用 rotate() 函数去旋转经过 变换2 的图形,得到 变换3的图形。 

变换1-3 代码表示:

4. 以铅垂线为对称轴翻转图形:这个就比较简单了。我们很容易就能发现翻转时,字符所处的行数不变,而列数则变为n-j+1。因此可得旋转变换:

transformed[i][n-j+1] = origin[i][j]

变换4 模拟完成。

变换4 代码表示:

5. 经过变换4后,再依次旋转90度,180度,270度:参照前三个模拟的思路,我们将 变换4 写成函数 reflect(),再依次用 rotate() 模拟三种旋转情况。

变换5 代码表示:

6. 不需要变换:这个就不用说了吧。

7. 无法通过上述变换得到要求的图形:如果上述变换全部都不能得到要求的图形,那么就输出 ‘7’,表示无解咯。

变换6-7 代码表示:

总结:模拟题型是最适合新手的题型,它不会用到任何优化和复杂难懂的算法,主要考验的是代码熟练度。模拟题型操作难度低,新手稍加练习就可以快速掌握。在看完这道题后,你是否对模拟有了新的理解?

题解提供者:深国交 G1 Joshua Fu

其实我们让计算机所做的一切,计算天气也罢,运行游戏也罢,全部都可以归类于模拟算法,即计算机对于实际问题的抽象模拟与计算。

而通过这篇文章你已经掌握了最基础的模拟,从此你迈出了使用算法解决生活中的问题的第一步。

此后你也将遇到各种各样,或复杂或晦涩的实际问题与情况,仅凭基本的模拟算法无法解决它们。不过不用担心,因为我们,深国交ADO算法社,将始终陪伴在你的身旁,为你推送干货满满通俗易懂的算法知识,助你在学习与运用算法的道路上砥砺前行。

Resources:

[0] https://www.goodreads.com/quotes/tag/programming

[1]  https://www.luogu.com.cn/problem/P1205

以上便是我们对基础模拟的理解,

希望对您有帮助。

如果您有补充或更正的地方欢迎在评论区讨论

感谢您的阅读与支持。

END

本文经授权转载自ADOSCIE

USACO官网:http://www.usaco.org/

往期推荐:http://www.biggerlab.com/uncategorized/2020%e5%b9%b4ap%e8%80%83%e8%af%95%e5%8f%af%e8%83%bd%e5%bb%b6%e6%9c%9f/


0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

error: Content is protected !!