Что такое сумма четных выражений в Фибоначчи (<4 миллиона)? [Большая путаница с типом данных] - PullRequest
Новая
       58

Что такое сумма четных выражений в Фибоначчи (<4 миллиона)? [Большая путаница с типом данных]

2 голосов
/ 29 октября 2009

Начиная с 1 и 2, первые 10 членов Серии Фибоначчи будут:

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

Найдите сумму всех четных членов в последовательности, которые не превышают 4 млн.

Теперь у меня появилась идея, как это сделать. Но я запутался в типах данных для хранения таких больших данных. Я получаю странные результаты с int. (

БОЛЬШЕ: Это проект Эйлера, 2-й вопрос. Но я не могу получить это. Я получаю сумасшедшие ценности как ответ. Может кто-нибудь выложить пожалуйста идеальную программу?

РЕДАКТИРОВАТЬ: Вот что я написал для простой печати Фибоначчи на экране. Голый Basic. Моя переменная сходит с ума, даже когда я даю 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;
}

Ответы [ 15 ]

6 голосов
/ 29 октября 2009

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

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

3 голосов
/ 29 октября 2009

В целях безопасности используйте тип данных 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);
2 голосов
/ 28 февраля 2014

Я не программист, но вот адаптация к коду Леффлера без 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);
2 голосов
/ 29 октября 2009

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

while (i<limit-2)

к этому: 

while (y<limit)

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

0 голосов
/ 06 июня 2019

ПРОСТОЕ РЕШЕНИЕ БЫЛО: - 

#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;
}
0 голосов
/ 21 апреля 2018

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

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)

Мы можем добиться большего успеха за это время (log n). Кроме того, матрица 2 × 2 и двумерный вектор могут быть снова умножены за O (1) раз. Поэтому достаточно вычислить M n . Следующий рекурсивный алгоритм вычисляет M n

  1. Если n = 0, вернуть I 2
  2. Если n = 1, вернуть M.
  3. Если n = 2 м.
  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.

0 голосов
/ 20 января 2017

Вы можете попробовать следующий код. 

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);
}
0 голосов
/ 30 сентября 2015

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

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

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

0 голосов
/ 13 декабря 2014

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


 }
0 голосов
/ 06 сентября 2013

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

  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;

со всеми оговорками, касающимися двойных преобразований в int, конечно.

Страница:
...