你会如何回答这个Django面试问题？

Question

我最近为某家公司做了一道编程题，作为面试前的准备。这道题是：

创建一个django应用，当然要以测试驱动的方式，向大家展示斐波那契数列。这个应用应该接受一个索引数字，并显示相应的斐波那契数列。此外，还应该有一个页面，显示最近生成的数列。而且，斐波那契有点急，不想等太久，所以要确保你的网络服务器运行得高效。

我想出了以下内容：

from django.views.generic.simple import direct_to_template
from django.http import Http404

LARGEST_SEQUENCE = [0,1] 
LARGEST = 1 
LATEST = []

def fib(n): 
    """Calculate the nth fibonacci sequence""" 
    global LARGEST
    if n > LARGEST: 
        while n > LARGEST: 
            next = LARGEST_SEQUENCE[LARGEST] + LARGEST_SEQUENCE[LARGEST-1] 
            #print 'appending ', next
            LARGEST_SEQUENCE.append(next)   
            LARGEST += 1  
        return LARGEST_SEQUENCE 
    else: 
        return LARGEST_SEQUENCE[0:n+1] 

def latest(request):
    results=[]
    for n in LATEST:
        result = fib(n)
        results.append((n,result))
    return direct_to_template(request, 'latest.html', {'results':results})

def index(request):
    if request.method=="POST":
        try:
            n=int(request.POST.get('n'))
        except:
            return Http404
        result = fib(n)
        if len(LATEST) >=  5:
            LATEST.pop()
        LATEST.insert(0,n)
    else:
        result = None
    return direct_to_template(request, 'base.html', {'result':result})

我所说的“最新”视图是我的第二个版本，因为第一个版本并不总是有效。最初的版本把“索引”的结果存储在 LATEST 中。 LATEST 最开始是一个斐波那契数列的列表，而不是最近的 N 值列表。

我主要想问的是，把运行时生成的最大斐波那契数列存储在 views.py 文件中，这样做是否不好？我知道这不是持久化存储，但题目并没有详细说明应该怎么做。你们觉得怎么样？如果是你们，你们会怎么解决这个问题？

谢谢大家！

Answer 1

尽管有一个大家都知道的计算公式是 O(1)，但在处理大数字时（比如100）它就不太管用了。

对于斐波那契数列，我会这样做：

def fib(n):
    "Complexity: O(log(n))"
    if n <= 0:
        return 0
    i = n - 1
    (a, b) = (1, 0)
    (c, d) = (0, 1)
    while i > 0:
        if i % 2:
            (a, b) = (d * b + c * a,  d * (b + a) + c * b)
        (c, d) = (c * c + d * d, d * (2 * c + d))
        i = i / 2
    return a + b

而对于最后的几个数字，我会创建一个模型。

from django.db import models

class Fibonacci(models.Model):
    parameter = models.IntegerField(primary_key=True)
    result = models.CharField(max_length=200)
    time = models.DateTimeField()

在显示这些内容时，我会这么做：

from models import Fibonacci

def index(request):
    result = None
    if request.method=="POST":
        try:
            n=int(request.POST.get('n'))
        except:
            return Http404
        try:
            result = Fibonacci.objects.get(pk=n)
            result.time = datetime.now()
        except DoesNotExist:
            result = str(fib(n))
            result = Fibonacci(n, result, datetime.now())
        result.save()
    return direct_to_template(request, 'base.html', {'result':result.result})

使用模型来获取最近的n条记录其实很简单。

Answer 2

每一个线性递推方程都可以直接求解。以斐波那契数列为例，它的方程是：

f_n+2 = f_n+1 + f_n
f_1 = 1
f_2 = 1

这个方程的解是：

f_n = 1/sqrt(5) * ((1+sqrt(5))/2)^n - 1/sqrt(5) * ((1-sqrt(5))/2)^n

使用这个直接的公式。如果想了解如何得到这个公式，可以查找线性递推方程的求解方法。例如，可以参考这里。

由于浮点数计算可能会出现误差，所以你应该把结果四舍五入到最接近的整数。