计算f(i)的函数

Question

当i为正整数时，存在满足下列条件的函数f(i)

f(0) = 0,
f(1) = 1
f(i) = f(i-1) + f(i-2)

所以，基于以上，我想写一个程序来确定f(i)。并编写程序求f(1000).

Answer 1

第 100 个斐波那契数是一个 巨大的值，因此需要 BigInteger (C#) 或其类似物。 C#实现可以是这样的（我怀疑它是否会被接受为家庭作业代码）。

private static IEnumerable<BigInteger> fibo() {
  yield return 0;
  yield return 1;

  BigInteger first = 0;
  BigInteger second = 1;

  while (true) {
    BigInteger result = first + second;

    first = second;
    second = result;

    yield return result;
  }
}

// Skip(1000) since it's defined that f(0) == 0 - unusual sequence starting;
// in mathematics sequences usually started from the 1st item
Console.Write(fibo().Skip(1000).FirstOrDefault().ToString());

答案是

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Answer 2

由于您似乎要让编程语言保持开放状态，所以我选择 python 这对这些事情来说非常有用。

你可以简单地做：

def f(i):
    if i == 0:
        return 0
    elif i == 1:
        return 1
    return f(i-1)+f(i-2)

如果你想更花哨和高效，使用迭代器：

def f():
    a, b = 0, 1
    while True:            
        yield a            
        a, b = b, a + b

代码运行速度非常快：

for i, val in enumerate(f()):
    if i == 1000:
        print val
        break

和 return 您想要的值 f(1000)，即：

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

@DmitryBychenko：你return输入的值实际上是 f(999)。

@MartinEvans：您的代码实际上是不正确的（差 1）。一种显而易见的方式是 f(1) 和 f(2) 编辑的值 return 是错误的：

>>> def f(i):
...     a,b = 0, 1
...     for i in range(i-1):
...             a,b = b, a+b
...     return a
... 
>>> f(0)
0
>>> f(1)
0
>>> f(2)
1
>>> f(3)
1

Answer 3

以下 Python 3.0 脚本可以工作：

def f(i):
    a, b = 0, 1

    for i in range(i):
        a, b = b, a + b

    return a

print(f(0))
print(f(1))
print(f(2))
print(f(3))
print(f(1000))

给你：

和

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Answer 4

显然，这需要 bc:

#!/usr/bin/bc --quiet

define fib(n) {
auto a,b,i;
if(n<2)return n;a=0;b=1;for(i=1;i<n;++i){c=a+b;a=b;b=c}return b;}

print fib(1000), "\n"
quit

计算f(i)的函数

Calculate the function of f(i)

function

fibonacci