4.2 数值 - 指数

在 a^n 中,a 叫做底数,n 叫做指数。a^n 读作“a 的 n 次方”或“a 的 n 次幂“

数值的整数次方

题目：实现函数 double Power(double base, int exponent)，求 base 的 exponent 次方。

不需要考虑溢出。

用例：

2^3 = 8
0^3 = 0
2^0 = 1
2^-3 = 1/(2^3) = 0.125
0^-3 

分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后 30 秒写出如下的代码：

double Power(double base, int exponent)
{
  double result = 1.0;
  for(int i = 1; i <= exponent; ++i)
    result *= base;
  return result;
}

上面的代码没有考虑: exponent<=0 判断一个浮点数是不是等于 0 时，不是直接写 base == 0 ,而应该判断它们的差的绝对值是不是小于一个很小的范围

如果指数大于 0，我们还可以使用递归实现：a^n = a^(n/2)*a^(n/2) (n 为偶数)， 通过这个思路也可以实现

2^16 = 2^8 * 2^8
2^8 = 2^4 * 2^4
2^4 = 2^2 * 2^2
2^2 = 2^1 * 2^1
2^1 = 2

使用递归实现的代码示例：

double Power(double base, unsigned int exponent)
{
    if (exponent == 0) return 1;
    if (exponent == 1) return base;
    double result = Power(base, exponent >> 1);
    result *= result;

    if (exponent & 1) result = result*base;

    return reslut;
}

Sqrt(x)

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

求根号 2 的值

并且按照我的需要列出指定小数位，比如根号 2 是 1.141 我要列出 1 位小数就是 1.1 2 位就是 1.14， 1000 位就是 1.141...... 等。。

分析： 泰勒级数 牛顿迭代法

判断一个自然数是否是某个数的平方

说明：当然不能使用开方运算。

square(25) YES
square(35) NO

方法 1： 从 1 开始遍历，显然这种方法很差 方法 2： 除数跟余数比较，除数从 2 开始,每一轮都跟结果比较；相等就是存在这个数，不相等就把除数 ++；时间复杂度为（根号 n）。在一个数比较大时，效率不够好。如 1194877489 =（34567）^2,需要从 2 开始，一直比较到 34566，做 3 万多次除法和比较运算。跟方法 1 一样。。

方法 3：二分查找 O(logn)。比如 25:

a. 先取 (0+25)/2=12.5,12.512.5>25,因此这个数应该小于 12.5 b.（0+12）/2 = 6, 66>25 c. (0+6)/2 = 3 d. (3+6)/2 = 4.5 e. (5+6)/2 = 5.5

int is_powered(int num)