分析:
在求一个数x的n次幂时,可分为偶数和奇数两种情况来讨论,若x为偶数,则x^n=x^n/2 * x^n/2,若果x为奇数,则x^n=x^(n-1)/2 * x^(n-1)/2 * x。它的基准情况(无需递归即能解出)很明显,就是n==0和n==1时,n==0时,则任何数的0次幂均为1,n==1时,任何数的1次幂均为它本身。
有了上述分析后,代码就很容易写出了。
public class Pow { public static void main(String[] args) { System.out.println(pow(2, 5)); System.out.println(pow(2, 10)); } /* * 求x得n次幂 */ public static long pow(long x,long n){ if(n==0){ return 1; } if(n==1){ return x; } if(x%2==0){ return pow(x*x, n/2); }else{ return pow(x*x, n/2)*x; /*return pow(x, n-1)*x;*/ //n为奇数时,n-1即为偶数,因此可以写成x^n=x^n-1 * x, //因为x^n-1的值是偶数次幂情况时已求出 } }} 二、非递归方法例子:
求x^5的值
5可以转成二进制,即101,5=2^2+2^0。
x^5因此可以写成x的2^2+2^0次幂。
我们知道一个数n,刚开始n%2==1的话,说明它转成二进制时,最低位为1,否则为0,下面进行n=n/2(n=n>>1)(右移操作);
如果再次进行n%2==1的话,说明此时的最低位为1,否则为0。
综上利用以上特性
public class Question23 { public static void main(String[] args) { System.out.println(Pow(3, 3)); //27 } public static int Pow(int x, int n) { int s = 1; while (n > 0) { if (n % 2 == 1) s *= x; x *= x; n >>= 1;//n=n/2; } return x; }}如果看不懂,不理解就找个例子代入,比如求4^11。
初始值x=4,n=11,s=1。
11的二进制表示为1011=1x2^3+0x2^2+1x2^1+1x2^0
第一次循环,n%2=1条件满足,s=4的1次方,x=4的2次方,n向右移动一位,即101
第二次循环,n%2=1条件满足,s=4的3次方,x=4的4次方,n继续向右移动一位,即10
第三次循环,n%2=1条件不满足,s=4的3次方没变,x=4的8次方,n继续向右移动一位,即1
第四次循环,n%2=1条件满足,s=4的11次方,此时x=4的16次方,n继续向右移动一位,即0
n>0条件不满足,结束循环。
看完这个过程,就应该明白了以下:
1011
↑
101
↑
10
↑
1
↑
1、x存在根本上是为了获得箭头所指的数在原本的数中的位权,因此依次为1,2,4,8
2、s存在根本上是为了求箭头所指数的和,因此为1,3,11。1101,其它位都为1,只有第三位为0,所以由3直接到11。
(4只是底数,不产生影响)
如果到这还不明白,建议多走几遍流程,便理解了。
For man is man and master of his fate