返回 登录
0

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

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

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

算法和菜谱

图片描述

算法是人类智慧的结晶

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

好的菜谱正是优秀的算法

图片描述

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

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

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

图片描述

算法有两个必要条件

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

算法的两大支柱

图片描述

要特别了解的重要算法

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

有代表性的算法

图片描述

相关图书:

图片描述

《写给大家看的算法书》 来自漫画帝国的图解算法书 轻松掌握数据处理关键点 【日】杉浦 贤 著 绝云 译 2016年6月出版 ◎ 从基础开始详尽地讲解算法 ◎ 将复杂的算法知识点与轻松有趣的漫画故事结合 ◎ 采用大量生动的类比,配合简洁易懂的配图,深入浅出地讲解算法

图片描述

评论