java幂函数的实现,Java 幂

　　00-1010介绍具体方法代码实现标题矩阵斐波那契数列的快速幂，用第n个泰波纳契数统计元音序列的个数。

　　00-1010快速求幂是一种高效的求幂方法。

　　比如我们求X的90次方，一般的方法可以经历一个循环，每次乘以一个X，然后循环90次就可以得到答案。时间复杂度为O(n)，效率较低。借助fast power，我们可以在O(log(n))的时间复杂度内完成这个运算。

　　00-1010我们可以通过二进制的视角来看幂运算。

　　要计算xn，请以二进制形式展开n。

　　所以只需要用一个周期就可以找到n的二进制的每一位，在每个周期中，如果二进制位是0，就不需要乘法。如果这个二进制位是1，就需要乘以x .而x *=x是在每个周期执行的，所以一次可以得到x的不同次方。

　　class Solution { public double myPow(double x，int n){ long exp=n；//特殊处理：补码表示的负最小值的倒数超过整数表示范围，所以增加数据表示范围if(x==0.0)返回0.0；if(n ^ 0){ x=1/x；exp=-exp；} double res=1.0while(exp 0){ if((exp 1)==1)RES *=x；x *=xexp=1；} return res}}

引入

具体方法

　　解法：求一个满足矩阵乘法的递推关系。

　　F(n)=f(n-1) f(n-2)，其依赖状态存储为列向量。

　　目标值f(n)的矩阵为：

　　关键是找到这两个矩阵直接满足的关系，知道系数矩阵mat。

　　"text-align:center">

　　则令

　　我们就成功找到了系数矩阵。

　　下面可以求得递推关系式：

　　对于mat可以通过快速幂求得结果。

class Solution { int mod = (int)1e9+7; public int fib(int n) { if(n <= 1) return n; long[][] mat = new long[][]{ {1, 1}, {1, 0} }; long[][] ans = new long[][]{ {1}, {0} }; int count = n - 1; while(count > 0) { if((count & 1) == 1) ans = mul(mat, ans); // 注意矩阵乘法顺序，不满足交换律 mat = mul(mat, mat); count >>= 1; } return (int)(ans[0][0] % mod); } public long[][] mul(long[][] a, long[][] b) { // 矩阵乘法，新矩阵的行数 = a的行数rowa，列数 = b的列数colb // a矩阵的列数 = b矩阵的行数 = common int rowa = a.length, colb = b[0].length, common = b.length; long[][] ans = new long[rowa][colb]; for (int i = 0; i < rowa; i++) { for (int j = 0; j < colb; j++) { for (int k = 0; k < common; k++) { ans[i][j] += a[i][k] * b[k][j]; ans[i][j] %= mod; } } } return ans; }}

第 N 个泰波那契数

　　解：

　　对于mat的幂运算可以使用快速幂

class Solution { public int tribonacci(int n) { if(n == 0) return 0; if(n == 1 n == 2) return 1; int[][] mat = new int[][]{ {1, 1, 1}, {1, 0, 0}, {0, 1, 0} }; int[][] ans = new int[][]{ {1}, {1}, {0} }; int count = n - 2; while(count > 0) { if((count & 1) == 1) ans = mul(mat, ans); mat = mul(mat, mat); count >>= 1; } return ans[0][0]; } public int[][] mul(int[][] a, int[][] b) { int rowa = a.length; int colb = b[0].length; int common = b.length; int[][] ans = new int[rowa][colb]; for(int i = 0; i < rowa; i++) { for(int j = 0; j < colb; j++) { for(int k = 0; k < common; k++) { ans[i][j] += a[i][k] * b[k][j]; } } } return ans; }}

统计元音字母序列的数目

　　提示：1 <= n <= 2 * 10^4

　　解：题目中给定的字符的下一个字符的规则如下：

　　字符串中的每个字符都应当是小写元音字母（‘a’,‘e’,‘i’,‘o’,‘u’）；

　　每个元音 ‘a’ 后面都只能跟着 ‘e’；每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘a’；每个元音 ‘i’ 后面不能再跟着另一个 ‘i’；每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’；每个元音 ‘u’ 后面只能跟着 ‘a’；以上等价于每个字符的前一个字符的规则如下：

　　元音字母 ‘a’ 前面只能跟着 ‘e’,‘i’,‘u’；元音字母 ‘e’ 前面只能跟着 ‘a’,‘i’；每个元音 ‘i’ 前面只能跟着 ‘e’,‘o’；每个元音 ‘o’ 前面只能跟着 ‘i’；每个元音 ‘u’ 前面只能跟着 ‘o’,‘i’；我们设 f[i][j] 代表当前长度为 i 且以字符 j 为结尾的字符串的数目，其中在此 j=0,1,2,3,4 分别代表元音字母 ‘a’,‘e’,‘i’,‘o’,‘u’

class Solution { long mod = 1_000_000_007; public int countVowelPermutation(int n) { long[][] mat = { {0, 1, 0, 0, 0}, {1, 0, 1, 0, 0}, {1, 1, 0, 1, 1}, {0, 0, 1, 0, 1}, {1, 0, 0, 0, 0} }; long[][] ans = { {1},{1},{1},{1},{1} }; int count = n - 1; while(count > 0) { if((count & 1) == 1) ans = mul(mat, ans); mat = mul(mat, mat); count >>= 1; } long res = 0; for(int i = 0; i < 5; i++) { res += ans[i][0]; } return (int)(res % mod); } public long[][] mul(long[][] a, long[][] b) { int rowa = a.length; int colb = b[0].length; int common = b.length; long[][] ans = new long[rowa][colb]; for(int i = 0; i < rowa; i++) { for(int j = 0; j < colb; j++) { for(int k = 0; k < common; k++) { ans[i][j] += a[i][k] * b[k][j]; ans[i][j] %= mod; } } } return ans; }}

以上就是Java数据结构之快速幂的实现的详细内容，更多关于Java快速幂的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

java幂函数的实现,Java 幂

目录

引入

具体方法

第 N 个泰波那契数

统计元音字母序列的数目

相关文章阅读