计算连续分数结果的最优算法

Question

一个连续的部分是这种类型的一系列划分:

depth   1    1+1/s

depth   2    1+1/(1+1/s)

depth   3    1+1/(1+1/(1+1/s))
  .     .      .           
  .     .      .      
  .     .      . 

深度是整数,但是s是浮点数.

什么是最佳算法(性能方面)来计算这样一个大深度的分数的结果？

Answer 1

提示:使用基本代数展开这些公式中的每一个.你会看到一种模式出现.

我会告诉你第一步,所以它变得很明显:

f(2,s) = 1+1/s = (s+1)/s
f(3,s) = 1+1/f(2,s) = 1+(s/(s+1)) = (1*(s+1) + s)/(s+1) = (2*s + 1) / (s + 1)
         /* You multiply the first "1" by denominator */
f(4,s) = 1+1/f(3,s) = 1+(s+1)/(2s+1) = (1*(2*s+1) + (s+1))/(2*s+1) = (3*s + 2) / (2*s + 1)
f(5,s) = 1+1/f(4,s) = 1+(2s+1)/(3s+2) = (1*(3*s+2) + (2s+1))/(3*s+2) = (5*s + 3) / (3*s + 2)

...

提示2:如果你没有看到上面出现的明显模式,最优化的算法将涉及计算斐波纳契数(因此你需要谷歌最佳的斐波那契#生成器).