算法合集之《浅谈类比思想》_免费下载

《算法合集之《浅谈类比思想》_免费下载》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈类比思想长沙市长郡中学周戈林【目录】摘要2关键字2止文2引言2常见的类比模式3具休事物类比抽象模型3相似算法之间的类比6图形类比数式8总结10感谢10参考文献10附录11【摘要】信息学是一门变幻莫测的艺术，它包含着海量的知识点。我们不能奢求掌握所有的知识，只能在已有知识的基础上，尽可能的把不熟悉的问题转化为熟悉的问题。类比思想，就是一种非常优秀的转化方法。本文尝试诠释一些常用的类比模式。【关键字】类比思想模型算法理性认识【正文】一、引言：类比是最有创造力的一种思维方法。它关注两个对彖在某些方面的相同或相似

2、，从而推测它们在其它方而也可能存在相同或相似Z处。举例来说，我们在小学一年级学到止确的握铅笔方法是“笔杆放在拇指、食指和中指的三个指梢z间。食指在前，拇指在左后，中指在右下，食指应较拇指低些，手指尖应距笔尖约3厘米。笔杆与作业木保持六十度的倾斜，掌心虚圆，指关节略弯曲”。学会了握铅笔，那么在三年级也可以用类似的方法使用钢笔书写。概括一下，这次握笔类比的形式为：对象A具有性质P、Q；对象A，具冇性质卩（P与P类似）；对象A，可能具有性质Q（Q与Q类似）。拿握笔来说，铅笔（对象A）笔杆比较细（性质P）,所以我们采

3、用上述“笔杆放在三个指梢Z间”的方法握笔（性质Q）；I佃钢笔（对彖A，）笔杆也比较细（性质P'）,所以我们采用同样的方法握笔（性质Q'）。很幸运，这次类比是正确的，我们成功地学会了写字。但有些吋候就没那么幸运了，譬如说，当面对一支毛笔时，以上的握笔方法写出的字就会产生相当的幽默效果。为什么我们的握笔方法面对毛笔失败了呢？这是因为毛笔是软笔，并且笔杆粗细不同，因此类比失败了。正确的握毛笔方法是用拇指和食指捏住笔的上端，用中指和无名指活动笔的卜•端，小指随无名指口然活动。概括这次握笔方法的转换，就是：对象A具有性

4、质P、Q和关系R；对象A，具有性质对彖A，具有性质Q，和关系R具体到握毛笔这个例子，铅笔（对象A）是笔（性质P）,并月.是硬笔（关系R）,需耍用三根手指托笔（性质Q）。而毛笔同样是笔（性质P'）,但却是软笔（关系R）,只需要两根手指夹笔（性质Q9）o这种类比形式考虑到了性质之间的关系，因此准确性提高了。总结一下对握笔的研究：第一次握笔类比关键在于铅笔和钢笔恰好都是硕笔，因此其成功具冇偶然性，它是基丁直观上的感性认识，称Z为简单类比；第二次握笔类比注意到铅笔与毛笔的不同点，其成功带有某种必然性，它是基于逻辑上

5、的理性认识，称之为科学类比。在信息学竞赛中需要的类比，往往是科学类比。下文将试图论述一些常见的类比模式：具休事物类比抽象模型；相似算法之间的类比；图形类比数式。二.常见的类比模式：2.1具体事物类比抽象模型：这是一种最常见的类比。现实事物不是严格的数学模型，在研究它们的过程屮必须根据需要捉炼相应的数学模型，否则便失去了建模的意义。在建模屮要联想具体事物的固有屈性和抽象模型的独有特点，才能恰如其分地建立模型和解决问题。举例来说：研究地球的公转可以把地球看成质点，这是因为相对于公转半径来说地球半径极其微小，可以忽

6、略。但是研究地球的自转时乂不能忽略地球半径,这是因为地球半径比起质点来又远远大得多了。从卜•面这个例了也可以看到，建模的角度不同，效果便截然不同。例一：山顶问题◊题口描述奶牛成群、土地众多的FJ有一个地形狭长的农场，农场被分成了"块土地,拜不超过1000。这些土地位于一条直线上，并从左到右编号为1至m每块土地的面积都相同，但是高度不一-定相同。每块土地都拥冇一个海拔高度值，这个值不超过1000000o如果一段相同高度土地的两边都比它低或者是农场的边界，那么这段土地将被称之为“山顶”。FJ希望通过搬走泥土来降低

7、某些土地的海拔高度，使“山顶”的数目不超过匕其中12W25。在这一前捉下，FJ希望搬运的泥土体积最小，也就是所有的土地减少的高度和最小。◊解法分析题口屮要求了一个很奇怪的“削平山顶”的任务。一个或几个“山顶”往往由一个“山脊”支撑。值得注意的是，“山顶”被削平后有可能会使“山脊”变成“山顶”。从解题的一般感觉上看，这似乎是一道动态规划的题目，尝试着用动态规划來解这道题目。根据一般的状态设计方法，我们用彳力丿表示前i块土地留丿个“山顶”的需要搬走泥土的最小体积。但是光用这两个值无法完全描述出当前土地的高度，因此

8、也无法得知它们对以后状态的影响。为了能准确表述土地的高度，我们需耍记录一个描述高度的序列集合，但存储这个集合的费用是让人无法忍受的。换一种思维看问题，不妨把整个农场180度翻转，使“山顶”朝下。以下是翻转样例得到的图形：―块十•地按照高度被剖分成了最多n个层面，每个层面按照高度被染成了不同的颜色。当然，较高的层面需要较低的层面支撑。而如果一个层面两边的层面都比它低，那么就是“山顶”。把层面看作结点，