3

从 1 和 2 开始，斐波那契数列的前 10 项将是：

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

求序列中所有不超过 400 万的偶数项之和。

现在，我有了如何做到这一点的想法。但我对保存如此大数据的数据类型感到困惑。我得到了奇怪的结果int。:(

更多：它的 Project Euler 第二个问题。但我无法得到它。我得到了疯狂的价值观作为答案。有人可以发布理想的程序吗？

编辑：这是我写的只是将斐波那契打印到屏幕上。基本款。即使我给出 100 作为限制，我的变量也会变得疯狂。我的代码错了吗？

// Simple Program to print Fibonacci series in Console
#include <stdio.h>
int main() {
    int x=1,y=2,sum=0,limit=0,i=0,temp=0;
    printf("Enter Limit:");
    scanf("%d",&limit);

    if(limit==1)
        printf("%d",x);
    else if(limit>1) {
        printf("%d %d",x,y);
        if (limit>2) {
            while (i<limit-2) {
                temp=y;
                sum=x+y;
                x=temp;
                y=sum;
                printf(" %d",sum);
                i++;
            }
        }
    }      

    printf("\n");
    return 0;
}

已解决：实际上，我自己设法得到了解决方案。这是我的程序。有用。

#include <stdio.h>
int main() {
    int x=1,y=2,sum,limit;     //Here value of first 2 terms have been initialized as 1 and 2
    int evensum=2;             //Since in calculation, we omit 2 which is an even number
    printf("Enter Limit: ");   //Enter limit as 4000000 (4million) to get desired result
    scanf("%d",&limit);
    while( (x+y)<limit ) {
        sum=x+y;
        x=y;
        y=sum;
        if (sum%2==0)
            evensum+=sum;
    }
    printf("%d \n",evensum);
    return 0;
}
4

14 回答 14

6

由于您只想要最多四百万，因此这可能int不是您的问题。

您的程序很可能有错误并且数据存储很好，因此您应该在较小的值上测试您的程序。例如，很明显，前三个偶数项的总和是 44（提示：每第三个项是偶数），所以如果你以 50 的上限运行程序，那么你应该立即得到 44。继续运行小型测试用例，以获得对大型测试用例的信心。

于 2009-10-29T15:31:10.750 回答
3

为安全起见，请使用“长”数据类型；C 标准要求至少持有 40 亿，但在大多数机器上，'int' 也将持有 40 亿。

enum { MAX_VALUE = 4000000 };
int sum  = 0;
int f_n0 = 0;
int f_n1 = 1;
int f_n2;

while ((f_n2 = f_n0 + f_n1) < MAX_VALUE)
{
    if (f_n2 % 2 == 0)
        sum += f_n2;
    f_n0 = f_n1;
    f_n1 = f_n2;
}
printf("%d\n", sum);
于 2009-10-29T15:54:21.603 回答
3

我不是程序员，但这是对 Leffler 代码的改编，没有 IF 标准。根据我在偶数斐波那契数列中发现的模式：0,2,8,34,144,610,2584... 有趣的是：f_n2 = 4 *f_n1 + f_n0。这也意味着这个程序只需要 1/3 的计算，因为它甚至不考虑/计算奇数斐波那契数。

enum { MAX_VALUE = 4000000 };
int sum  = 2;
int f_n0 = 0;
int f_n1 = 2;
int f_n2 = 8;

while (f_n2 < MAX_VALUE)
{
    sum += f_n2;
    f_n0 = f_n1;
    f_n1 = f_n2;
    f_n2 = 4*f_n1 + f_n0;
}
printf("%d\n", sum);
于 2014-02-28T14:23:48.543 回答
2

尝试改变这个：

while (i<limit-2)

对此：

while (y<limit)

如所写，您的程序正在循环，直到它达到第 4 百万个斐波那契数（即，当 i 达到 400 万时，虽然溢出显然首先发生）。循环应该检查 y（较大的斐波那契数）何时大于 400 万。

于 2009-10-29T17:50:21.400 回答
1

伙计们，我得到了答案。我确认了结果并且 int 可以处理它。这是我的程序：

#include <stdio.h>
int main() {
    int x=1,y=2,sum,limit;     //Here value of first 2 terms have been initialized as 1 and 2
    int evensum=2;             //Since in calculation, we omit 2 which is an even number
    printf("Enter Limit: ");   //Enter limit as 4000000 (4million) to get desired result
    scanf("%d",&limit);
    while( (x+y)<limit ) {
        sum=x+y;
        x=y;
        y=sum;
        if (sum%2==0)
            evensum+=sum;
    }
    printf("%d \n",evensum);
    return 0;
}

感谢所有的回复和帮助。“思考我的脚”来救援:)

于 2009-10-31T17:18:17.923 回答
0

使用BigInt。

再说一次，unsigned int存储价值超过 40 亿，所以即使“所有斐波那契数的总和不超过 400 万”（显然，必须小于 800 万），你也不应该有任何问题？

于 2009-10-29T15:19:01.603 回答
0

int对于几乎每个现代系统上的数百万价值来说，它已经足够大了，但long如果你担心它，你可以使用它。如果这仍然给您带来奇怪的结果，那么问题出在您的算法上。

于 2009-10-29T15:29:59.787 回答
0

您的程序打印 F_1 + ..+ F_limit 而不是 F_1 + ... F_n 与 F_n < limit 如您所述。

查看关于斐波那契数和斯隆 A000045的维基百科文章：斐波那契数呈指数增长。检查此表F_48 = 4807526976，它超过了 int。F_100 是 354224848179261915075 ，它甚至肯定会溢出 int64_t （不过，您的堆栈不会溢出）。

于 2009-10-29T22:53:37.683 回答
0

一个有趣的解决方案是对斐波那契数列使用封闭形式，对几何级数使用封闭形式。最终解决方案如下所示：

  sum = ( (1-pow(phi_cb, N+1)) / (1-phi_cb) - (1-pow(onephi_cb,N+1)) / (1-onephi_cb)) / sqrt(5);

在哪里

  double phi       = 0.5 + 0.5 * sqrt(5);
  double phi_cb    = pow(phi, 3.0);
  double onephi_cb = pow(1.0 - phi, 3.0);
  unsigned N = floor( log(4000000.0 * sqrt(5) + 0.5) / log(phi) );
  N = N / 3;

当然，还有关于 double 到 int 类型转换的所有警告。

于 2013-09-06T16:51:33.930 回答
0

斐波那契数列中的每个新项都是通过添加前两项来生成的。从 1 和 2 开始，前 10 个术语将是：

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

通过考虑斐波那契数列中值不超过四百万的项，求偶数项之和。

   int main()

  {  
     long first = 1, second = 2, next, c;

     int sum=0;
     for ( c = 1 ; c <100000000; c++ )

  {

     next = first + second;
     if(next>=4000000)
     {
     next=  next-second;
     break;
     }

     first = second;
     second = next;    

  if(next%2==0){

     sum=sum+next;
  }

 }

  printf("the sum of even valued  term is %d\n",sum+2);


 }
于 2014-12-13T20:09:26.823 回答
0

这是我的程序：

#include <iostream>

long int even_sum_fibonacci(int n){
    int i = 8;
    int previous_i = 2;
    int next_i = 0;
    long int sum = previous_i + i;;
    while(n>next_i){
        next_i = i*4 + previous_i;
        previous_i = i;
        i = next_i;
        sum = sum + i;
    }
    return sum - next_i; //now next_i and i are both the bigger number which
                         //exceeds 4 million, but we counted next_i into sum
                         //so we'll need to substract it from sum
}



int main()
{
   std::cout << even_sum_fibonacci(4000000) << std::endl; 

   return 0;
}

因为如果您查看斐波那契数列（前几个偶数） 2 8 34 144 610 2584 ...您会发现它与 next_number = current_number * 4 + previous_number的模式匹配。

这是解决方案之一。所以结果是4613732

于 2015-09-29T22:24:14.517 回答
0

你可以试试下面的代码。

public static void SumOfEvenFibonacciNumbers()
{
    int range = 4000000;
    long sum = 0;
    long current = 1;
    long prev = 0;
    long evenValueSum= 0;
    while (evenValueSum< range)
    {
        sum = prev + current;
        prev = current;
        current = sum;
        if (sum % 2 == 0 )
        {
            evenValueSum = evenValueSum+ sum;
        }
    }

    Console.WriteLine(evenValueSum);
}
于 2017-01-20T12:44:01.457 回答
0

你可以使用上面的代码。

import numpy as np
M = [[0,1],[1,1]]
F = [[0],[1]]
s = 0
while(F[1][0] < 4000000):
 F = np.matmul(M, F)
 if not F[0][0]%2:
   s+=F[0][0]

print(s)

我们可以在 O(log n) 时间内做得比这更好。此外，一个 2 × 2 矩阵和一个二维向量可以在 O(1) 时间内再次相乘。因此，计算 M n就足够了。以下递归算法计算 M n

  1. 如果 n = 0，则返回 I 2
  2. 如果 n = 1，则返回 M。
  3. 如果 n = 2m。
  4. 递归计算 N = M m，并设置 P = N 2。
  5. 如果 n = 2m+1，设置 P = PM。
  6. 返回 P。我们有 T(n) = T(n/2) + O(1)，根据大师定理 T(n) = O(log n)

您还可以对偶数斐波那契数列使用递归：EFn = 4EFn-1 + EFn-2，种子值 EF0 = 0 和 EF1 = 2。

于 2018-04-21T06:50:35.257 回答
0

简单的解决方案是：-

#include <iostream>
using namespace std;

int main(int argc, char** argv) {   
int n1=1;
int n2=2;
int num=0,sum;

for (int i=1;i,n1<4000000;i++)
{

    cout<<"    "<<n1;
    num=n1+n2;
    if(!(n1%2))
    {
        sum+=n1;
    }
    n1=n2;
    n2=num;     
}
cout<<"\n Sum of even term is = "<<sum;
return 0;
}
于 2019-06-06T11:12:44.723 回答