siren0413
BAN USERwow, seems like someone took that the wrong way.
The idea behind this problem is similar as the way we solve Fibonacci in log(n) time costs, which we have to use matrix multiplication. so, even it has factor of 2, the basic algorithm is almost the same. What we need to do is to modify the Fibonacci algorithm a little bit, then we all set.
The Fibonacci algorithm:
| f(n+1) f(n) | = | 1 1 |^(n)
| f(n ) f(n-1) | | 1 0 |
Then we take a look at our problem:
| f(n+1) f(n) | =| 3 1 | *| 2 1 |^(n-1)
| f(n ) f(n-1)| | 1 0.5 | | 2 0 |
To solve our problem, I changed the
| 1 1 | to | 2 1 |
| 1 0 | | 2 0 |
because of the factor of 2. then in Fibonacci serious, the f(1) = 1 and f(2) =1 which is slightly different with our problem, in our problem, f(0)=0.5, f(1) = 1, f(2)=3, so I give it a initial matrix
| 3 1 | to let it start, then make the n to n-1, because
| 1 0 |
we've already got our initial matrix.
again, apologize for my little knowledge, I'm not writing code for airplane so no worries.
Quick Sort Version:
output: [4, 10, 5, 9, 6, 8, 7, 7, 8, 6, 9, 5]
- siren0413 February 18, 2013