题目
实现函数double Power(double base, int exponet),求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
分析
暴力法
exponet次方，循环exponet次就可以了。时间复杂度为O(n)，O(1)；
C
#include<stdio.h> #include<stdlib.h> //暴力法 double Power(double base, int exponent) { int i = 0; double sum = 1; for (i = 0; i < exponent; i++) { sum *= base; } return sum; } int main() { printf("2^3=%f\n", Power(2, 3)); return 0; }
递归法
我们可以得出公式：baseexponet = base exponet-1;复杂度不变，但是写法比较优雅。
C
#include<stdio.h> #include<stdlib.h> //递归 double Power(double base, int exponent) { if (exponent == 0) { return 1; } return Power(base, exponent - 1) * base; } int main() { printf("2^3=%f\n", Power(2, 3)); return 0; }
但是上面俩种方法都存在一种隐藏危险，如果输出负数怎么办？？？
所以我们要把所有情况都考虑进来比如，base=0,exponent为负数，小数，零等。
优化的暴力法
C
#include<stdio.h> #include<stdlib.h> double Power(double base, double exponent) { if (base == 0 || exponent < 0)//exponent < 0 { return -1; } int flag = 1;//记录exponent正负，1表示大于1，-1表示在0-1直接 int i = 0; double sum = 1; if (exponent < 1 && exponent > 0)//0 < exponent < 1 { exponent = 1.0 / exponent; flag = -1; } for (i = 0; i < exponent; i++) { sum *= base; } if (flag == -1)//如果exponent本身是小数就求倒数 { sum = 1.0 / sum; } return sum; } int main() { printf("2^3=%f\n", Power(2, 3)); return 0; }
公式+递归
如果求216，可以转换为求28 * 28；28 = 24*24；24 = 22 * 22；22 = 21 * 21;
同理求215，215 = 27*28；28又等价于上面得到计算，这里我们只算27；27=24*23;23=21*22;
我们还可以优化215。215 = 2 * 2 7 * 27;把那个奇数单独拿出来。
根据上面的规律我们可以列一个公式
我们根据公式实现递归算法。
时间复杂度为O(log2n),空间复杂度为O(1);
C
#include<stdio.h> #include<stdlib.h> //这里的exponent是整数哦 double PowerRecursion(double base, int exponent)//递归计算 { if (exponent == 0) { return 1; } if (exponent == 1) { return base; } double sum = PowerRecursion(base, exponent >> 1); sum *= sum; if (exponent % 2 == 1)//只要是奇数，就在单独乘一次。 { sum *= base; } return sum; } double Power(double base, double exponent) { if (base == 0 || exponent < 0)//exponent < 0 { return -1; } int flag = 1;//记录exponent正负，1表示大于1，-1表示在0-1直接 int i = 0; double sum = 1; if (exponent < 1 && exponent > 0)//0 < exponent < 1 { exponent = 1.0 / exponent; flag = -1; } sum = PowerRecursion(base, (int)exponent); if (flag == -1)//如果exponent本身是小数就求倒数 { sum = 1.0 / sum; } return sum; } int main() { printf("2^3=%f\n", Power(2, 3)); return 0; }
本章完！
