基本数字运算

103 阅读2分钟

导语

计算机软件技术与数学是不可切割的有机整体,很多企业在招聘求职者的时候,往往非常在意求职者的属性能力。所以,面试官在考察求职者时,也会比较喜欢出这类题目,例如: 怎么判断一个数是不是质数等等。在此我选择了一些个人感觉还可以的题目,总结了一下

如何计算一个数的 n 次方 ?

给定一个数 d 和 n , 如何计算 d 的 n 次方? 例如: d = 2 , n = 3 , d 的 n 次方为 8
看到这题,我不忍的翻了一下眼 , 这不就叫我们实现一下 Math.pow() 这个函数吗?
结果 res =Math.pow(d , n) 。这时候我想很久很久以前, 当时计算机才刚刚被发明的时候 ,那些大佬们倒是是如何实现这个 一个数的 n 次方 这个功能的呢?
额 , 扯多了, 不好意思啊
思路1:其实,这问题想一想就看的出
2 ** 3 == 1* 2 * 2 * 2
2 ** -3 == 1 / 2 / 2 / 2
遍历一遍是完事了

def power (d , n):
if n == 0: return 1
if n == 1: return d
res = 1
if n > 0:
    i = 1
    while (i <= n):
        res *= d
        i+=1
    return res
else:
    i = 1
    while i <= abs(n):
        res = res / d
        i+=1
    return res

算法分析: 时间复杂度 O(n) , 需要注意的是 , 当 n 非常大的时候 , 这种方法的效率是非常低下的,有没有办法更快一点呢?

思路2: 我们假设我们要求的为
2 ** 4 = 2 * 2 * 2 * 2 , 当我们循环到 2 * 2 的时候 , 其实就没有必要循环了 , 为什么呢 ?
递归

def power(d,n):
if n == 0 : return 1
if n == 1 : return d
tmp = power(d , abs(n)/2) + 0.0
# print tmp
if n > 0:
    if n % 2 == 1: # n 为 奇数
        return tmp*tmp*d
    else: # n 为偶数
        return tmp * tmp
else:
    if n % 2 ==1:
        print (1 /(tmp*tmp*d))
        return (1 /(tmp*tmp*d))
    else:
        return (1/(tmp*tmp))

算法分析: 时间复杂度 O(log n)