3

以下代码将使用相邻差值算法生成前 10 个斐波那契数：

v = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
std::adjacent_difference(v.begin(), v.end() - 1, v.begin() + 1, std::plus<int>());

for (auto n : v) {
    std::cout << n << ' ';
}
std::cout << '\n';

输出：1 1 2 3 5 8 13 21 34 55

但是，如果我想继续生成斐波那契数，直到达到（例如）4,000,000 的值（例如，不是第四百万个斐波那契数，而是值恰好是 400 万（或更大）的第 N 个斐波那契数），该怎么办。

显然，带有 push_back 的 do while 循环可以完成这项工作，但我想知道是否可以将 STL 算法与 back_inserter 和 lambda 函数结合起来指定重复直到条件（例如，在达到或超过 400 万个值后停止插入)?

我看到的问题是大多数算法都在一个范围内运行，并且提前我们不知道需要多少元素才能产生 400 万的斐波那契数。

4

3 回答 3

5

标准算法用于提取编程实践中常见的实现。这使您更容易理解代码和读者理解它。使用内置算法将斐波那契数累积到给定值对您和任何阅读您的代码的人来说都是一种过度杀伤力。

为你的用例编写一个“愚蠢”的解决方案真的很容易，而且更容易维护。例如：

void fibUpTo(int limit) {
  int a, b, c;
  a = b = 1;
  while (a < limit) {
    cout << a << endl;
    c = a + b; 
    a = b;
    b = c;
  }
}
于 2013-10-15T12:43:18.420 回答
3 
int my_plus(int a, int b)
{
    int result = a + b;
    if (result >= 4000000)
        throw result;
    return result;
}

try {
    adjacent_difference(v.begin(), v.end() - 1, v.begin() + 1, my_plus);
} catch (int final) {
    cout << final << endl;
}

这就是我认为的“愚蠢的黑客”，但我认为它会起作用。如果您想稍微美化一下，请创建一个异常类来保存最终结果，而不是抛出一个原始整数。并将阈值作为模板参数。

但实际上，不要这样做，因为这是一个愚蠢的黑客：只需使用你提到的“for”循环。

于 2013-10-15T12:40:20.180 回答
2

在find_ifboost 迭代器库的帮助下：

#include <boost/iterator/function_input_iterator.hpp>
#include <algorithm>
#include <climits>

struct fibonacci_generator {
    typedef int result_type;
    fibonacci_generator() : n(0) {}
    // dummy generator
    // put the code to generate fibonacci
    // sequence here
    int operator()() { return n++; }
private:
    int n;
};

int main()
{
    fibonacci_generator g;
    int i = *std::find_if(
        make_function_input_iterator(g, boost::infinite()),
        make_function_input_iterator(g, boost::infinite()),
        [](int i) { return i > 1000000; });
}

一种copy_until算法在这里可能有用，可以将结果推回向量，但您需要自己编写。

于 2013-10-15T12:47:20.410 回答