2025年[C语言]Pow函数的实现

科技前沿 • 2025-03-26 19:57 • 阅读 29

大家好，我是讯享网，很高兴认识大家。

力扣题目：

50. Pow(x, n) - 力扣（LeetCode）
讯享网https://leetcode.cn/problems/powx-n/

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); }

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

如果有错误，欢迎在评论区指正；

2025年[C语言]Pow函数的实现

力扣题目：

1.函数参数及返回值：

2.函数的实现

2.1暴力

2.1.1算法思路

2.1.2代码展示

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

2.2.1算法思路

2.2.2代码展示

2.2.3易错点

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

2.3.1算法思路

2.3.2代码展示

相关推荐