题5：设计一个高效的求a的n次幂的算法

算法分析：

1、可以用for循环实现 a*a*a*a*...

2、可以用递归实现 res*pow1(a,n-ex)

1 package recursion; 2  3 /** 4  * @author zsh 5  * @company wlgzs 6  * @create 2019-02-18 16:30 7  * @Describe 设计一个高效的求a的n次幂的算法 8  */ 9 public class Main8 {10 11     /**12      * 循环法求a的n次幂，复杂度O(n)13      * @param a14      * @param n15      * @return 结果16      */17     static int pow0(int a,int n){18         int res = 1;19         for (int i = 0; i < n; i++) {20             res = res*a;21         }22         return res;23     }24 25     /**26      * 优化后求a的n次幂27      * @param a28      * @param n29      * @return 结果30      */31     static int pow1(int a,int n){32         if (n == 0){33             return 1;34         }35         int res = a;36         //指数37         int ex = 1;38         while ( 2*ex <= n){39             res = res*res;40             ex = ex*2;41         }42         //差n-ex次方没有乘到结果上去43         return res*pow1(a,n-ex);44     }45 46     public static void main(String[] args) {47         System.out.println(pow0(2,15));48         System.out.println(pow1(2,15));49     }50 }