| 145 | |
| 146 | // 用矩阵乘法解决斐波那契第n项的问题 |
| 147 | public static void f3() { |
| 148 | // 0 1 1 2 3 5 8 13 21 34... |
| 149 | // 0 1 2 3 4 5 6 7 8 9 |
| 150 | int[][] start = { { 1, 0 } }; |
| 151 | int[][] m = { |
| 152 | { 1, 1 }, |
| 153 | { 1, 0 } |
| 154 | }; |
| 155 | int[][] a = multiply(start, m); |
| 156 | // 1 1 |
| 157 | // 1 0 |
| 158 | // |
| 159 | // 1 0 1 1 |
| 160 | print(a); |
| 161 | System.out.println("======"); |
| 162 | int[][] b = multiply(a, m); |
| 163 | // 1 1 |
| 164 | // 1 0 |
| 165 | // |
| 166 | // 1 1 2 1 |
| 167 | print(b); |
| 168 | System.out.println("======"); |
| 169 | int[][] c = multiply(b, m); |
| 170 | // 1 1 |
| 171 | // 1 0 |
| 172 | // |
| 173 | // 2 1 3 2 |
| 174 | print(c); |
| 175 | System.out.println("======"); |
| 176 | int[][] d = multiply(c, m); |
| 177 | // 1 1 |
| 178 | // 1 0 |
| 179 | // |
| 180 | // 3 2 5 3 |
| 181 | print(d); |
| 182 | } |
| 183 | |
| 184 | // 用矩阵快速幂解决斐波那契第n项的问题 |
| 185 | public static void f4() { |