不用库函数实现计算一个数的n次方
发布日期:2021-10-02 06:27:36 浏览次数:2 分类:技术文章

本文共 1239 字,大约阅读时间需要 4 分钟。

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

求解思路1

常规解法,需要注意几个点即可:

  • 底数为0,不管多少次方都为0(一般底数不为0
  • 指数为0,结果为1
  • 指数为负数,结果为正数次幂的倒数
class Solution {
public: double Power(double base, int exponent) {
double res=base; if(exponent){
if(exponent>0){
for(int i=1;i
运行时间:2ms占用内存:376k

求解思路2

据说啊,有这么一个公式:

在这里插入图片描述
我们回过头来看看思路1中的解法,如果我们要计算a32次方的话就要计算32

而有了上面的公式,我们要计算a32次方,可以这么算:

先算 a 2 a^2 a2 -> 再算 a 4 = a ( 2 ) × 2 a^4=a^{(2)\times 2} a4=a(2)×2 -> 再算 a 8 = a ( 4 ) × 2 a^8=a^{(4)\times 2} a8=a(4)×2 -> 再算 a 16 = a ( 8 ) × 2 a^{16}=a^{(8)\times 2} a16=a(8)×2,最后算 a 32 = a ( 16 ) × 2 a^{32}=a^{(16)\times 2} a32=a(16)×2

哇,amazing

算一个数的32次方我们只需要计算5次就可以了!!!

由于我们计算的次方比较低,因此可以采用递归的方法来计算,代码如下:

class Solution {
public: double Power(double base, int exponent) {
if(exponent>0) return calculate(base,exponent); else return 1.0/calculate(base,-exponent); } double calculate(double base,int exponent){
if(exponent==0)return 1.0; if(exponent==1)return base; double res=calculate(base,exponent>>1); res*=res; if(exponent&0x1) res*=base; return res; }};
运行时间:3ms占用内存:376k

转载地址:https://blog.csdn.net/Jeaten/article/details/108083581 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:打印从1到最大的n位数 — C++实现
下一篇:求二进制中1的个数的几种解法

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月26日 16时56分40秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章