0左边必有1的二进制字符串数量

本文主要是介绍0左边必有1的二进制字符串数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//0左边必有1的二进制字符串数量
public class GetNum{//递归的解法public static int GetNum01(int n){if(n<1){return 0;}return process(1,n);}//递归函数public static int process(int i,int n){if(i==n-1){return 2;}if(i==n){return 1;}return process(i+1,n)+process(i+2,n);}//迭代的解法public static int GetNum02(int n){if(n<1){return 0;}if(n==1){return 1;}int pre=1;int cur=1;int tmp=0;for(int i=2;i<n+1;i++){tmp=cur;cur+=pre;pre=tmp;}return cur;}//矩阵的乘法解法public static int GetNum03(int n){if(n<1){return 0;}if(n==1||n==2){return n;}int [][]base={{1,1},{1,0}};int [][]res=matrixPower(base,n-2);return 2*res[0][0]+res[1][0];}public static int[][] matrixPower(int[][] m, int p){int[][] res = new int[m.length][m[0].length];for (int i = 0; i < res.length; i++) {res[i][i] = 1;}int[][] tmp = m;for (; p != 0; p >>= 1) {if ((p & 1) != 0) {res = muliMatrix(res, tmp);}tmp = muliMatrix(tmp, tmp);}return res;}//矩阵的乘法public static int[][] muliMatrix(int[][] m1, int[][] m2) {int[][] res = new int[m1.length][m2[0].length];for (int i = 0; i < m1.length; i++) {for (int j = 0; j < m2[0].length; j++) {for (int k = 0; k < m2.length; k++) {res[i][j] += m1[i][k] * m2[k][j];}}}return res;}public static void main (String[]args){for (int i = 0; i <= 20; i++) {System.out.println(GetNum01(i));System.out.println(GetNum02(i));System.out.println(GetNum03(i));System.out.println("===================");}}
}