时间戳

首页 > 解决方案 > 更快地生成递归序列（类似于斐波那契）

c++ - 更快地生成递归序列（类似于斐波那契）

问题描述

嗨，必须计算一个系列的第 n 项，因为 n 非常大，并且必须尽可能快地完成。

该系列由以下函数定义：

f(0) = 1
f(1) = 1
f(2n) = f(n)
f(2n+1) = f(n) + f(n-1)

我知道我必须使用记忆。我做了这段代码，但问题是大 n 值会导致分段错误。我想尝试做一个 2 值数组版本（就像这里的回复之一中描述的那样），但我没有找到正确的解决方案。

uint64_t f(uint64_t n)
{
    uint64_t a[n+2];
    uint64_t i;

    a[0] = 1;
    a[1] = 1;
 
    for(i = 2; i <= n; i++)
    {
        if (i % 2 == 0)
        { 
            a[i] =  a[i / 2];
        }
        else
        {
            a[i] =  a[i / 2] + a[(i / 2) - 1];
        }
    }
    return a[n];
};

标签： c++seriesfibonacci

解决方案

我认为递归在这里是正确的想法，因为您只需要最后一个值，它实际上并不依赖于那么多先前的值。最好的情况是，如果您的输入是 2 的幂，例如 2^n。然后你只需要 n 个输入的值。尽管在其他情况下性能更差，但它仍然应该比实际计算所有前面的值要好得多。

编辑：使用评论中要求的特定数字和一个计数器变量来显示所需的评估数量：

EDIT2：当然可以（以及真正的性能提升！）将递归与缓存中间结果结合起来，正如@Bob__ 在他下面的评论中所展示的那样，谢谢！对于未来的读者，这里有递归+缓存的完整版本。使用给定的输入，缓存将 g 所需的评估数量从没有缓存的 12875760616 显着减少到只有 164 的缓存。

#include <iostream>
#include <map>
#include <stdexcept>

static unsigned long count = 0;
static std::map<unsigned long, unsigned long> cache;

static unsigned long g(unsigned long n) {
  auto it = cache.find(n);
  if (it != cache.end()) {
    return it->second;
  }

  ++count;
  if (count == 0) {
    std::cout << "Integer overflow! Aborting!";
    throw std::overflow_error("overflow error!");
  }

  if (n == 0 or n == 1) {
    return 1;
  } else if (n % 2 == 0) {
    auto a = g(n / 2);
    cache.insert({n, a});
    return a;
  } else {
    auto a = g((n - 1) / 2) + g((n - 3) / 2);
    cache.insert({n, a});
    return a;
  }
}

int main() {
  try {
    std::cout << "result: " << g(123456789012345678) << std::endl;
    std::cout << "number of used values: " << count << std::endl;
  } catch (std::exception &e) {
    std::cout << "An error occured:\n" << e.what() << std::endl;
  }
}

推荐阅读