C 实现计算 x 的 n 次幂递归快速幂详解题目描述给定一个浮点数x和一个整数n请计算x的n次幂即x^n。其中x表示底数。n表示指数。n可以是正数、负数或者 0。例如输入2 10 输出1024输入2 -3 输出0.125思路分析如果使用普通循环计算x^n需要连续乘n次时间复杂度是O(n)。为了提高效率可以使用快速幂思想。快速幂的核心是每次把指数缩小一半。当n是偶数时x^n (x * x)^(n / 2)当n是奇数时x^n x * (x * x)^(n / 2)当n是负数时可以转换成倒数形式x^(-n) (1 / x)^n这样就可以用递归不断缩小指数提高计算效率。边界情况本题需要注意以下几种情况当n 0时结果为1。当n 1时结果为x。当n 0时需要转换为倒数计算。当x 0且n 0时数学上没有意义因为会出现除以 0。另外处理负指数时不要直接写-n。如果n是int类型的最小值直接取反会导致溢出。因此代码中使用-(n 1)来避免这个问题。代码实现#includeiostream#includeiomanip#includestdexceptusingnamespacestd;classPowerCalculator{public:doublecalculate(doublex,intn){if(n0)return1.0;if(n1)returnx;if(x0n0){throwinvalid_argument(0 cannot be raised to a negative power.);}if(n0){intpositiveN-(n1);return(1/x)*calculate(1/x,positiveN);}inthalfn/2;if(n%20){returncalculate(x*x,half);}else{returnx*calculate(x*x,half);}}};intmain(){PowerCalculator calculator;doublex;intn;cout请输入底数 x 与指数 nendl;cinxn;try{coutfixedsetprecision(6);coutx 的 n 次幂为calculator.calculate(x,n)endl;}catch(constexceptione){cout计算错误e.what()endl;}return0;}运行示例输入2 10输出2.000000 的 10 次幂为1024.000000输入2 -3输出2.000000 的 -3 次幂为0.125000输入5 0输出5.000000 的 0 次幂为1.000000复杂度分析快速幂每次递归都会把指数缩小一半。因此时间复杂度O(log n)空间复杂度O(log n)空间复杂度主要来自递归调用栈。