Как бы вы ответили на этот вопрос на интервью с Джанго?

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})

«Последний» вид - моя вторая версия, потому что первая версия не работала согласованно. Исходная версия хранила результат из «index» в LATEST. LATEST изначально был списком последовательностей fib (списков) вместо списка недавних значений N.

Полагаю, мой главный вопрос заключается в том, плохо ли хранить наибольшую последовательность fib, сгенерированную во время выполнения, в файле 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

Используйте эту прямую формулу. Для того, чтобы добраться до него, ищите решение уравнения линейного восстановления. Например. здесь .

Из-за ошибок с плавающей запятой вы должны округлить результат до ближайшего целого числа.