¿Cuál es la suma de términos pares en Fibonacci (< 4million)? [Confusión de tipo de datos de gran valor]
https://stackoverflow.com/questions/1644446
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Al comenzar con 1 y 2, los primeros 10 términos de la serie Fibonacci serán:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Encuentre la suma de todos los términos pares en la secuencia que no excedan los 4 millones.
Ahora, tengo la idea de cómo hacer esto. Pero estoy confundido acerca de los tipos de datos para contener datos tan grandes. Estoy obteniendo resultados extraños con int . :(
MÁS: su proyecto Euler segunda pregunta. Pero no puedo entenderlo. Obtengo valores locos como respuesta. ¿Alguien puede publicar el programa ideal?
EDITAR: Esto es lo que escribí para imprimir Fibonacci en la pantalla. Desnudo básico. Mi variable se vuelve loca incluso cuando doy 100 por el límite. ¿Mi código es incorrecto?
// 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;
}
RESUELTO: En realidad, logré obtener la solución yo mismo. Aquí está mi programa. 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;
}
Solución 9
Chicos, tengo la respuesta. Confirmé el resultado e int puede manejarlo. Aquí está mi 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;
}
Gracias por todas las respuestas y ayuda. "Pensar en mis pies" al rescate :)
Otros consejos
Dado que solo desea hasta cuatro millones, es probable que int no sea su problema.
Es muy posible que su programa tenga errores y que el almacenamiento de datos esté bien, por lo que debe probar su programa en valores más pequeños. Por ejemplo, está claro que la suma de los primeros tres términos pares es 44 (sugerencia: cada tercer término es par), por lo que si ejecuta su programa con un límite de 50, debería recuperar 44 al instante. Siga ejecutando casos de prueba pequeños para obtener confianza en los más grandes.
Por seguridad, use el tipo de datos 'largo'; el estándar C requiere que contenga al menos 4 mil millones, pero en la mayoría de las máquinas, 'int' también tendrá 4 mil millones.
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);
Intenta cambiar esto:
while (i<limit-2)
a esto:
while (y<limit)
Como está escrito, su programa está en ciclo hasta llegar al número 4 millones de Fibonacci (es decir, cuando llego a 4 millones, aunque obviamente el desbordamiento ocurre primero). El ciclo debe verificar para ver cuándo y (el número más grande de Fibonacci) llega a ser mayor de 4 millones.
No soy un programador, pero aquí hay una adaptación al código de Leffler sin el criterio IF. Debería funcionar para MAX_VALUES por encima de 2 (dado que no hay errores en la sintaxis de programación), basado en un patrón que encontré en la serie de Fibonacci uniforme: 0,2,8,34,144,610,2584 ... tan interesante: f_n2 = 4 * f_n1 + f_n0. Esto también significa que este programa solo necesita 1/3 de los cálculos, ya que ni siquiera considera / calcula los números impares 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 es lo suficientemente grande para valores de millones en casi todos los sistemas modernos, pero puede usar long si está preocupado por ello. Si eso todavía te da resultados extraños, entonces el problema está en tu algoritmo.
Use BigInt .
Por otra parte, unsigned int almacena valores de hasta más de 4 mil millones, por lo que no debería tener ningún problema incluso con la suma de todos los números de Fibonacci de hasta 4 millones. (que, obviamente, tiene que ser inferior a 8 mil)?
Un error que probablemente esté viendo es el mal formato de sus declaraciones printf (). Con una printf ("% d% d ") seguida de una printf ("% d "), los números de 3, 5, 8, 13, 21, 34, 55 se imprimirán como: 3 5 813 21 3455 que sin duda parece una producción original con números muy inapropiados. Necesita algunos espacios o saltos de línea más: printf ("% d% d \ n "), printf ("% d \ n ").
Tampoco veo dónde estás buscando solo los términos pares para contribuir a la suma.
Su programa imprime F_1 + .. + F_limit y no F_1 + ... F_n con F_n < límite como lo describiste.
Consulte el artículo de Wikipedia sobre Números de Fibonacci y Sloane A000045 : los números de Fibonacci crecen exponencialmente. Comprobando esta tabla F_48 = 4807526976 que excede int. F_100 es 354224848179261915075 que seguramente desborda incluso int64_t (sin embargo, su pila no lo hace).
Una solución divertida es usar la forma cerrada para las secuencias de Fibonacci y la forma cerrada para las progresiones geométricas. La solución final se ve así:
sum = ( (1-pow(phi_cb, N+1)) / (1-phi_cb) - (1-pow(onephi_cb,N+1)) / (1-onephi_cb)) / sqrt(5);
donde
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;
con todas las advertencias con respecto a las conversiones de tipo doble a int, por supuesto.
Cada nuevo término en la secuencia de Fibonacci se genera agregando los dos términos anteriores. Al comenzar con 1 y 2, los primeros 10 términos serán:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Al considerar los términos en la secuencia de Fibonacci cuyos valores no superan los cuatro millones, encuentre la suma de los términos de valor par.
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);
}
Aquí está mi 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 si nos fijamos en la serie de Fibonacci (en los primeros números pares) 2 8 34 144 610 2584 ... verá que coincide con el patrón que next_number = current_number * 4 + previous_number .
Esta es una de las soluciones. Entonces el resultado es 4613732
Puedes probar el siguiente código.
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);
}
Puede usar el código anterior.
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)
Podemos hacerlo mejor que esto en tiempo O (log n). Además, una matriz de 2 × 2 y un vector bidimensional se pueden multiplicar nuevamente en el tiempo O (1). Por lo tanto, es suficiente para calcular M n . El siguiente algoritmo recursivo calcula M n
- Si n = 0, devuelve I 2
- Si n = 1, devuelve M.
- Si n = 2m.
- Calcule recursivamente N = M m y establezca P = N 2 .
- Si n = 2m + 1, configure P = PM.
- Volver P. Tenemos T (n) = T (n / 2) + O (1), y por el teorema del maestro T (n) = O (log n)
También puede usar la recurrencia para la secuencia Even Fibonacci es: EFn = 4EFn-1 + EFn-2 con valores de semillas EF0 = 0 y EF1 = 2.
SOLUCIÓN SIMPLE SERÍA: -
#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;
}
