首页 > 其他 > 详细

面试题16:数值的整数次方

时间:2018-08-08 22:23:28      阅读:274      评论:0      收藏:0      [点我收藏+]
// 面试题16:数值的整数次方
// 题目:实现函数double Power(double base, int exponent),求base的exponent
// 次方。不得使用库函数,同时不需要考虑大数问题。

解题思路:

解题并不难,重要的是要考虑到输入的各种情况,并且有相应的处理。

double和int都是可以取负数和0的,如果base取0,exponent<0,结果显然是不存在的。

base取0,exponent取非负,直接返回1就可以了。

其他情况,正常运算就好,要注意如果exponent<0,应该取绝对值,完成幂次方之后再取倒数。

如果想提高代码运行效率的话,可以使用递归或者循环来把a^n分解

a^n=a^(n/2)*a^(n/2),n为偶数

  a^((n-1)/2)*a^((n-1)/2)*a,n为奇数

还有一点需要注意的就是,float、double类型的变量不能用==来比较,应该另外写个函数。

c/c++:

bool g_InvalidInput = false;
bool equal(double num1, double num2);
double PowerWithUnsignedExponent(double base, unsigned int absExp);

double Power(double base, int exponent) {
	//参数校验
	if (equal(base, 0.0) && exponent < 0) {
		g_InvalidInput = true;
		return 0.0;
	}

	//对指数exponent取绝对值
	unsigned int absExp = (unsigned int)(exponent);
	if (exponent<0)
		absExp = (unsigned int)(-exponent);

	//计算pow(base,absExp)
	double result = PowerWithUnsignedExponent(base, absExp);
	//若exponent<0,取倒数
	if (exponent<0)
		result = 1.0 / result;

	return result;
}

double PowerWithUnsignedExponent(double base, unsigned int absExp) {
	//递归中止的边界值
	if (absExp == 0)
		return 1;
	if (absExp == 1)
		return base;

	//简化计算量
	double result = 0;
	result = PowerWithUnsignedExponent(base, absExp >> 1);
	result *= result;
	if (absExp & 0x1 == 1)
		result *= base;

	return result;
}

bool equal(double num1, double num2){
	//double不能直接用==比较
	if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
		return true;
	else
		return false;
}

 

参考资料:

剑指offer第二版面试题16

面试题16:数值的整数次方

原文:https://www.cnblogs.com/BoqianLiu/p/9445996.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!