面试时碰到的一道题目,题目的要求是:

The definition of a Fibonacci sequence is like this:

  • F(0) = 0

  • F(1) = 1

  • F(n) = F(n-1) + F(n-2)

Now let’s define G(n) = F(n)/F(n+1).

Golden ratio is the limit of G(n) when n approaches infinity.

With all the above information, we have a way to estimating golden ratio g:

Find the first n that matches |G(n+1) - G(n)| < t, where t is the precision threshold, then the corresponding G(n) is considered as the estimated value of golden ratio.

第一眼看到这题的时候,脑子里蹦出来的就是“递归”实现斐波那契数列,然后去计算G(n)的值,去计算判断一下即可,所以代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def estimate_golden_ratio(t)
  return nil if t <= 0

  n = 2
  while n do
    result = (cal_g(n+1) - cal_g(n)).abs

    if (result < t)
        return n
    else
        n += 1
    end
  end
end

def fibonacci(n)
    return n if n <= 1
    (fibonacci(n-1) + fibonacci(n-2))
end

def cal_g(n)
    return (fibonacci(n).to_f / fibonacci(n+1).to_f)
end

puts estimate_golden_ratio(1e-6)
puts estimate_golden_ratio(1e-8)
puts estimate_golden_ratio(1e-10)
puts estimate_golden_ratio(1e-15)
puts estimate_golden_ratio(1e-20)

然后理所当然的会有问题,递归实现的问题就是计算度高的时候会导致超时。面试官问了下有没有什么想法去优化,我的反应就是使用循环去替代递归实现,这样子可以提高计算。

但后面经过提醒仔细想了下,这个不是单纯的计算数列,它是需要获得一个期望的n值,不断的循环去获得所期望的值,其实呢也就是不断循环的计算F(),这里面重复的计算其实也是一个影响因素,当然修改斐波那契数列也是提高计算速度的。所以自己的想法是使用一个数组去保存计算的值,减少重复计算。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
FI_ARRAY = [0, 1]

def estimate_golden_ratio(t)
  return nil if t <= 0

  n = 2
  while n do
    result = (cal_g(n+1) - cal_g(n)).abs

    if (result < t)
        return n
    else
        n += 1
    end
  end
end

def fibonacci(n)
    arr_length = FI_ARRAY.length

    if n >= arr_length
        for i in arr_length..n
            FI_ARRAY[i] = FI_ARRAY[i-1] + FI_ARRAY[i-2]
        end
    end

    return FI_ARRAY[n]
end

def cal_g(n)
    return (fibonacci(n).to_f / fibonacci(n+1).to_f)
end

puts estimate_golden_ratio(1e-6)
puts estimate_golden_ratio(1e-8)
puts estimate_golden_ratio(1e-10)
puts estimate_golden_ratio(1e-15)
puts estimate_golden_ratio(1e-20)

当然这个也是有它的问题,当计算度变高时,需要保存的值增多,数组也会变大,空间消耗也会增多。后面想了下,也写了个普通的解法,当然呢这里面还是存在大量重复计算,所以计算应该还是上面那个更快。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def estimate_golden_ratio(t)
  return nil if t <= 0

  n = 2
  while n do
    tmp_g, tmp_g_1 = cal_g(n)
    result = (tmp_g_1 - tmp_g).abs

    if (result < t)
        return n
    else
        n += 1
    end
  end
end

def fibonacci(n)
    result_array = [0, 1]
    first, second = result_array

    for i in 2..n+1
        third = first + second
        first = second
        second = third
    end

    result_array = [first, second]
    return result_array
end

def cal_g(n)
    tmp_n, tmp_n_1 = fibonacci(n)
    tmp_n_2 = tmp_n + tmp_n_1

    tmp_g = tmp_n.to_f / tmp_n_1.to_f
    tmp_g_1 = tmp_n_1.to_f / tmp_n_2.to_f
    return [tmp_g, tmp_g_1]
end

puts estimate_golden_ratio(1e-6)
puts estimate_golden_ratio(1e-8)
puts estimate_golden_ratio(1e-10)
puts estimate_golden_ratio(1e-15)
puts estimate_golden_ratio(1e-20)

上面的代码是满足了题目设定的计算,但是自己考虑,当给出的t过小时,浮点数的精度损失大于了t时,这个就会产生结果上的误差,此时就需要考虑其他的方案了。

从此可以看出来,一道简单的题其实可以引申出来探讨的内容还是很多的,有时还是需要自己多思考,多探索,还是多努力加油吧!