莆田网站开发公司,wordpress怎么清缓存,烟台百度网站建设推广,如何在腾讯云上建设网站“令人生畏且难以掌握”“和自己无缘”#xff0c;诸位是不是会对算法留下这样的印象呢#xff1f;诚然#xff0c;有那种无法轻松理解、难以掌握的算法#xff0c;但是并不是说只有把那种” “由智慧超群的学者才能想出的算法全部牢记心中才能编写程序#xff0c;简单的算… “令人生畏且难以掌握”“和自己无缘”诸位是不是会对算法留下这样的印象呢诚然有那种无法轻松理解、难以掌握的算法但是并不是说只有把那种” “由智慧超群的学者才能想出的算法全部牢记心中才能编写程序简单的算法也是有的。而且诸位自己也不妨去思考一些原创的算法。只要理清在现实世界解决问题的步骤再结合计算机的特性就一定能想出算法。思考算法也可以是一件非常有趣的事。下面笔者将介绍思考算法时的要点。请诸位务必以此为契机和算法成为朋友体味思考算法所带来的乐趣。”
要点1算法中解决问题的步骤是明确且有限的 思考求解两个整数的最大公约数 解法1直觉法 解法2辗转相除法 哪种才真正算的上算法呢 要点 2计算机不靠直觉而是机械地解决问题
“计算机不能自发地思考。因此计算机所执行的由程序表示的算法必须是由机械的步骤所构成。所谓“机械的步骤”就是不用动任何脑筋只要按照这个步骤做就一定能完成的意思。众多的学者和前辈程序员们已经发明创造出了很多机械地解决问题的步骤这些步骤并不依赖人类的直觉。由此所构成的算法被称为“典型算法”。” “请诸位注意以下三点1. 步骤是明确的、完全不依赖直觉的2. 步骤是机械的、不需要动脑筋就能完成的3. 使步骤终止的原因是明确的。” 要点 3了解并应用典型算法 “这次请思考一下解决“求解 12 和 42 的最小公倍数”这个问题的算法。所谓最小公倍数就是指两个整数的公共倍数是一个数几倍的数中最小的那个数。最小公倍数的求解方法诸位在中学的数学课上也应该学过了但是很可惜求解步骤是依赖人类的直觉的。请再思考一个适用于计算机的机械的算法。诸位说不定会想“反正会有典型算法的吧比如‘某某氏的某某法’”然后就纠结于是否还要自己思考。 但是即使查了算法辞典之类的书也还是找不到求解最小公倍数的算法。为什么呢因为我们可以通过以下方法求解最小公倍数——用两个整数的乘积除以这两个整数的最大公约数。因此 12 和 42 的最小公倍数就是 12×42÷6 84 了。如此简单的算法不能算作典型算法。这个例子说明先自己思考[…]”
要点 4利用计算机的处理速度 “这次再请诸位思考求解“判定 91 是否是素数”这一问题的算法。在用于判定素数的典型算法中有一个被称为“埃拉托斯特尼筛法”的算法。在学习这个算法之前先请诸位思考如果是在数学考试中碰到了这道题要如何解答呢” 也许有人会这样想用 91 分别除以比它小的所有正整数如果没有找到能够整除的数那么 91 就是素数。但是如此繁琐的步骤可行吗实际上这就是正确答案。埃拉托斯特尼筛法是一种用于把某个范围内的所有素数都筛选出来的算法比如筛选 100 以内的所有素数其基本思路就是用待判定的数除以比它小的所有正整数。例如要判定 91 是否是素数只要分别除以 290 之间的每个数就可以了因为 1 肯定能够整除任何数所以从 2 开始检测。
无论是多么冗长繁琐的步骤只要明确并且机械就能构成优秀的算法。诸位把算法用程序表示出来让计算机去执行而计算机会用令人吃惊的速度为我们执行。为了判定 91 是否是素数用 91 除以 290 这 89 个数的操作一瞬间就可以完成。在思考算法时不防时刻记着解决问题时是可以利用计算机的处理速度的。 作为利用计算机的处理速度解决问题的另一个例子请试着求解以下联立方程组。题目是鸡兔同笼问题鸡和兔子共计 10 只把它们的脚加起来共计 32 只问鸡和兔子分别有多少只设有 x 只鸡y 只兔子那么就可以列出如下的联立方程组。 因为鸡和兔子的只数应该都在 010 这个范围内所以就试着把 010 中的每个数依次代入 x 和 y只要能够找到使这两个方程同时成立的数值也就求出了答案。利用计算机的处理速度答案一瞬间就出来了
要点 5使用编程技巧提升程序执行速度
解决一个问题的算法未必只有一种。在考量用于解决同一个问题的多种算法的优劣时可以认为转化为程序后执行时间较短的算法更为优秀。虽然计算机的处理速度快得惊人但是当处理的数据数值巨大或是数量繁多时还是要花费大量的时间。例如判定 91 是否是素数的过程一下子就有结果了可是要去判定 999999937 的话笔者的电脑就要花费大约 55 分钟之久言外之意 999999937 是素数。 有时稍微往算法中加入一些技巧就能大幅度地缩短处理时间。在判定素数上原先的过程是用待判定的数除以比它小的所有正整数只要在此之上加入一些技巧改成用待判定的数除以比它的 1/2 小的所有数处理时间就会缩短。之所以改成这样是因为没有必要去除以比它的 1/2 还大的数。 在算法技巧中有个著名的技巧叫作“哨兵”。这个技巧多用在线性搜索从若干个数据中查找目标数据等算法中。线性搜索的基本过程是将若干个数据从头到尾依次逐个比对直到找到目标数据。 下面还是通过例题来思考吧。假设有 100 个箱子里面分别装有一个写有任意数字的纸条箱子上面标有 1100 的序号。现在要从这 100 个箱子当中查找是否有箱子装有写着要查找数字的纸条。
首先看看不使用哨兵的方法。从第一个箱子开始依次检查每个箱子中的纸条。每检查完一个纸条还要再检查箱子的编号用变量 N 表示并进一步确认编号是否已超过最后一个编号了。 “所示的过程虽然看起来似乎没什么问题但是实际上含有不必要的处理——每回都要检查箱子的编号有没有到 100。” 为了消除这种不必要的处理于是添加了一个 101 号箱子其中预先放入的纸条上写有正要查找的数字。这种数据就被称为“哨兵”。通过放入哨兵就一定能找到要找的数据了。找到要找的数据后如果该箱子的编号还没有到 101 就意味着找到了实际的数据如果该箱子的编号是 101则意味着找到的是哨兵“而没有找到实际的数据。使用了哨兵的流程图如图 5.7 所示。需要多次反复检查的就只剩下“第 N 个箱子中包含要找的数字吗”这一点了程序的执行时间也因此大幅度地缩减了。 讲一个故事来解释哨兵的概念吧。假设某个漆黑的夜晚诸位在海岸的悬崖边上玩一个游戏请勿亲身尝试。诸位“站在距悬崖边缘 100 米的地方地上每隔 1 米就任意放 1 件物品。请找出这些物品中有没有苹果。 诸位每前进 1 米就要捡起地上的物品检查是否拿到了苹果同时还要检查有没有到达悬崖的边缘不检查的话就有可能掉到海里。也就是说要对这两种检查反复若干次。 使用了哨兵以后就要先把起点挪到距悬崖边缘 101 米的地方再在悬崖的边缘放置一个苹果如图所示。这个苹果就是哨兵。通过放置哨兵诸位就一定能找到苹果了。每前进 1 米时只需检查捡到的物品是不是苹果就可以了。发现是苹果以后只需站在原地再检查一步开外的情况。如果还没有到达悬崖边缘就意味着找到了真正要找的苹果。已经达到了悬崖边缘则说明现在手中的[…]
要点 6找出数字间的规律
“所有的信息都可以用数字表示——这是计算机的特性之一。因此为了构造算法经常会利用到存在于数字间的规律。例如请思考一下判定石头剪刀布游戏胜负的算法。如果把石头、剪刀、布分别用数字 0、1、2 表示把玩家 A 做出的手势用变量 A 表示玩家 B 做出的手势用变量 B 表示那么变量 A 和 B 中所存储的值就是这三个数中的某一个。请以此判断玩家 A 和 B 的输赢。” “如果能够发现“工资 底薪加班补贴交通补贴预扣税款”这样的规律那么解决问题的步骤就是明确的步骤数也是有限的因此构造出的算法也就是优秀的了。” 要点 7先在纸上考虑算法
“最后介绍最为重要的一点那就是思考算法的时候要先在纸上用文字或图表描述出解决问题的步骤而不要立刻开始编写代码。 画流程图就可以方便地把算法用图表示出来因此请诸位大量地、灵活地运用它。如果不想画流程图也可以用语言把算法描述出来写成文书。总之先写到纸上这一点很重要。”
