算法在身边——学习算法从妈妈的菜谱开始

2016-07-07作者:[日] 杉浦贤编辑:博文视点

听到“算法(Algorithm)”这个词,大部分人都觉得好像很艰深晦涩。的确,这不是一个常常能听到的词。事实上,在数学、计算机等理工科领域,所谓的算法,指的就是“对特定问题的解决步骤”。而这里说的特定问题,通常有:对信息进行排序、搜索目标信息等不同的问题。 此外,如果说“算法是解决问题的步骤”,那么撇开计算机的数据处理不论,现实生活中也有很多问题的解决方法蕴含了算法的思想。这其中的代表就是菜谱。

我们都知道,记录做出各色各样的菜品所需步骤的东西就是菜谱。例如:鸡肉咖喱、马铃薯炖肉以上两个菜品的菜谱里,会把制作菜品所必需的材料种类、量标记清楚,并且把做菜的过程、每一步需要的时间等正确地记述下来。遵从这样的步骤,无论是谁都可以做出一道不错的鸡肉咖喱或者马铃薯炖肉。像这样对给定问题(做一道鸡肉咖喱等)给出可行解法的菜谱,也就是“解决问题的步骤”,正可以称得上是不错的算法范例。


算法和菜谱



算法是人类智慧的结晶


按照菜谱指定的方法做菜,有时候也不一定能做出好吃的菜。如果分毫不差地遵照一份菜谱,结果做出来的菜并不好吃,那么我们可以说那一份菜谱“不是很好的菜谱”。于是很自然地,那份菜谱也就渐渐地没什么人用了。 而可以做出大家都觉得美味的菜的菜谱,会有越来越多的人重复使用。这样的菜谱也就成了“好的菜谱”。而好的菜谱在越来越多人使用的情况下,会被慢慢地改善,可以指导人做出越来越美味的菜。像这样,好的菜谱上就聚集了为了做出美味的菜而付出的前人的智慧的结晶。在程序中应用的算法也是一样。自计算机面世,在利用计算机解决各种各样的“问题”时,无数解法、步骤被人们提出来。“是不是可以更好地复用”、“是不是可以更高效”、“是不是可以花费更少的空间代价”等,很多研究者会从这些方面对现存的算法进行改善。而历经时间的洗炼,那些优雅的算法正在被应用到各种计算机程序中去。像这样,算法也一样,聚集了为了编写优雅的程序而付出的前人的智慧的结晶。


好的菜谱正是优秀的算法



了解算法对玩游戏有帮助吗


优秀的算法是编写程序的范本,能帮助我们巧妙地解决问题。这和玩游戏时用的攻略异曲同工。在游戏对战的时候,采取更好的战略往往容易获得胜利。曾经有这么一款射击游戏,它的玩法是:“用移动的炮台把从游戏画面上方不断迫近的敌人击落”。在这款游戏的设计中,甚至还有直接写成招式名称的游戏定式,譬如“○○式”、“△△攻击”等。依照定式所指示的步骤来操作,无论谁每次都可以打倒同样的敌人。这种为游戏通关设计的定式,也算是不错的算法。所谓的“定式”,原本是围棋术语,指的是“在某种局面下,最优的固定下法”。在将棋1或者国际象棋中,同等的东西被称为“棋式”,在英文里叫“theory”。在下围棋的时候,在某种局面下只要知道相应的定式,就可以在没有“思考往后几步的下法,在各种下法中找出最好的下法”的情况下,直接下出最好的一步棋。定式中汇集了无数前人的智慧,因此知道的定式越多,下赢不知道定式的对手就越简单。而计算机中的算法也是如此。一个学习过算法的人,即便没有多高的天份,在编写同样功能的程序时,完成度比没有学习过算法的人有明显的优势。


汇集前人智慧的定式也是优秀的算法



算法有两个必要条件


作为“解决问题的处理顺序”的算法,必须要具备下述两个重要的条件。 1.准确性 对相应的问题,算法必须能够得出正确的结果。这正是算法的准确性。所谓算法的准确性,指的是“输入符合指定条件的值,一定要保证能得到正确的输出”。算法准确性的证明事实上并不简单。乍看之下能够得出正确结果的算法,很可能在多了某些特别的边界输入值的情况下就会发生谬误。证明算法准确性的其中一个方法是,“对于算法中的任意一个步骤,输入当前步骤满足条件的值,看看是否能得到当前步骤产生的准确的结果,以此细分并判定。”这种方法叫断言(Assertion)。 2.可停止性 算法必须是最终可停止的。也就是说,一直重复,永远也不能返回结果的操作步骤(也叫死循环)是不能被称作算法的。算法的可停止性也就是“保证无论什么样的输入,也一定可以在有限时间内正确地停止”。


算法的两大支柱



要特别了解的重要算法


编写程序时必要的算法浩如烟海,而其中有些是要特别了解的重要的算法。本书将介绍一些比较有代表性的算法。 1.专用于数论计算的算法:求解最大公约数的辗转相除法、求解联立方程的高斯消元法、求解定积分近似值的梯形公式、计算质数的埃拉托斯特尼筛法 2.对一组乱序的数据进行升序或者降序排序的算法(sort):选择排序、冒泡排序、插入排序、希尔排序、归并排序、快速排序 3.在大量数据中找出目标数据的搜索算法(search):线性搜索(linear search)、二分搜索(binary search) 4.在一个字符串中找到符合特定模式的子串(子字符串)的匹配算法:简单字符串搜索、KMP 算法、BM 算法。


有代表性的算法


内容来源:书问

书名
书籍比价

分享到

扫描二维码 ×

电子纸书

教育 我们身边的故事 中国教育问题访谈

程平源
清华大学出版社[2015] ¥15

幸福的起点——出彩人生从“家”开始

姚鸿昌、郭文玲、武星
清华大学出版社[2014] ¥14

机器学习:从公理到算法

于剑
清华大学出版社[2017] ¥48

装在口袋里的爸爸院 注音版援 机器妈妈

杨鹏著
春风文艺出版社[2012] ¥5

JSP+Servlet+Tomcat应用开发从零开始学(第2版)

林龙 刘华贞
清华大学出版社[2019] ¥47

C语言编程从零开始学(视频教学版)

王英英、李小威
清华大学出版社[2018] ¥77

Excel商务图表从零开始学

王亚飞、孔令春
清华大学出版社[2015] ¥35

JSP+Servlet+Tomcat应用开发从零开始学

林龙
清华大学出版社[2015] ¥41

出版业领先的TMT平台

使用社交账号直接登陆

Copyright © 2019 BookAsk 书问   |   京ICP证160134号


注册书问

一键登录

Copyright © 2019 BookAsk 书问   |   京ICP证160134号