对数函数及其应用 对数函数 应用

对数是数学史上一个重要的发明,有着划时代的意义,对数函数在信息学竞赛中也同样有着非常重要的应用,很多时候,合理使用对数函数会简化我们的程序,降低时间复杂度和编程复杂度。

注:为了使描述方便,以下均用log(a)N的形式表示一个普通对数(非常用对数和自然对数),其中a为底数,N为真数;用logn表示log(2)n。

例1:求一个十进制数的位数。

解析:我们以这道很简单的题目作为一个小小的引子。这一题当然有很朴素的O(lgn)的算法,应当说这已经很好了,但是我们应该考虑一下,是否有更简单的方法。注意看朴素算法的时间复杂度,lgn,我们知道朴素算法的实现是不停的div10,分离出它的每一位,所以我们是否可以猜想n的位数是lgn。结论是显然的,所以这一题的答案就是Trunc(lgn+1),因为pascal中没有常用对数,只有自然对数,利用换底公式我们得到Trunc(ln(n)/ln(10))+1。

对数的应用远远不止于此,利用对数,我们可以将乘除运算化为加减运算,将幂运算化为乘除运算,从而提高我们程序的效率。下面我们再看一个例子。

例2:求a^b。

解析:这样的题目我们有O(n)的朴素算法,也有O(logn)的快速幂算法,但是由上一题的启示我们是否可以利用对数在O(1)的时间内算出a^b。2^k显然是可以的,因为有shl和shr的位运算(2^k=shl(1,k))。那么一般的呢?答案是仍然可以在O(1)的时间内算出。我们知道a^(log(a)N)=N,所以a^(log(a)(N^M))=N^M,由对数的性质我们可以知道a^(M*log(a)N)=a^(log(a)(N^M))=N^M(注意,幂运算已经化为乘法运算了),换句话说,e^(b*ln(a))=a^b,而pascal中是提供e的指数函数(exp)和对数函数(ln)的,于是我们得到:

a^b=Trunc(exp(ln(a)*b))

需要注意的事,由对数定义可知,这里a不能为0。

应用:麦森数(Noip2003普及组复赛第4题)

【问题描述】形如2P-1的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,2P-1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。

任务:从文件中输入P(1000<P<3100000),计算2P-1的位数和最后500位数字(用十进制高精度数表示)

【输入格式】

文件中只包含一个整数P(1000<P<3100000)

【输出格式】

第一行:十进制高精度数2P-1的位数。

第2-11行:十进制高精度数2P-1的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)

不必验证2P-1与P是否为素数。

【输入样例】

1279

【输出样例】

386

00000000000000000000000000000000000000000000000000

对数函数及其应用 对数函数 应用

00000000000000000000000000000000000000000000000000

00000000000000104079321946643990819252403273640855

38615262247266704805319112350403608059673360298012

23944173232418484242161395428100779138356624832346

49081399066056773207629241295093892203457731833496

61583550472959420547689811211693677147548478866962

50138443826029173234888531116082853841658502825560

46662248318909188018470682222031405210266984354887

32958028878050869736186900714720710555703168729087

解析:

我们撇开高精度运算,这不是本文的重点,在这里,我们关注的是第一问,也就是十进制高精度数2P-1的位数,这一问是可以在高精度运算结束后统计出的,但是例1与例2可以帮助我们在做高精度之前算出这个值的。

首先我们要明确一点,不可能先算出2P-1,再求它的位数,所以需要对例1例2的公式加以组合变形。又因为2P不可能为10的整数次幂,也就是说2P-1和2P位数必然相等,于是问题转化为求2P的位数。

将2和p代入例2的公式则有2P=trunc(exp(ln(2)*p)),将右边整体代入到例1的公式中,则有2P的位数=

Trunc(ln(2)*p/ln(10))+1

至此问题圆满解决。

笔者以上列出的只是对数函数在信息学竞赛中几点小小的应用,但是我们可以由此看到,合理使用对数函数对我们的程序是有很大帮助的,随着我们不断探索,对数函数的应用也会越来越广泛。

  

爱华网本文地址 » http://www.413yy.cn/a/25101014/226266.html

更多阅读

Excel中指数、对数函数及其应用 指数函数对数函数图像

正如有了计算器就没人用算盘,如今都配了电脑,几乎很少有人再用计算器了。但最近也遇到一个问题:编制“十二五”规划时,要计算出“十一五”期间的年均增长速度,涉及到数学中的开5次方,而电脑中自带的计算器只能开平方。怎么办?利用数学知识

对数函数及其应用 对数函数 应用

对数是数学史上一个重要的发明,有着划时代的意义,对数函数在信息学竞赛中也同样有着非常重要的应用,很多时候,合理使用对数函数会简化我们的程序,降低时间复杂度和编程复杂度。注:为了使描述方便,以下均用log(a)N的形式表示一个普通对数(

物理练习二滑轮及其应用

物理练习二滑轮及其应用一、填空题1.如图所示,物体重G=500N,滑轮重10N,当物体G匀速上升时,则挂钩B承受拉力为__________N,挂钩A承受_______N的拉力,拉力F为_________N,若绳子自由端向上拉动0.5m,则物体向上移动________m。甲乙

声明:《对数函数及其应用 对数函数 应用》为网友中国好男人分享!如侵犯到您的合法权益请联系我们删除