打字猴:1.7004149e+09
1700414900
1700414901 解决一个问题的算法未尽只有一种。在考量用于解决同一个问题的多种算法的优劣时,可以认为转化为程序后,执行时间较短的算法更为优秀。虽然计算机的处理速度很惊人,但当处理的数据数值巨大或数量繁多时还是要花费大量的时间的。例如,判定91是否是素数的过程一下就有结果了,可是要判定999999937的话,笔者的计算机要花费大约55分钟了
1700414902
1700414903 有时稍微在算法中加入一些技巧,就能大幅度地缩短处理时间。在判定素数上,原先的过程是用待判定的数除以比较它小的所有正整数,只要加入一些技巧,改成用待判定的数除以比较它的1/2小的所有数,处理时间就会缩短。之所以改成这样是因为没有必要去除以比较它的1/2还大的数(要是从2开始依次除下去,只需要从2除到待判定数的平方根就足够了)。通过这点改进,除法运算的处理时间就能够缩短1/2
1700414904
1700414905 在算法技巧中有个著名的技巧叫作“哨兵”,这个技巧多用在线性搜索(从若干个数据中查找目标数据)等算法中。线性搜索的基本过程是将若干个数据从头到尾,依次逐个对比,直到找到目标数据。
1700414906
1700414907 下面还是通过例题来思考吧。假设有100个箱子,里面分别装有一个写有任意数字的纸条,箱子上面标有1-100的序号,现在要从这100 个箱子中找出是否有箱子装有写着要找数字的纸条
1700414908
1700414909 首先看看不使用哨兵的方法。从第一个箱子开始依次检查每个箱子中的纸条。每检查完一个纸条,还要再检查箱子的编号(用变量N表示),并进一步确认编号是否已超过最后一个编号了。这个过程用流程图表示如图5.6所示
1700414910
1700414911 图5.6 未使用哨兵的流程图
1700414912
1700414913
1700414914
1700414915
1700414916 图5.6所示的过程,虽然看起来似乎没有什么问题,但实际上含有不必要的处理–每回都要检查箱子的编号有没有到100
1700414917
1700414918 为了消除这种不必要的处理,于是添加了一个101号箱子,其中预先放入的纸条上琯有正要查找的数字。这种数据称为“哨兵”,通过放入哨兵,就一定能找到要找的数据了。找到要找的数据后,如果该箱子的编号还没有到101就意味着找到了实际的数据;如果该箱子的编号是101,则意味着找到的是哨兵,而没有找到实际的数据。使用了哨兵的流程图如图5.7所示。
1700414919
1700414920 图5.7 使用了哨兵的流程图
1700414921
1700414922
1700414923
1700414924
1700414925 需要反复多次检查的就只剩下“第N个箱子中包含要找的数字吗?”这一点了,程序的执行时间也因此大幅度缩减了
1700414926
1700414927 当笔者第一次得知哨兵的作用时,对其巧妙性感到惊叹,兴奋异常。有些读者会感到“不太明白巧妙在哪里”,那么就讲一个故事来解释哨兵的概念吧。假设某个漆黑的夜晚,在海岸的悬崖边上玩一个游戏,站在距悬崖边缘100米的地方,地上每隔1米放置一个物品,请找出这些物品中有没有苹果。
1700414928
1700414929 每前进1米就要捡起地上的物品,检查是否是苹果,同时还要检查有没有到悬崖边缘(不检查的话有可能掉到海里)。也就是说要对这两种检查反复若干次。
1700414930
1700414931 使用了哨兵后,就要先把起点挪到距离悬崖101米的地方,再在悬崖边缘放置一个苹果(如图5.8所示)
1700414932
1700414933 图5.8 使用了哨兵的游戏
1700414934
1700414935
1700414936
1700414937
1700414938 这个苹果就是哨兵。每前进1米只需检查捡到的物品是不是苹果就可以了。如果捡到了苹果,只需站在原地再检查1米外的情况,如果还没有到悬崖边缘,就意味着找到了真正的苹果。如果捡到的是哨兵,说明已经到悬崖边缘了,而没有找到真正要找的苹果
1700414939
1700414940
1700414941
1700414942
1700414943 计算机是怎样跑起来的 [:1700412664]
1700414944 计算机是怎样跑起来的 5.7 要点6:找出数字间的规律
1700414945
1700414946 所有的信息都可以用数字表示–这是计算机的特性之一。因此,为了构造算法,经常会利用到存在于数字间的规律。例如,请思考一下判定石头剪刀布游戏胜负的算法,如果把石头、剪刀、布分别用数字0,1,2表示,把玩家A做出的手势用变量A表示,玩家B做出的手势用变量B表示,那么变量A和变量B中所存储的值就是这一个数中的某一个。请以此判断玩家A和B的输赢
1700414947
1700414948 如果算法没有使用任何技巧,也许就会通过枚举表5.2所列出的9(3*3)种组合来判定输赢吧。把这个表格转换成程序后就得到了代码清单5.4.可以看出这是一种冗长而双枯燥的判断方法(代码清单5.4和5.5列出的都只是程序的一部分,因此不能直接运行)
1700414949
[ 上一页 ]  [ :1.7004149e+09 ]  [ 下一页 ]