[C语言]Pow函数的实现

简介: [C语言]Pow函数的实现

力扣题目:

1.函数参数及返回值:

double pow (double x, double n);

返回值就是x的n次方的值;

2.函数的实现

2.1暴力

2.1.1算法思路

时间复杂度O(N); 空间复杂度O( 1 );

最朴素的方法一个一个计算,比如计算x^4,就先计算x^2,然后x^3直到x^4然后返回结果;

2.1.2代码展示

double myPow(double n, double k)
{
    double temp = n;
    if (k == 0)
    {
        return 1;
    }
    else if (k > 0)
    {
        //return n * myPow(n, k - 1);
        k--;
        while (k > 0)
        {
            n *= temp;
            k--;
        }
        return n;
    }
    else if (k < 0)
    {
        //return (1.0 / n) * myPow(n, k + 1);
        k--;
        n = 1.0 * n;
        while (k < 0)
        {
            n /= temp;
            k++;
        }
        return n;
    }
    return -1;
}

2.2分治的思想「快速幂算法 + 递归」

2.2.1算法思路

时间复杂度O(logN); 空间复杂度O(logN);

算法的思路就是假设要计算2^64 那么就先计算2 ^ 32 然后将两个2 ^ 32相乘 以此类推:可以指数级减少运算次数;

分类讨论当n为奇数和偶数的情况:

当我们要计算x ^ n 时 可以先计算y = x ^ (n / 2), x ^ n = y ^ 2;(n 为偶数) x ^ n = y ^ 2 * x;(n 为奇数) 递归的结果为n == 0 return 1;

2.2.2代码展示

double myPowBranch(double n, long long k)
{
    if(k == 0)
    {
        return 1;
    }
    else if(k % 2 != 0)
    {
        double temp = myPowBranch(n, k / 2);
        return temp * temp * n;
    }
    else
    {
        double temp = myPowBranch(n, k / 2);
        return temp * temp;
    }
}
double myPow(double n, double k)
{
    if(n == 1 || k == 0)
    {
        return 1;
    }
    else if(k < 0)
    {
        return 1 / myPowBranch(n, (long long)fabs(k));
    }
    else
    {
        return myPowBranch(n, (long long)k);
    }
}

2.2.3易错点

鄙人再实现这个算法的时候计算当k为负值的时候,因为需要求k的绝对值使用abs函数,导致k比较大的时候出现报错的现象

在运行测试样例 2 -2,147,483,648 会报错;

报错的原因:是因为k的类型时double类型应用fabs函数来取绝对值,因为k的值找过了int类型的范围所以会产生这样的报错,abs函数只能用于整型的取绝对值。

2.3分治的思想「快速幂算法 + 迭代」

2.3.1算法思路

对2.2的方法进行了进一步的优化,由于递归要利用大量的栈空间,所以我们不采取递归的方法的,从而实现节省空间;具体思路如下(算是三个方法中最难理解的一个,但是也是最优的一个代码):

2.3.2代码展示

double myPowBranch(double x, long long N)
{
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) 
        {
            if (N % 2 == 1)
            {
                // 如果 N 二进制表示的最低位为 1,那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位,这样我们每次只要判断最低位即可
            N = N >> 1;
        }
        return ans;
}
double myPow(double x, double N)
{
    return N >= 0 ? myPowBranch(x, N) : 1.0 / myPowBranch(x, -N);
}

如果内容帮到你,请点个赞,收藏一下吧;

如果有错误,欢迎在评论区指正;

相关文章
|
3天前
|
算法 Unix Linux
C语言随机数的产生(rand、srand、time函数细节讲解)
C语言随机数的产生(rand、srand、time函数细节讲解)
|
10天前
|
存储 C语言
C语言学习记录——动态内存函数介绍(malloc、free、calloc、realloc)
C语言学习记录——动态内存函数介绍(malloc、free、calloc、realloc)
17 1
|
1天前
|
安全 C语言
【C语言基础】:内存操作函数
【C语言基础】:内存操作函数
|
1天前
|
编译器 C语言 C++
【C语言基础】:字符函数和字符串函数-2
【C语言基础】:字符函数和字符串函数
|
1天前
|
C语言
【C语言基础】:字符函数和字符串函数-1
【C语言基础】:字符函数和字符串函数
TU^
|
2天前
|
编译器 程序员 Serverless
C语言之函数
C语言之函数
TU^
2 0
TU^
|
2天前
|
机器学习/深度学习 C语言
C语言之函数递归
C语言之函数递归
TU^
6 1
|
2天前
|
C语言
C语言——字符串操作函数
C语言——字符串操作函数
|
2天前
|
机器学习/深度学习 算法 C语言
【C语言基础】:函数递归详解
【C语言基础】:函数递归详解
|
2天前
|
编译器 程序员 C语言
【C语言基础】:函数详解
【C语言基础】:函数详解