生成Fibonacci数直到达到某个值的STL算法

Question

下面的代码将使用adjacent_difference算法生成前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

但是，如果我想继续生成Fibonacci数，直到达到一个值为4,000,000的斐波纳契数(例如，不是第四个第一百万个斐波纳契数，而是数值恰好是400万(或更高)的第N个斐波纳契数)，该怎么办？

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

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

Answer 1

使用find_if和boost迭代器库提供的一些帮助：

#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算法在这里可能有用，可以将结果推回向量，但您需要编写自己的算法。

Answer 2

标准算法是用来提取编程实践中常见的实现的。这使您更容易理解代码，也使读者更容易理解代码。使用内置算法将斐波纳契数字累加到给定的值对于您和读您的代码的人来说都是过份的。

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

void fibUpTo(int limit) {
  int a, b, c;
  a = b = 1;
  while (a < limit) {
    cout << a << endl;
    c = a + b; 
    a = b;
    b = c;
  }
}

Answer 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“循环即可。