a**********s
发帖数: 588 | 1 有几个同学问面筋，不太记得起来，很多版上是有的，所以觉得那些面你的人水平挺一
般的，下面贴两个印象深刻的：
1。这道题被好几个不同的公司面到过：Fibonacci数列，一般让你给一个recursive的
版本，然后写个iterative的版本，然后问有没有更快的可能性。我记得以前在某个版
讨论过，参考wiki:
这样的方法，可以在O(log(N))的时间和O(1)的空间复杂度内算好。要写程序的话，用
类似下面的方法：
Matrix2x2 F[][2] = {{1, 1}, {1, 0}}, Fn[2][2] = {{1, 0}, {0, 1}};
while (N) {
if (N & 1)
mul(F, Fn, Fn); // Fn = Fn x F;
mul(F, F, F); // F = F^2;
N = N >> 1;
}
2。另外一题很简单，但是蛮tricky的。How to test if a number "a" is power of 2
return (a-1) & (a) == 0;
网上经常有问怎么 | y*******g
发帖数: 6599 | 2 第二个很有趣.
【在 a**********s 的大作中提到】
: 有几个同学问面筋，不太记得起来，很多版上是有的，所以觉得那些面你的人水平挺一
: 般的，下面贴两个印象深刻的：
: 1。这道题被好几个不同的公司面到过：Fibonacci数列，一般让你给一个recursive的
: 版本，然后写个iterative的版本，然后问有没有更快的可能性。我记得以前在某个版
: 讨论过，参考wiki:
: 这样的方法，可以在O(log(N))的时间和O(1)的空间复杂度内算好。要写程序的话，用
: 类似下面的方法：
: Matrix2x2 F[][2] = {{1, 1}, {1, 0}}, Fn[2][2] = {{1, 0}, {0, 1}};
: while (N) {
: if (N & 1)
| o***r
发帖数: 81 | 3 感谢！ fibonacci数列用矩阵算这个很有启发性！
我终于理解为啥线性递推的关系式都可以用矩阵做了……
【在 a**********s 的大作中提到】
: 有几个同学问面筋，不太记得起来，很多版上是有的，所以觉得那些面你的人水平挺一
: 般的，下面贴两个印象深刻的：
: 1。这道题被好几个不同的公司面到过：Fibonacci数列，一般让你给一个recursive的
: 版本，然后写个iterative的版本，然后问有没有更快的可能性。我记得以前在某个版
: 讨论过，参考wiki:
: 这样的方法，可以在O(log(N))的时间和O(1)的空间复杂度内算好。要写程序的话，用
: 类似下面的方法：
: Matrix2x2 F[][2] = {{1, 1}, {1, 0}}, Fn[2][2] = {{1, 0}, {0, 1}};
: while (N) {
: if (N & 1)
| h***n
发帖数: 276 | 4 第一题不是有数学公式摆在那里嘛
【在 a**********s 的大作中提到】
: 有几个同学问面筋，不太记得起来，很多版上是有的，所以觉得那些面你的人水平挺一
: 般的，下面贴两个印象深刻的：
: 1。这道题被好几个不同的公司面到过：Fibonacci数列，一般让你给一个recursive的
: 版本，然后写个iterative的版本，然后问有没有更快的可能性。我记得以前在某个版
: 讨论过，参考wiki:
: 这样的方法，可以在O(log(N))的时间和O(1)的空间复杂度内算好。要写程序的话，用
: 类似下面的方法：
: Matrix2x2 F[][2] = {{1, 1}, {1, 0}}, Fn[2][2] = {{1, 0}, {0, 1}};
: while (N) {
: if (N & 1)
| c******a
发帖数: 198 | 5 大侠可以解释一下1里面的while吗？看的不是很懂的说。
【在 a**********s 的大作中提到】
: 有几个同学问面筋，不太记得起来，很多版上是有的，所以觉得那些面你的人水平挺一
: 般的，下面贴两个印象深刻的：
: 1。这道题被好几个不同的公司面到过：Fibonacci数列，一般让你给一个recursive的
: 版本，然后写个iterative的版本，然后问有没有更快的可能性。我记得以前在某个版
: 讨论过，参考wiki:
: 这样的方法，可以在O(log(N))的时间和O(1)的空间复杂度内算好。要写程序的话，用
: 类似下面的方法：
: Matrix2x2 F[][2] = {{1, 1}, {1, 0}}, Fn[2][2] = {{1, 0}, {0, 1}};
: while (N) {
: if (N & 1)
| s*******i
发帖数: 712 | 6 问问那个 Fn[2][2] = {{1, 0}, {0, 1}}和 Fn = Fn * F
的部分是怎么回事？
http://upload.wikimedia.org/math/a/6/0/a6083f85f39b468210f5715a8e30d572.pn
g
【在 a**********s 的大作中提到】
: 有几个同学问面筋，不太记得起来，很多版上是有的，所以觉得那些面你的人水平挺一
: 般的，下面贴两个印象深刻的：
: 1。这道题被好几个不同的公司面到过：Fibonacci数列，一般让你给一个recursive的
: 版本，然后写个iterative的版本，然后问有没有更快的可能性。我记得以前在某个版
: 讨论过，参考wiki:
: 这样的方法，可以在O(log(N))的时间和O(1)的空间复杂度内算好。要写程序的话，用
: 类似下面的方法：
: Matrix2x2 F[][2] = {{1, 1}, {1, 0}}, Fn[2][2] = {{1, 0}, {0, 1}};
: while (N) {
: if (N & 1)
| a**********s
发帖数: 588 | 7 不好意思, 我没有写好, 刚才写了一个, 你可以copy&paste一下看看, 当然, 上面几楼
说的直接推导的公式是最干净利落的
template
struct Mat2X2
{
T m[4];
T* operator [] (int i) { return m + i*2; }
const T* operator [] (int i) const { return m + i*2; }
Mat2X2 operator * (const Mat2X2& op) const {
Mat2X2 M = {
(*this)[0][0] * op[0][0] + (*this)[0][1] * op[1][0],
(*this)[0][0] * op[0][1] + (*this)[0][1] * op[1][1],
(*this)[1][0] * op[0][0] + (*this)[1][1] * op[1][0],
(*
【在 s*******i 的大作中提到】
: 问问那个 Fn[2][2] = {{1, 0}, {0, 1}}和 Fn = Fn * F
: 的部分是怎么回事？
:
: http://upload.wikimedia.org/math/a/6/0/a6083f85f39b468210f5715a8e30d572.pn
: g
| z****e
发帖数: 2024 | 8 identity matrix.
for odd numbers.
Lz's code is good.
【在 s*******i 的大作中提到】
: 问问那个 Fn[2][2] = {{1, 0}, {0, 1}}和 Fn = Fn * F
: 的部分是怎么回事？
:
: http://upload.wikimedia.org/math/a/6/0/a6083f85f39b468210f5715a8e30d572.pn
: g
| q******u
发帖数: 46 | 9 有公式要算a^n也要log(n)啊，而且和lz的算法也差不多的，her code is nice，
【在 h***n 的大作中提到】
: 第一题不是有数学公式摆在那里嘛
| s*********l
发帖数: 103 | 10 1. Fibonacci Numbers
http://fayaa.com/code/view/544/
2. Two more related questions:
http://www.spellscroll.com/questionfull/243/
Given a number N, find out the nearest power of 2 which is greater than or
equal to N.
http://www.spellscroll.com/questionfull/222/
Determine if a number is a power of an integer.
【在 a**********s 的大作中提到】
: 有几个同学问面筋，不太记得起来，很多版上是有的，所以觉得那些面你的人水平挺一
: 般的，下面贴两个印象深刻的：
: 1。这道题被好几个不同的公司面到过：Fibonacci数列，一般让你给一个recursive的
: 版本，然后写个iterative的版本，然后问有没有更快的可能性。我记得以前在某个版
: 讨论过，参考wiki:
: 这样的方法，可以在O(log(N))的时间和O(1)的空间复杂度内算好。要写程序的话，用
: 类似下面的方法：
: Matrix2x2 F[][2] = {{1, 1}, {1, 0}}, Fn[2][2] = {{1, 0}, {0, 1}};
: while (N) {
: if (N & 1)
| j**l
发帖数: 2911 | 11 说明一下，那个在O(logN)时间计算矩阵的N次方的方法是从如下的计算整数a的N次方的
方法推广而来
unsigned long long power(int a, int n)
{
unsigned long long result =1;
int p = a;
while (n)
{
if (n & 1)
result *= p;
n >>= 1;
p *= p;
}
return result;
} | m********g
发帖数: 692 | |
|
