查logo的网站/网站制作推广电话

目录

1 问题描述

2 解决方案

2.1 从左至右二进制幂

2.2 从右至左二进制幂

 

---

1 问题描述

使用n的二进制表示，计算a的n次方。

 

---

2 解决方案

2.1 从左至右二进制幂

此方法计算a的n次方具体思想，引用《算法设计与分析基础》第三版一段文字介绍：

 

 

具体代码如下：

package com.liuzhen.chapter6;import java.util.ArrayList;
import java.util.Scanner;public class LeftRightBinaryExponentiation {//返回数字n的二进制数组public int[] get10To2(int n){ArrayList<Integer> list = new ArrayList<Integer>();while(n > 0){list.add(n % 2);n = n / 2;}int len = list.size();int[] result = new int[len];for(int i = 0;i < len;i++)result[i] = list.get(len-1-i);return result;}/** 函数功能：返回数字a的n次方结果*/public int getPowerA(int a,int n){int[] nTwo = get10To2(n);int result = a;for(int i = 1;i < nTwo.length;i++){result = result*result;if(nTwo[i] == 1)result *= a;}return result;}public static void main(String[] args){Scanner in = new Scanner(System.in);System.out.println("请输入一个数字n:");int n = in.nextInt();System.out.println("请输入一个数字a:");int a = in.nextInt();LeftRightBinaryExponentiation test = new LeftRightBinaryExponentiation();System.out.println("那么"+a+"的"+n+"次方结果："+test.getPowerA(a, n));}
} 

运行结果：

请输入一个数字n:
10
请输入一个数字a:
2
那么2的10次方结果：1024请输入一个数字n:
8
请输入一个数字a:
10
那么10的8次方结果：100000000

 

2.2 从右至左二进制幂

引用《算法设计与分析基础》第三版一段文字介绍：

 

 

具体代码如下：

package com.liuzhen.chapter6;import java.util.ArrayList;
import java.util.Scanner;public class RightLeftBinaryExponentiation {//返回数字n的二进制数组public int[] get10To2(int n){ArrayList<Integer> list = new ArrayList<Integer>();while(n > 0){list.add(n % 2);n = n / 2;}int len = list.size();int[] result = new int[len];for(int i = 0;i < len;i++)result[i] = list.get(len-1-i);return result;}//返回数字a的n次方结果public int getPowerA(int a,int n){int[] nTwo = get10To2(n);int temp = a;int len = nTwo.length;int result;if(nTwo[len-1] == 1)result = a;elseresult = 1;for(int i = len-2;i >= 0;i--){temp = temp*temp;if(nTwo[i] == 1)result *= temp;}return result;}public static void main(String[] args){Scanner in = new Scanner(System.in);System.out.println("请输入一个数字n:");int n = in.nextInt();System.out.println("请输入一个数字a:");int a = in.nextInt();RightLeftBinaryExponentiation test = new RightLeftBinaryExponentiation();System.out.println("那么"+a+"的"+n+"次方结果："+test.getPowerA(a, n));}
}

运行结果：

请输入一个数字n:
13
请输入一个数字a:
2
那么2的13次方结果：8192请输入一个数字n:
8
请输入一个数字a:
10
那么10的8次方结果：100000000