O que é soma de termos, mesmo em Fibonacci (<4million)? [Confusão Grande Valor Tipo de dados]

https://stackoverflow.com/questions/1644446

10-07-2019
|

Pergunta

Ao começar com 1 e 2, os primeiros 10 termos de Fibonacci Series será:

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

Encontre a soma de todos os termos even-valorizados na seqüência que não excedam 4 milhões.

Agora, eu tive a idéia de como fazer isso. Mas eu estou confuso sobre os tipos de dados para armazenar esses dados grandes. Eu estou recebendo resultados estranhos com int. : (

Mais: seu projeto Euler segunda pergunta. Mas eu não posso obtê-lo. Recebo valores loucos como resposta. Alguém por favor pode postar o programa ideal?

EDIT: Aqui está o que eu escrevi para apenas imprimir Fibonacci para a tela. Nua Basic. Meu variável fica louco mesmo quando eu dou 100 para o limite. É o meu erro código?

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

RESOLVIDO: Na verdade, eu consegui obter a solução mim. Aqui é o meu programa. Ele funciona.

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

Solução 9

Gente, eu tenho a resposta. I confirmou o resultado e int pode lidar com isso. Aqui está o meu programa:

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

Thx por todas as respostas e ajuda. "Pensando em meus pés" para o resgate:)

Outras dicas

Uma vez que você só quer até quatro milhões, é provável que int não é o seu problema.

É bem possível que o seu programa é buggy e que o armazenamento de dados é muito bem, então você deve testar seu programa em valores menores. Por exemplo, é claro que a soma dos três primeiros termos ainda é de 44 (dica: cada terceiro termo é mesmo) por isso, se você executar o seu programa com um limite de 50, então você deve começar imediatamente 44 de volta. Continue correndo casos de teste pequenas para obter a confiança nas maiores.

Por razões de segurança, use o 'long' tipo de dados; o padrão C exige que a espera pelo menos 4 bilhões, mas na maioria das máquinas, 'int' também irá realizar 4 bilhões.

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

Tente alterar o seguinte:

while (i<limit-2)

a esta:

while (y<limit)

Como escrito, o seu programa está dando um ciclo até chegar ao número Fibonacci 4000000 (ou seja, quando i chega a 4 milhões, embora estouro obviamente ocorrer primeiro). O circuito deve verificar para ver quando y (o maior número de Fibonacci) torna-se maior do que 4.000.000.

Eu não sou um programador, mas aqui é uma adaptação ao código de Leffler sem a IF-critério. Ele deve funcionar para MAX_VALUES acima de 2 (dado não há erros na sintaxe de programação), com base em um padrão que eu encontrei na série, mesmo só de Fibonacci: 0,2,8,34,144,610,2584 ... tão interessante: f_n2 = 4 * f_n1 + f_n0. Isso também significa que este programa só precisa de 1 / 3rd dos cálculos, uma vez que nem sequer considerar / calcular os números ímpares de Fibonacci.

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

int é grande o suficiente para valores na casa dos milhões em quase todos os sistemas modernos, mas você pode usar long se você está preocupado com isso. Se isso ainda lhe dá resultados estranhos, então o problema é com o seu algoritmo.

Use BigInt .

Então, novamente, lojas unsigned int valores até mais de 4 bilhões de dólares, para que você não deve ter quaisquer problemas, mesmo com "soma de todos os números de Fibonacci até 4 milhões" (que, obviamente, tem que ser inferior a 8 mil) ?

Um bug que provavelmente você está vendo é a má formatação do printf () declarações. Com um printf ( "% d% d") seguido por um printf ( "% d"), número de 3, 5, 8, 13, 21, 34, 55 vai imprimir como: 3 5 21 813 3455 o que certamente parece saída funky com números grosseiramente inadequadas. Você precisa de um pouco mais espaços ou linefeeds:. Printf ( "% d% d \ n"), printf ( "% d \ n")

Eu também não vejo onde você está realmente verificando apenas para os termos ainda contribuir para a soma.

Suas impressões programa f_1 + .. + F_limit e não f_1 + ... f_n com f_n

Verifique o artigo da Wikipedia sobre Fibonacci Numbers e Sloane A000045 : números de Fibonacci cresce exponencialmente. Marcar esta href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html" rel="nofollow mesa F_48 = 4807526976 que excede int. F_100 é 354224848179261915075 que certamente transborda mesmo int64_t (sua pilha não, embora).

Uma solução divertido é usar a forma fechada para sequências de Fibonacci e a forma fechada para progressão geométrica. Os olhares de soluções ponta como este:

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

onde

  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;

com todas as advertências sobre dupla para conversões do tipo int é claro.

Cada novo prazo na sequência de Fibonacci é gerado adicionando os dois termos anteriores. Ao começar com 1 e 2, os primeiros 10 termos serão:

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

Ao considerar os termos da sequência de Fibonacci cujos valores não excedam quatro milhões, encontrar a soma dos termos ainda valorizados.

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


 }

Aqui está o meu programa:

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

Porque se você olhar para a série de Fibonacci (para os primeiros números pares) 2 8 34 144 610 2584 ... você verá que ele corresponde ao padrão que next_number = CURRENT_NUMBER * 4 + previous_number .

Esta é uma das soluções. Assim, o resultado é 4613732

Você pode tentar o código abaixo.

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

Você pode usar o código acima.

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)

Nós podemos fazer melhor do que isso em O (log n). Além disso, uma matriz de 2 x 2 e um vector bidimensional pode ser multiplicado novamente em O (1) hora. Portanto basta calcular M ⁿ. O seguinte algoritmo recursivo calcula M ⁿ

Se n = 0, voltar I ₂
Se n = 1, retornar M.
Se n = 2m.
recursivamente calcular N = M ^m, e o conjunto de P = N ².
Se n = 2m + 1, P = conjunto PM.
Voltar P. Nós temos T (n) = T (n / 2) + O (1), e pelo teorema de mestre T (n) = O (log n)

Você também pode usar recorrência para a sequência de Fibonacci Mesmo é: EFN = 4EFn-1 + EFN-2 com valores de semente EF0 = 0 e EF1 = 2.

SIMPLE solução seria: -

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

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow