Что такое сумма четных членов Фибоначчи (4 миллиона фунтов стерлингов)? [Путаница с типом данных большого значения]

Поскольку вам нужно всего четыре миллиона, вполне вероятно, что int не является вашей проблемой.

Вполне возможно, что ваша программа содержит ошибки и что с хранилищем данных все в порядке, поэтому вам следует протестировать вашу программу на меньших значениях. Например, ясно, что сумма первых трех четных слагаемых равна 44 (подсказка: каждое третье слагаемое четно), поэтому, если вы запустите свою программу с ограничением 50, вы должны мгновенно получить обратно 44. Продолжайте запускать небольшие тестовые случаи, чтобы быть уверенными в более крупных.

В целях безопасности используйте тип данных long; стандарт C требует, чтобы он содержал не менее 4 миллиардов, но на большинстве машин 'int' также будет содержать 4 миллиарда.

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);

Я не программист, но вот адаптация к коду Леффлера без IF-критерия. Это должно работать для MAX_VALUES выше 2 (учитывая, что в синтаксисе программирования нет ошибок), основываясь на шаблоне, который я нашел в четном ряду Фибоначчи: 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);

Попробуйте изменить это:

while (i<limit-2)

к этому:

while (y<limit)

Как написано, ваша программа циклически повторяется, пока не достигнет 4-миллионного числа Фибоначчи (т. е. когда я доберусь до 4 миллионов, хотя, очевидно, сначала произойдет переполнение). Цикл должен проверять, когда y (большее число Фибоначчи) становится больше 4 миллионов.

int достаточно велико для значений в миллионы почти во всех современных системах, но вы можете использовать long, если вас это беспокоит. Если это по-прежнему дает вам странные результаты, проблема заключается в вашем алгоритме.

Используйте BigInt< /а>.

Ваша программа печатает F_1 + ..+ F_limit, а не F_1 +... F_n с F_n ‹ limit, как вы описали.

Ознакомьтесь со статьей Википедии о числах Фибоначчи и Sloane A000045: Числа Фибоначчи растут экспоненциально. Проверяя эту таблицу F_48 = 4807526976 что превышает внутр. F_100 - это 354224848179261915075, что наверняка переполняет даже int64_t (хотя ваш стек этого не делает).

Ребята, я получил ответ. Я подтвердил результат, и 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;
}

Спасибо за все ответы и помощь. "Думаю на ногах" в помощь :)

Забавным решением является использование закрытой формы для последовательностей Фибоначчи и закрытой формы для геометрических прогрессий. Окончательное решение выглядит так:

  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.

Каждый новый член последовательности Фибоначчи создается путем добавления двух предыдущих членов. Начиная с 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);


 }  

Вот моя программа:

#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 ..., вы увидите, что он соответствует шаблону, который < strong>следующий_номер = текущий_номер * 4 + предыдущий_номер.

Это одно из решений. Таким образом, результат 4613732

Вы можете попробовать приведенный ниже код.

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);
}

Вы можете использовать приведенный выше код.

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ⁿ. Следующий рекурсивный алгоритм вычисляет Mⁿ

1. Если n = 0, вернуть I₂
2. Если n = 1, вернуть M.
3. If n = 2m.
4. Рекурсивно вычислить N = M^m и установить P = N².
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.

ПРОСТЫМ РЕШЕНИЕМ БУДЕТ БЫТЬ: -

#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;
}