Попытайтесь использовать карту, n является ключом, и его соответствующее Число Фибоначчи является значением.

@Paul

спасибо за информацию. Я не знал это. От ссылка Википедии Вы упомянули:

Этот метод сохранения значений, которые были уже вычислены, называют memoization

Да, я уже посмотрел на код (+1). :)

Действительно ли это - сознательно выбранный пример? (например, крайний случай, который Вы желаете протестировать)

, Как это в настоящее время O (1.6^n) я просто, хотят удостовериться, что Вы просто ищете ответы при обработке общего случая этой проблемы (кэширующий значения, и т.д.) и не просто случайно пишущий плохой код :D

Рассмотрение этого конкретного случая, вроде которого у Вас могло быть что-то:

var cache = [];
function fib(n) {
    if (n < 2) return 1;
    if (cache.length > n) return cache[n];
    var result = fib(n - 2) + fib(n - 1);
    cache[n] = result;
    return result;
}

, Который ухудшается к O (n) в худшем случае :D

[Редактирование: * не равняется + :D]

[Еще одно редактирование: версия Haskell (потому что я - мазохист или что-то)

fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n

]

Какой язык - это? Это ничего не переполняет в c... Кроме того, можно попытаться создать справочную таблицу на "куче" или использовать карту

кэширование обычно является хорошей идеей для такого рода вещи. Так как числа Фибоначчи являются постоянными, можно кэшировать результат, после того как Вы вычислили его. Quick C / пример псевдокода

class fibstorage {


    bool has-result(int n) { return fibresults.contains(n); }
    int get-result(int n) { return fibresult.find(n).value; }
    void add-result(int n, int v) { fibresults.add(n,v); }

    map<int, int>   fibresults;

}


fib(int n ) {
    if(n==0 || n==1)
            return 1;

    if (fibstorage.has-result(n)) {
        return fibstorage.get-result(n-1);
    }

    return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
             (fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
           );
}


calcfib(n) {
    v = fib(n);
    fibstorage.add-result(n,v);
}

Это было бы довольно медленно, поскольку каждая рекурсия приводит к 3 поискам, однако это должно проиллюстрировать общее представление

Быстрый и грязный memoization в C++:

Любой рекурсивный метод type1 foo(type2 bar) { ... } легко мемоизован с map<type2, type1> M.

// your original method
int fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
    if(n==0 || n==1)
        return 1;

    // only compute the value for fib(n) if we haven't before
    if(M.count(n) == 0)
        M[n] = fib(n-1) + fib(n-2);

    return M[n];
}

РЕДАКТИРОВАНИЕ: @Konrad Rudolph
Konrad указывает что станд.:: карта не является самой быстрой структурой данных, которую мы могли использовать здесь. Это правда, vector<something> должно быть быстрее, чем map<int, something> (хотя могло бы требоваться больше памяти, если бы исходные данные к рекурсивным вызовам функции не были последовательными целыми числами как, они в этом случае), но карты удобны использовать обычно.

Согласно Википедия Выдумка (0) должна быть 0, но она не имеет значения.

Вот простое решение C# с для цикла:

ulong Fib(int n)
{
  ulong fib = 1;  // value of fib(i)
  ulong fib1 = 1; // value of fib(i-1)
  ulong fib2 = 0; // value of fib(i-2)

  for (int i = 0; i < n; i++)
  {
    fib = fib1 + fib2;
    fib2 = fib1;
    fib1 = fib;
  }

  return fib;
}

Это - довольно общий прием, чтобы преобразовать рекурсию в хвостовая рекурсия и затем циклично выполниться. Поскольку больше детали видит, например, этот лекция (ppt).

Если Вы используете C# и можете использовать PostSharp, вот простой memoization аспект для Вашего кода:

[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
    private Dictionary<Object[], Object> _Cache;

    public MemoizeAttribute()
    {
        _Cache = new Dictionary<object[], object>(this);
    }

    public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
    {
        Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
        if (_Cache.ContainsKey(arguments))
        {
            eventArgs.ReturnValue = _Cache[arguments];
            eventArgs.FlowBehavior = FlowBehavior.Return;
        }
    }

    public override void OnExit(MethodExecutionEventArgs eventArgs)
    {
        if (eventArgs.Exception != null)
            return;

        _Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
    }

    #region IEqualityComparer<object[]> Members

    public bool Equals(object[] x, object[] y)
    {
        if (Object.ReferenceEquals(x, y))
            return true;

        if (x == null || y == null)
            return false;

        if (x.Length != y.Length)
            return false;

        for (Int32 index = 0, len = x.Length; index < len; index++)
            if (Comparer.Default.Compare(x[index], y[index]) != 0)
                return false;

        return true;
    }

    public int GetHashCode(object[] obj)
    {
        Int32 hash = 23;

        foreach (Object o in obj)
        {
            hash *= 37;
            if (o != null)
                hash += o.GetHashCode();
        }

        return hash;
    }

    #endregion
}

Вот является образец реализацией Fibonacci с помощью него:

[Memoize]
private Int32 Fibonacci(Int32 n)
{
    if (n <= 1)
        return 1;
    else
        return Fibonacci(n - 2) + Fibonacci(n - 1);
}

Это называют memoization и существует очень хорошая статья о Matthew Podwysocki memoization отправлена в эти дни. Это использует Fibonacci для иллюстрирования его. И показывает код в C# также. Считайте его здесь .

Путем Perl имеет модуль memoize , который делает это для любой функции в Вашем коде, который Вы указываете.

# Compute Fibonacci numbers
sub fib {
      my $n = shift;
      return $n if $n < 2;
      fib($n-1) + fib($n-2);
}

, Чтобы к memoize эта функция все Вы делаете, запускают Вашу программу с

use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)

@lassevk:

Это является потрясающим, точно о чем я думал в моей голове после чтения о memoization в высший порядок Perl . Двумя вещами, которые я думаю, были бы полезные дополнения:

1. дополнительный параметр для определения статического метода или членского метода, который используется для генерации ключа к кэшу.
2. дополнительный способ изменить кэш возражает так, чтобы Вы могли использовать диск, или база данных поддержала кэш.

Не уверенный, как сделать этот вид вещи с Атрибутами (или если они даже возможны с этим видом реализации), но я планирую попытаться выяснить.

(Вне темы: Я пытался отправить это как комментарий, но я не понял, что комментарии имеют такую короткую позволенную длину, таким образом, это действительно не соответствует как 'ответ')

При использовании языка с первоклассными функциями как Схема можно добавить memoization, не изменяя первоначальный алгоритм:

(define (memoize fn)
  (letrec ((get (lambda (query) '(#f)))
           (set (lambda (query value)
                  (let ((old-get get))
                    (set! get (lambda (q)
                                (if (equal? q query)
                                    (cons #t value)
                                    (old-get q))))))))
    (lambda args
      (let ((val (get args)))
        (if (car val)
            (cdr val)
            (let ((ret (apply fn args)))
              (set args ret)
              ret))))))


(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

первый блок предоставляет memoization услугу, и второй блок является последовательностью fibonacci с помощью того средства. Это теперь имеет O (n) время выполнения (в противоположность O (2^n) для алгоритма без memoization).

Примечание: memoization средство предоставило использованию цепочку закрытий для поиска предыдущих вызовов. В худшем случае случитесь, это может быть O (n). В этом случае, однако, требуемые значения всегда наверху цепочки, удостоверяясь O (1) поиск.

Как другие плакаты указали, , memoization является стандартным способом обменять память на скорость, вот некоторый псевдо код для реализации memoization для любой функции (если функция не имеет никаких побочных эффектов):

Начальная буква функционируют код:

 function (parameters)
      body (with recursive calls to calculate result)
      return result

Это должно быть преобразовано к

 function (parameters)
      key = serialized parameters to string
      if (cache[key] does not exist)  {
           body (with recursive calls to calculate result)
           cache[key] = result
      }
      return cache[key]

проблема с этим кодом состоит в том, что он генерирует ошибку переполнения стека для любого числа, больше, чем 15 (в большинстве компьютеров).

Действительно? Какой компьютер Вы используете? Требуется много времени в 44, но стек не переполняется. На самом деле Ваша попытка получить значение, больше, чем целое число, может содержать (~4 миллиарда неподписанного, ~2 миллиарда, со знаком), прежде чем стек будет идти в по потоку (Fibbonaci (46)).

Это работало бы на то, что Вы хотите сделать хотя (работает злой быстрый)

class Program
{
    public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
    static void Main(string[] args)
    {
        Console.WriteLine(Fibbonacci(46).ToString());
        Console.ReadLine();
    }

    public static int Fibbonacci(int number)
    {
        if (number == 1 || number == 0)
        {
            return 1;
        }

        var minus2 = number - 2;
        var minus1 = number - 1;

        if (!Items.ContainsKey(minus2))
        {
            Items.Add(minus2, Fibbonacci(minus2));
        }

        if (!Items.ContainsKey(minus1))
        {
            Items.Add(minus1, Fibbonacci(minus1));
        }

        return (Items[minus2] + Items[minus1]);
    }
}

Mathematica имеет особенно гладкий способ сделать memoization, полагаясь на то, что хеши и вызовы функции используют тот же синтаксис:

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

Вот именно. Это кэширует (memoizes) выдумку [0] и выдумку [1] от летучей мыши и кэшей остальные по мере необходимости. Правила для вызовов функции сопоставления с образцом таковы, что это всегда использует более определенное определение перед более общим определением.

Другие ответили на Ваш вопрос хорошо и точно - Вы ищете memoization.

Языки программирования с оптимизация последнего вызова (главным образом функциональные языки) может сделать определенные случаи рекурсии без переполнения стека. Это непосредственно не относится к Вашему определению Fibonacci, хотя существуют приемы..

формулировка Вашего вопроса заставила меня думать об интересной идее.. Предотвращение переполнения стека чистой рекурсивной функции, только храня подмножество стековых фреймов и восстанавливая при необходимости.. Только действительно полезный в нескольких случаях. Если Ваш алгоритм только условно полагается на контекст в противоположность возврату, и/или Вы оптимизируете для памяти не скорость.

Еще один превосходный ресурс для программистов C# для рекурсии, partials, приправления карри, memoization, и их рода, является блогом Wes Dyer, хотя он не отправил в некоторое время. Он объясняет memoization хорошо с основательными примерами кода здесь: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx

@ESRogs:

std::map поиск O (журнал n), который заставляет его замедлиться здесь. Лучше используйте вектор.

vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);

unsigned int fib(unsigned int n) {
    if (fib_cache.size() <= n)
        fib_cache.push_back(fib(n - 1) + fib(n - 2));

    return fib_cache[n];
}