偶数斐波那契数相加
Addition of Even Fibonacci Numbers
我正在尝试解决 Project Euler 上的 2nd problem，我必须打印 400 万以下所有偶数斐波那契数的总和。我正在使用以下代码，但程序没有返回任何值。当我用 10 之类的小数替换 4000000 时，我得到了总和。这是否意味着我的程序耗时太长？我做错了什么？
#include <iostream>
using namespace std;
int fibonacci(int i) {
if (i == 2)
return 2;
else if (i == 1)
return 1;
else return fibonacci(i - 1) + fibonacci(i - 2);
}
int main() {
int currentTerm, sum = 0;
for (int i = 1; i <= 10; i++) {
currentTerm = fibonacci(i);
if (currentTerm % 2 == 0)
sum += currentTerm;
}
cout << sum;
return 0;
}
欢迎来到 Stack Overflow :)
我只在循环中修改了您的代码，并使您的斐波那契实现保持不变。我已经在 Project Euler 上验证了代码的答案。代码可以在下面找到，希望我的评论能帮助你更好地理解它。
我改变的三件事是：
1) 您试图一直寻找一个数字，直到第 4,000,000 次迭代，而不是寻找小于 4,000,000 的数字。这意味着您的程序可能会疯狂地尝试添加一个非常大的数字（我们不需要）<- 这可能就是您的程序放弃的原因
2) 我改进了对偶数的检查；我们知道斐波那契数列是奇奇偶数、奇奇偶数，所以我们真的只需要将每三个数字添加到我们的总和而不是检查数字本身是否为偶数 <- 模运算大量使用非常昂贵
3) 我添加了两行用 couts 注释掉的行，它们可以帮助您调试和解决输出问题
还有一个 link 关于使用动态规划更有效地解决问题，如果有人需要的话。
祝你好运！
#include <iostream>
using namespace std;
int fibonacci(int i) {
if (i == 2)
return 2;
else if (i == 1)
return 1;
else return fibonacci(i - 1) + fibonacci(i - 2);
}
int main() {
// need to add the sum of all even fib numbers under a particular sum
int max_fib_number = 4000000;
int currentTerm, sum = 0;
currentTerm = 1;
int i = 1;
// we do not need a for loop, we need a while loop
// this is so we can detect when our current number exceeds fib
while(currentTerm < max_fib_number) {
currentTerm = fibonacci(i);
//cout << currentTerm <<"\n";
// notice we check here if currentTerm is a valid number to add
if (currentTerm < max_fib_number) {
//cout << "i:" << i<< "\n";
// we only want every third term
// this is because 1 1 2, 3 5 8, 13 21 34,
// pattern caused by (odd+odd=even, odd+even=odd)
// we also add 1 because we start with the 0th term
if ((i+1) % 3 == 0)
sum += currentTerm;
}
i++;
}
cout << sum;
return 0;
}
您可以在计算中使用 Binet 公式 - 这将允许您放弃缓慢的递归算法，另一种选择可能是用于计算斐波那契数的非递归算法。 https://en.wikipedia.org/wiki/Jacques_Philippe_Marie_Binet。这是一个使用比奈公式的例子，它会比递归算法快很多，因为它不会重新计算所有以前的数字。
#include <iostream>
#include <math.h>
using namespace std;
int main(){
double num{},a{(1+sqrt(5))/2},b{(1-sqrt(5))/2},c{sqrt(5)};
int sum{};
for (auto i=1;i<30;++i){
num=(pow(a,i)-pow(b,i))/c;
if (static_cast<int>(num)%2==0)
sum+=static_cast<int>(num);
}
cout<<sum;
return 0;
}
变体 2
int fib_sum(int n)
{
int sum{};
if (n <= 2) return 0;
std::vector<int> dp(n + 1);
dp[1] = 1; dp[2] = 1;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
if(dp[i]%2==0)
sum+=dp[i];
}
return sum;
}
这是您修改后的代码，可以为项目欧拉问题生成正确的输出。
#include <iostream>
using namespace std;
int fibonacci(int i) {
if (i == 2)
return 2;
else if (i == 1)
return 1;
else return fibonacci(i - 1) + fibonacci(i - 2);
}
int main() {
int currentsum, sum = 0;
for (int i = 1; i <= 100; i++) {
currentsum = fibonacci(i);
//here's where you doing wrong
if(sum >= 4000000) break; //break when sum reaches 4mil
if(currentsum %2 == 0) sum+=currentsum; // add when even-valued occurs in the currentsum
}
cout << sum;
return 0;
}
Output 4613732
这是我的代码，其中包含 while 循环，直到总和中出现 400 万，并附有一些解释。
#include <iostream>
using namespace std;
int main()
{
unsigned long long int a,b,c , totalsum;
totalsum = 0;
a = 1; // 1st index digit in fib series(according to question)
b = 2; // 2nd index digit in fib series(according to question)
totalsum+=2; // because 2 is an even-valued term in the series
while(totalsum < 4000000){ //loop until 4million
c = a+b; // add previous two nums
a = b;
b = c;
if(c&1) continue; // if its odd ignore and if its an even-valued term add to totalsum
else totalsum+=c;
}
cout << totalsum;
return 0;
}
对于投反对票的人，您实际上可以说出代码中的错误，而不是投反对票 https://projecteuler.net/problem=2 的实际答案是上述代码的输出 4613732 , 竞争性编程本身是关于你能多快解决问题而不是干净的代码。
如果您需要多个斐波那契数，尤其是如果您需要所有数，请不要使用递归方法，而是使用迭代：
var prev=0;
var curr=1;
var sum=0;
while(curr<4000000){
if(curr%2==0)
sum+=curr;
var temp=prev;
prev=curr;
curr+=temp;
}
console.log(sum);
代码段是JavaScript（所以这里可以运行），但是如果你把var-s变成int-s，那就是C-够了。
但实际问题是循环：你不需要计算第一个
n (4000000) 斐波那契数（会导致各种溢出），但小于4000000的斐波那契数.
Problem 2 项目 Euler 问（强调我的）
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
正在做
for (int i = 1; i <= 4000000; i++)
{
currentTerm = fibonacci(i);
// ...
}
您正在尝试计算直到第 4,000,000 个斐波那契数，这是一个非常大的野兽，而您应该在第 33[=] 附近停下来44=] 代替。
其他答案已经指出了递归方法的低效性，但让我在讨论中添加一些数字，使用你程序的这个稍微修改过的版本
#include <iostream>
#include <iomanip>
int k = 0;
// From https://oeis.org/A000045 The fibonacci numbers are defined by the
// recurrence relation F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
// In the project Euler question the sequence starts with 1, 2, 3, 5, ...
// So in the following I'll consider F(1) = 1 and F(2) = 2 as The OP does.
long long fibonacci(long long i)
{
++k;
if (i > 2)
return fibonacci(i - 1) + fibonacci(i - 2);
else
return i;
}
int main()
{
using std::cout;
using std::setw;
const long limit = 4'000'000;
long sum = 0;
cout << " i F(i) sum calls\n"
"-----------------------------------\n";
for (int i = 1; ; ++i)
{
long long F_i = fibonacci(i);
if ( F_i > limit ) // <-- corrected end condition
break;
if (F_i % 2 == 0)
{
sum += F_i;
cout << setw(3) << i << setw(10) << F_i
<< setw(10) << sum << setw(11) << k << '\n';
}
}
cout << "\nThe sum of all even Fibonacci numbers less then "
<< limit << " is " << sum << '\n';
return 0;
}
一旦执行（live here），您可以注意到递归函数已被调用超过 10,000,000 次，计算到 33第个斐波那契数.
这根本不是正确的方法。记忆化可能会有所帮助，here 有一个快速基准将递归函数与记忆化技术的玩具实现进行比较，它由您看不到的直方图表示。因为比其他的短30万倍
不过，这不是 "correct" 或 "natural" 处理此问题的方法。正如其他答案中所述，您可以简单地按顺序计算每个数字，给出之前的数字。 Enthus3d 还注意到序列中的模式：奇数、奇数、偶数、奇数、奇数、偶数、...
我们可以更进一步，直接计算只偶数项：
#include <iostream>
int main()
{
const long limit = 4'000'000;
// In the linked question the sequence starts as 1, 2, 3, 5, 8, ...
long long F_0 = 2, F_3 = 8, sum = F_0 + F_3;
for (;;)
{
// F(n+2) = F(n+1) + F(n)
// F(n+3) = F(n+2) + F(n+1) = F(n+1) + F(n) + F(n+1) = 2F(n+1) + F(n)
// F(n+6) = F(n+5) + F(n+4) = F(n+4) + F(n+3) + F(n+3) + F(n+2)
// = 2F(n+3) + F(n+4) + F(n+2) = 3F(n+3) + 2F(n+2)
// = 3F(n+3) + 2F(n+1) + 2F(n) = 3F(n+3) + F(n+3) - F(n) + 2F(n)
long long F_6 = 4 * F_3 + F_0;
if ( F_6 > limit )
break;
sum += F_6;
F_0 = F_3;
F_3 = F_6;
}
std::cout << sum << '\n'; // --> 4613732
return 0;
}
直播here.
如果你想要一点魔法，你还可以建立在每个第 3 个斐波那契数都是偶数的基础上，在 "even+odd=>odd"、"odd+even=>odd" 和仅 [=52= 的基础上]:
0 1 1 2 3 5 8...
E O O E O O E
^ O+O
^ E+O
^ O+E
^ O+O
var prev=1;
var curr=2;
var sum=0;
while(curr<4000000){
sum+=curr;
console.log("elem: "+curr,"sum: "+sum);
for(var i=0;i<3;i++){
var temp=prev;
prev=curr;
curr+=temp;
}
}
如果问题只是标题，偶数斐波那契数的加法（比方说，其中的 n），纯数学可以完成这项工作，使用 Binet 的公式（@Silerus 中描述的 answer) and the fact that it is an (a^n-b^n)/c thing, where a^n and b^n are geometric sequences, every 3rd of them also being a geometric sequence, (a^3)^n, and the sum of geometric sequences 有一个简单的封闭形式（如果级数是 a*r^n，总和是 a*(1-r^n)/(1-r)）。
将所有内容放在一起：
// convenience for JS->C
var pow=Math.pow;
var sqrt=Math.sqrt;
var round=Math.round;
var s5=sqrt(5);
var a=(1+s5)/2;
var a3=pow(a,3);
var b=(1-s5)/2;
var b3=pow(b,3);
for(var i=0;i<12;i++){
var nthEvenFib=round((pow(a3,i)-pow(b3,i))/s5);
var sumEvenFibs=round(((1-pow(a3,i+1))/(1-a3)-(1-pow(b3,i+1))/(1-b3))/s5);
console.log("elem: "+nthEvenFib,"sum: "+sumEvenFibs);
}
同样，如果第一个片段中的 var-s 被一些 C-type、int-s 替换，并且大部分 double-s 在后一个中（循环变量 i 当然可以是一个简单的 int）。
您可以使用 constexpre 函数对所有偶数斐波那契数和求和使用编译时预计算，从而大大加快速度。
对 Binets 公式的简短检查表明，回旋处 30 个偶数斐波那契数将适合 64 位无符号值。
30 个数字真的可以很容易地计算出来，而不需要编译器做任何努力。因此，我们可以创建一个包含所有需要值的编译时间 constexpr std::array。
因此，您将拥有零运行时开销，使您的编程速度极快。我不确定是否有更快的解决方案。请看：
#include <iostream>
#include <array>
#include <algorithm>
#include <iterator>
// ----------------------------------------------------------------------
// All the following wioll be done during compile time
// Constexpr function to calculate the nth even Fibonacci number
constexpr unsigned long long getEvenFibonacciNumber(size_t index) {
// Initialize first two even numbers
unsigned long long f1{ 0 }, f2{ 2 };
// calculating Fibonacci value
while (--index) {
// get next even value of Fibonacci sequence
unsigned long long f3 = 4 * f2 + f1;
// Move to next even number
f1 = f2;
f2 = f3;
}
return f2;
}
// Get nth even sum of Fibonacci numbers
constexpr unsigned long long getSumForEvenFibonacci(size_t index) {
// Initialize first two even prime numbers
// and their sum
unsigned long long f1{ 0 }, f2{ 2 }, sum{ 2 };
// calculating sum of even Fibonacci value
while (--index) {
// get next even value of Fibonacci sequence
unsigned long long f3 = 4 * f2 + f1;
// Move to next even number and update sum
f1 = f2;
f2 = f3;
sum += f2;
}
return sum;
}
// Here we will store ven Fibonacci numbers and their respective sums
struct SumOfEvenFib {
unsigned long long fibNum;
unsigned long long sum;
friend bool operator < (const unsigned long long& v, const SumOfEvenFib& f) { return v < f.fibNum; }
};
// We will automatically build an array of even numbers and sums during compile time
// Generate a std::array with n elements taht consist of const char *, pointing to Textx...Texty
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
return std::array<SumOfEvenFib, sizeof...(ManyIndices)>{ { {getEvenFibonacciNumber(ManyIndices + 1), getSumForEvenFibonacci(ManyIndices + 1)}...}};
};
// You may check with Ninets formula
constexpr size_t MaxIndexFor64BitValue = 30;
// Generate the reuired number of texts
constexpr auto generateArray()noexcept {
return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}
// This is an constexpr array of even Fibonacci numbers and its sums
constexpr auto SOEF = generateArray();
// ----------------------------------------------------------------------
int main() {
// Show sum for 4000000
std::cout << std::prev(std::upper_bound(SOEF.begin(), SOEF.end(), 4000000))->sum << '\n';
// Show all even numbers and their corresponding sums
for (const auto& [even, sum] : SOEF) std::cout << even << " --> " << sum << '\n';
return 0;
}
已使用 MSVC 19、clang 11 和 gcc10 进行测试
使用 C++17 编译
我正在尝试解决 Project Euler 上的 2nd problem，我必须打印 400 万以下所有偶数斐波那契数的总和。我正在使用以下代码，但程序没有返回任何值。当我用 10 之类的小数替换 4000000 时，我得到了总和。这是否意味着我的程序耗时太长？我做错了什么？
#include <iostream>
using namespace std;
int fibonacci(int i) {
if (i == 2)
return 2;
else if (i == 1)
return 1;
else return fibonacci(i - 1) + fibonacci(i - 2);
}
int main() {
int currentTerm, sum = 0;
for (int i = 1; i <= 10; i++) {
currentTerm = fibonacci(i);
if (currentTerm % 2 == 0)
sum += currentTerm;
}
cout << sum;
return 0;
}
欢迎来到 Stack Overflow :)
我只在循环中修改了您的代码，并使您的斐波那契实现保持不变。我已经在 Project Euler 上验证了代码的答案。代码可以在下面找到，希望我的评论能帮助你更好地理解它。
我改变的三件事是：
1) 您试图一直寻找一个数字，直到第 4,000,000 次迭代，而不是寻找小于 4,000,000 的数字。这意味着您的程序可能会疯狂地尝试添加一个非常大的数字（我们不需要）<- 这可能就是您的程序放弃的原因
2) 我改进了对偶数的检查；我们知道斐波那契数列是奇奇偶数、奇奇偶数，所以我们真的只需要将每三个数字添加到我们的总和而不是检查数字本身是否为偶数 <- 模运算大量使用非常昂贵
3) 我添加了两行用 couts 注释掉的行，它们可以帮助您调试和解决输出问题
还有一个 link
祝你好运！
#include <iostream>
using namespace std;
int fibonacci(int i) {
if (i == 2)
return 2;
else if (i == 1)
return 1;
else return fibonacci(i - 1) + fibonacci(i - 2);
}
int main() {
// need to add the sum of all even fib numbers under a particular sum
int max_fib_number = 4000000;
int currentTerm, sum = 0;
currentTerm = 1;
int i = 1;
// we do not need a for loop, we need a while loop
// this is so we can detect when our current number exceeds fib
while(currentTerm < max_fib_number) {
currentTerm = fibonacci(i);
//cout << currentTerm <<"\n";
// notice we check here if currentTerm is a valid number to add
if (currentTerm < max_fib_number) {
//cout << "i:" << i<< "\n";
// we only want every third term
// this is because 1 1 2, 3 5 8, 13 21 34,
// pattern caused by (odd+odd=even, odd+even=odd)
// we also add 1 because we start with the 0th term
if ((i+1) % 3 == 0)
sum += currentTerm;
}
i++;
}
cout << sum;
return 0;
}
您可以在计算中使用 Binet 公式 - 这将允许您放弃缓慢的递归算法，另一种选择可能是用于计算斐波那契数的非递归算法。 https://en.wikipedia.org/wiki/Jacques_Philippe_Marie_Binet。这是一个使用比奈公式的例子，它会比递归算法快很多，因为它不会重新计算所有以前的数字。
#include <iostream>
#include <math.h>
using namespace std;
int main(){
double num{},a{(1+sqrt(5))/2},b{(1-sqrt(5))/2},c{sqrt(5)};
int sum{};
for (auto i=1;i<30;++i){
num=(pow(a,i)-pow(b,i))/c;
if (static_cast<int>(num)%2==0)
sum+=static_cast<int>(num);
}
cout<<sum;
return 0;
}
变体 2
int fib_sum(int n)
{
int sum{};
if (n <= 2) return 0;
std::vector<int> dp(n + 1);
dp[1] = 1; dp[2] = 1;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
if(dp[i]%2==0)
sum+=dp[i];
}
return sum;
}
这是您修改后的代码，可以为项目欧拉问题生成正确的输出。
#include <iostream>
using namespace std;
int fibonacci(int i) {
if (i == 2)
return 2;
else if (i == 1)
return 1;
else return fibonacci(i - 1) + fibonacci(i - 2);
}
int main() {
int currentsum, sum = 0;
for (int i = 1; i <= 100; i++) {
currentsum = fibonacci(i);
//here's where you doing wrong
if(sum >= 4000000) break; //break when sum reaches 4mil
if(currentsum %2 == 0) sum+=currentsum; // add when even-valued occurs in the currentsum
}
cout << sum;
return 0;
}
Output 4613732
这是我的代码，其中包含 while 循环，直到总和中出现 400 万，并附有一些解释。
#include <iostream>
using namespace std;
int main()
{
unsigned long long int a,b,c , totalsum;
totalsum = 0;
a = 1; // 1st index digit in fib series(according to question)
b = 2; // 2nd index digit in fib series(according to question)
totalsum+=2; // because 2 is an even-valued term in the series
while(totalsum < 4000000){ //loop until 4million
c = a+b; // add previous two nums
a = b;
b = c;
if(c&1) continue; // if its odd ignore and if its an even-valued term add to totalsum
else totalsum+=c;
}
cout << totalsum;
return 0;
}
对于投反对票的人，您实际上可以说出代码中的错误，而不是投反对票 https://projecteuler.net/problem=2 的实际答案是上述代码的输出 4613732 , 竞争性编程本身是关于你能多快解决问题而不是干净的代码。
如果您需要多个斐波那契数，尤其是如果您需要所有数，请不要使用递归方法，而是使用迭代：
var prev=0;
var curr=1;
var sum=0;
while(curr<4000000){
if(curr%2==0)
sum+=curr;
var temp=prev;
prev=curr;
curr+=temp;
}
console.log(sum);
代码段是JavaScript（所以这里可以运行），但是如果你把var-s变成int-s，那就是C-够了。
但实际问题是循环：你不需要计算第一个 n (4000000) 斐波那契数（会导致各种溢出），但小于4000000的斐波那契数.
Problem 2 项目 Euler 问（强调我的）
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
正在做
for (int i = 1; i <= 4000000; i++)
{
currentTerm = fibonacci(i);
// ...
}
您正在尝试计算直到第 4,000,000 个斐波那契数，这是一个非常大的野兽，而您应该在第 33[=] 附近停下来44=] 代替。
其他答案已经指出了递归方法的低效性，但让我在讨论中添加一些数字，使用你程序的这个稍微修改过的版本
#include <iostream>
#include <iomanip>
int k = 0;
// From https://oeis.org/A000045 The fibonacci numbers are defined by the
// recurrence relation F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
// In the project Euler question the sequence starts with 1, 2, 3, 5, ...
// So in the following I'll consider F(1) = 1 and F(2) = 2 as The OP does.
long long fibonacci(long long i)
{
++k;
if (i > 2)
return fibonacci(i - 1) + fibonacci(i - 2);
else
return i;
}
int main()
{
using std::cout;
using std::setw;
const long limit = 4'000'000;
long sum = 0;
cout << " i F(i) sum calls\n"
"-----------------------------------\n";
for (int i = 1; ; ++i)
{
long long F_i = fibonacci(i);
if ( F_i > limit ) // <-- corrected end condition
break;
if (F_i % 2 == 0)
{
sum += F_i;
cout << setw(3) << i << setw(10) << F_i
<< setw(10) << sum << setw(11) << k << '\n';
}
}
cout << "\nThe sum of all even Fibonacci numbers less then "
<< limit << " is " << sum << '\n';
return 0;
}
一旦执行（live here），您可以注意到递归函数已被调用超过 10,000,000 次，计算到 33第个斐波那契数.
这根本不是正确的方法。记忆化可能会有所帮助，here 有一个快速基准将递归函数与记忆化技术的玩具实现进行比较，它由您看不到的直方图表示。因为比其他的短30万倍
不过，这不是 "correct" 或 "natural" 处理此问题的方法。正如其他答案中所述，您可以简单地按顺序计算每个数字，给出之前的数字。 Enthus3d 还注意到序列中的模式：奇数、奇数、偶数、奇数、奇数、偶数、...
我们可以更进一步，直接计算只偶数项：
#include <iostream>
int main()
{
const long limit = 4'000'000;
// In the linked question the sequence starts as 1, 2, 3, 5, 8, ...
long long F_0 = 2, F_3 = 8, sum = F_0 + F_3;
for (;;)
{
// F(n+2) = F(n+1) + F(n)
// F(n+3) = F(n+2) + F(n+1) = F(n+1) + F(n) + F(n+1) = 2F(n+1) + F(n)
// F(n+6) = F(n+5) + F(n+4) = F(n+4) + F(n+3) + F(n+3) + F(n+2)
// = 2F(n+3) + F(n+4) + F(n+2) = 3F(n+3) + 2F(n+2)
// = 3F(n+3) + 2F(n+1) + 2F(n) = 3F(n+3) + F(n+3) - F(n) + 2F(n)
long long F_6 = 4 * F_3 + F_0;
if ( F_6 > limit )
break;
sum += F_6;
F_0 = F_3;
F_3 = F_6;
}
std::cout << sum << '\n'; // --> 4613732
return 0;
}
直播here.
如果你想要一点魔法，你还可以建立在每个第 3 个斐波那契数都是偶数的基础上，在 "even+odd=>odd"、"odd+even=>odd" 和仅 [=52= 的基础上]:
0 1 1 2 3 5 8...
E O O E O O E
^ O+O
^ E+O
^ O+E
^ O+O
var prev=1;
var curr=2;
var sum=0;
while(curr<4000000){
sum+=curr;
console.log("elem: "+curr,"sum: "+sum);
for(var i=0;i<3;i++){
var temp=prev;
prev=curr;
curr+=temp;
}
}
如果问题只是标题，偶数斐波那契数的加法（比方说，其中的 n），纯数学可以完成这项工作，使用 Binet 的公式（@Silerus 中描述的 answer) and the fact that it is an
(a^n-b^n)/c thing, where a^n and b^n are geometric sequences, every 3rd of them also being a geometric sequence, (a^3)^n, and the sum of geometric sequences 有一个简单的封闭形式（如果级数是 a*r^n，总和是 a*(1-r^n)/(1-r)）。
将所有内容放在一起：
// convenience for JS->C
var pow=Math.pow;
var sqrt=Math.sqrt;
var round=Math.round;
var s5=sqrt(5);
var a=(1+s5)/2;
var a3=pow(a,3);
var b=(1-s5)/2;
var b3=pow(b,3);
for(var i=0;i<12;i++){
var nthEvenFib=round((pow(a3,i)-pow(b3,i))/s5);
var sumEvenFibs=round(((1-pow(a3,i+1))/(1-a3)-(1-pow(b3,i+1))/(1-b3))/s5);
console.log("elem: "+nthEvenFib,"sum: "+sumEvenFibs);
}
同样，如果第一个片段中的 var-s 被一些 C-type、int-s 替换，并且大部分 double-s 在后一个中（循环变量 i 当然可以是一个简单的 int）。
您可以使用 constexpre 函数对所有偶数斐波那契数和求和使用编译时预计算，从而大大加快速度。
对 Binets 公式的简短检查表明，回旋处 30 个偶数斐波那契数将适合 64 位无符号值。
30 个数字真的可以很容易地计算出来，而不需要编译器做任何努力。因此，我们可以创建一个包含所有需要值的编译时间 constexpr std::array。
因此，您将拥有零运行时开销，使您的编程速度极快。我不确定是否有更快的解决方案。请看：
#include <iostream>
#include <array>
#include <algorithm>
#include <iterator>
// ----------------------------------------------------------------------
// All the following wioll be done during compile time
// Constexpr function to calculate the nth even Fibonacci number
constexpr unsigned long long getEvenFibonacciNumber(size_t index) {
// Initialize first two even numbers
unsigned long long f1{ 0 }, f2{ 2 };
// calculating Fibonacci value
while (--index) {
// get next even value of Fibonacci sequence
unsigned long long f3 = 4 * f2 + f1;
// Move to next even number
f1 = f2;
f2 = f3;
}
return f2;
}
// Get nth even sum of Fibonacci numbers
constexpr unsigned long long getSumForEvenFibonacci(size_t index) {
// Initialize first two even prime numbers
// and their sum
unsigned long long f1{ 0 }, f2{ 2 }, sum{ 2 };
// calculating sum of even Fibonacci value
while (--index) {
// get next even value of Fibonacci sequence
unsigned long long f3 = 4 * f2 + f1;
// Move to next even number and update sum
f1 = f2;
f2 = f3;
sum += f2;
}
return sum;
}
// Here we will store ven Fibonacci numbers and their respective sums
struct SumOfEvenFib {
unsigned long long fibNum;
unsigned long long sum;
friend bool operator < (const unsigned long long& v, const SumOfEvenFib& f) { return v < f.fibNum; }
};
// We will automatically build an array of even numbers and sums during compile time
// Generate a std::array with n elements taht consist of const char *, pointing to Textx...Texty
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
return std::array<SumOfEvenFib, sizeof...(ManyIndices)>{ { {getEvenFibonacciNumber(ManyIndices + 1), getSumForEvenFibonacci(ManyIndices + 1)}...}};
};
// You may check with Ninets formula
constexpr size_t MaxIndexFor64BitValue = 30;
// Generate the reuired number of texts
constexpr auto generateArray()noexcept {
return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}
// This is an constexpr array of even Fibonacci numbers and its sums
constexpr auto SOEF = generateArray();
// ----------------------------------------------------------------------
int main() {
// Show sum for 4000000
std::cout << std::prev(std::upper_bound(SOEF.begin(), SOEF.end(), 4000000))->sum << '\n';
// Show all even numbers and their corresponding sums
for (const auto& [even, sum] : SOEF) std::cout << even << " --> " << sum << '\n';
return 0;
}
已使用 MSVC 19、clang 11 和 gcc10 进行测试
使用 C++17 编译