折半试乘查找算法,听此名字,还不如直接试乘呢,直接试乘是没有范围的。此算法先确定一个范围,然后再试乘。并且试乘的积并不是原来的数。
正常的开方,我们是用以下公式:(a+b)^2=a^2+2ab+b^2。这相当易于手算。但不利于写程序代码。
对于超大整数开方,利用上述公式,代码是较为烦琐的。所以,这里介绍一个试乘折半查找算法。
数学根据如下:
我们有:
对于奇数,[(n+1)/2]^2-[(n-1)/2]^2=n
我们令:a+b=(n+1)/2 c+d=(n-1)/2
则:(a+b)^2-(c+d)^2=n
当ab=cd时,我们有:(a-b)^2-(c-d)^2=n
所以,如果n为完全平方,则有:c=d,所以,我们只要求出
a+b=(n+1)/2,c=d时,ab=c^2,或ab=d^2即可得到平方根。
举例说明如下:
对于:9
c+d=4,c=d=2, cd=4
a+b=5, 所以,ab=4时: a=4, b=1 a-b=3 即是平方根。
对于25:
c+d=12,c=d=6, cd=36
a+b=13, 所以,ab=36时: a=9, b=4 a-b=5 即是平方根。
对于偶数,[(n+2)/2]^2-[(n-2)/2]^2=4n
我们令:a+b=(n+2)/2 c+d=(n-2)/2
则:(a+b)^2-(c+d)^2=4n
同理我们也有(a-b)^2-(c-d)^2=4n
所以一样也有,如果n这完全平方,则有:c=d,所以,我们只要求出
a+b=(n+2)/2,c=d时,ab=c^2,或ab=d^2即可得到平方根。
举例说明如下:
对于:16
c+d=6,c=d=3, cd=9
a+b=10, 所以,ab=9时: a=9, b=1 (a-b)/2=8/2=4 即是平方根。
对于36:
c+d=16,c=d=8, cd=64
a+b=20, 所以,ab=64时: a=16, b=4 (a-b)/=12/2=6 即是平方根。
由此可见,算法就是简单地让 c=d, 并求出 ab=c^2,
其中, a+b=(n+1)/2 c+d=(n-1)/2(奇数)
a+b=(n+2)/2 c+d=(n-2)/2(偶数)
理论上来讲,如果是用10进制,40位的数字,如果用(a+b)^2=a^2+2ab+b^2公式法,要算40次。
但折半试乘查找算法却要试乘126次左右。
表面上看,可能前者快,但对于每一个10进制的位实际都要试根。要试出合适的2ab+b^2。也就多许多次加法和许多次减法。
但折半试乘查找算法只是将乘出的结果直接与目标数比大小。
所以,此算法的效率,必须经过测试才能证明。
另一方面,此算法的算法复杂度则远远小于平方和法的复杂度。
如果此算法效率高,则我们可以有这样的结论,并非算法复杂度高的算法效率一定高。
分享到:
相关推荐
静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法静态查找表。实现有序表的折半查找算法
折半查找的递归算法,非常实用,可以实现的C语言程序
折半查找算法,折半查找算法,折半查找算法
该算法是在折半算法的基础上,推广折段的段数,通过简单的数学模型证明了最优的分段数为3,而不是2(即折半)。在文章的最后给出了算法的C程序代码。如果有应用到实际中,算法还可以进一步精简。
由N个有序整数组成的数列已放在一维数组中,给定程序MODI1.C中函数fun的功能是:利用折半查找整数m在数组中的位置。若找到,返回其下标值;反之,返回-1。 折半查找的基本算法是:每次查找前先确定数组中待查的范围...
折半查找算法在顺序表中插入一个元素讲解.pdf
折半查找算法 顺序表 折半查找算法C语言版
折半查找算法,c、c++,数据结构课本中讲解的算法实现。
用C语言实现折半查找,折半查找算法较简单
使用折半查找,输入一个整数,查找是否在数组中,如在给出下标,否则-1
c语言 折半 查找 算法 数据结构 绝对可用 欢迎下载 绝对可用 欢迎下载
数据结构中实现哈希查找、顺序查找和折半查找的代码
本书是折半查找算法的标准教材,目的是让大家知道好的程序设计和算法分析技巧,难得一见的好书!
递归调用的折半查找java代码,算法分析与设计实验报告。
数据结构课程设计-综合查找算法(顺序查找、折半查找、二叉排序树、哈希表) 可以在Microsoft Visual C++ 上运行没有错误 包括论文word文档,答辩的ppt等
折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)
本资源为算法课程实验,用C++实现了折半查找,能帮助同学完成课程实验
所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找