c++ - programa - serie fibonacci algoritmo

¿Por qué(int) 55== 54 en C++?

Question

Así que estoy aprendiendo C ++. Tengo mi "Lenguaje de programación C ++" y "C + efectivo" y estoy ejecutando Project Euler. Problema 1 ... dunzo. Problema 2 ... no tanto. Estoy trabajando en VS2008 en una aplicación de consola Win32.

¿Cuál es la suma de todos los términos pares de la secuencia de Fibonacci por debajo de 4 millones?

No estaba funcionando, así que reduje a un caso de prueba de 100 ...

Esto es lo que escribí ...

// Problem2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "Project Euler Problem 2:/n/n";
    cout << "Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:/n/n";
    cout << "1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .../n/n";
    cout << "Find the sum of all the even-valued terms in the sequence which do not exceed four million./n/n";
    cout << "Answer:  " << Solve();
}

double Solve() {
    int FibIndex = 0;
    double result = 0.0;
    double currentFib = GenerateNthFibonacciNumber(FibIndex);
    while (currentFib < 100.0){
        cout << currentFib << " " << (int)currentFib << " " << (int)currentFib % 2 << "/n";
        if ((int)currentFib % 2 == 0){
            result += currentFib;
            cout<<(int)currentFib;
        }
        currentFib = GenerateNthFibonacciNumber(++FibIndex);
    }
    return result;
}

double GenerateNthFibonacciNumber(const int n){
    //This generates the nth Fibonacci Number using Binet''s Formula
    const double PHI = (1.0 + sqrt(5.0)) / 2.0;
    return ((pow(PHI,n)-pow(-1.0/PHI,n)) / sqrt(5.0));
}

Y aquí está la salida ...

Proyecto Euler problema 2:

Cada nuevo término en la secuencia de Fibonacci se genera al agregar 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, ...

Encuentre la suma de todos los términos pares en la secuencia que no excedan los cuatro millones.

0 0 0
1 1 1
1 1 1
2 2 0
3 3 1
5 5 1
8 8 0
13 13 1
21 21 1
34 34 0
55 54 0
89 89 1
Respuesta: 99

Así que tengo tres columnas de código de depuración ... el número devuelto por la función de generación, (int) generatedNumber, y (int) generatedNumber% 2

Entonces, en el 11º término tenemos

55,54,0

¿Por qué (int) 55 = 54?

Gracias

Answer 1

Rompe el código de generatring, a veces el número de flotador no se comporta de la manera en que pensamos cuando se usa en una expresión larga ... rompe el código y verifica.

Answer 2

Casting to int trunca el número, igual que si floor(currentFib) . Entonces, incluso si currentFib es 54.999999 ... (un número tan cercano a 55 que se redondeará cuando se imprima), (int)currentFib producirá 54.

Answer 3

De acuerdo, la respuesta corta es que bajo ninguna condición debe (int) 55 == 54, por lo que debe comenzar a preguntarse qué está haciendo realmente la línea de código asociada.

Primera pregunta: ¿con qué fuerza == unen en comparación con un tipocast?

Answer 4

Debido al redondeo de punto flotante, esa fila 55 está calculando algo así como 54.99999. Casting double to int trunca el .99999 a la derecha.

En mi máquina, imprimir una columna que muestra (currentFib-(int)currentFib) muestra errores del orden de 1.42109e-14. Entonces es más como 0.999999999999986.

Answer 5

Estoy de acuerdo al 100% con la respuesta de shog9: con el algoritmo que usaste para calcular Fibonacci, debes tener mucho cuidado con los valores de coma flotante. Encontré que la página cubbi.com: números de fibonacci en c ++ parece mostrar otras formas de obtenerlos.

Busqué una buena idea sobre cómo hacer que su implementación de GenerateNthFibonacciNumber maneje casos en los que devuelve el doble 54.999999, pero cuando lo transfiere a una int o un long obtiene 54.

Encontré lo que parece ser una solución razonable en C ++ Rounding , que he adaptado a continuación en tu código.

Además, no es un gran problema, pero es posible que desee precalcular la PHI, luego pasarla como parámetro o referenciarla como global; ahora la vuelve a calcular cada vez que llame a la función.

double GenerateNthFibonacciNumber(const int n)
{
        //This generates the nth Fibonacci Number using Binet''s Formula   
        const double PHI = (1.0 + sqrt(5.0)) / 2.0;
        double x = ((pow(PHI,n)-pow(-1.0/PHI,n)) / sqrt(5.0));
        // inspired by http://www.codingforums.com/archive/index.php/t-10827.html
        return ((x - floor(x)) >= 0.5) ? ceil(x) : floor(x);
}

Finalmente, así es como reescribí el método Solve () para que GenerateNthFibonacciNumber (FibIndex) solo se llame en un lugar del código. También agregué la columna con el total acumulado actual de los términos pares de Fibonacci a su salida:

double Solve() {
    long FibIndex = 0;
    double result = 0.0;
    double oldresult = 0.0;
    int done = 0;
    const double PHI = (1.0 + sqrt(5.0)) / 2.0;

    while (!done)
    {
        double currentFib = GenerateNthFibonacciNumber(++FibIndex);
        if ((int)currentFib % 2 == 0)
        {
            oldresult = result;

            if (currentFib >= 4000000.0)
            {
                done = 1;
            }
            else
            {
                result += currentFib;
            }

        }
        cout << currentFib << " " << (int)currentFib << " " << (int)currentFib % 2 << " " << (int)result << "/n";       
    }
    return result;
}

Answer 6

Shog9 tiene razón, usar el tipo doble para un problema como este no es la mejor manera de ir si vas a lanzar cosas a ints. Si su compilador lo admite, debe usar un tipo de entero largo o de 64 bits, que seguramente tendrá el resultado de la suma de todos los términos pares de menos de 4 millones de la secuencia de Fibonacci.

Si usamos el hecho de que la secuencia de Fibonacci sigue el patrón odd odd even odd odd even ... algo de la siguiente manera debería ser el truco.

...
unsigned int fib[3];
fib[0]=1;
fib[1]=1;
fib[2]=2;

unsigned long long sum=0;

while(fib[2]<4000000)
{
    sum+=fib[2];

    fib[0]=(fib[1]+fib[2]);
    fib[1]=(fib[2]+fib[0]);
    fib[2]=(fib[0]+fib[1]);
}

std::cout<<"The sum is: "<<sum<<". /n";
....

eso debería ser el truco, podría haber formas aún más rápidas, pero esta es bastante directa y fácil de leer.

Mirándolo, me doy cuenta de que probablemente podría salirse con un entero estándar de 32 bits sin signo como el número de suma, pero lo dejaré como está por las dudas.

Además, su código realiza una gran cantidad de llamadas a funciones para generar la n. ° función de número de Fibonacci. Un compilador de optimización decente alineará estas llamadas, pero si no lo hace, las cosas se ralentizarán, ya que las llamadas a funciones son más costosas que otras técnicas.

Answer 7

Sé que esto no ayudará con tu pregunta real, pero mencionaste que estás aprendiendo C ++. Recomendaría mantenerme lo más cerca posible de ANSI, con fines de aprendizaje. Creo que es /Za en MSVC (que es lo que probablemente esté usando), o -ansi -pedantic en GCC.

En particular, debe usar una de estas firmas para main hasta que tenga una buena razón (específica de la plataforma) para hacer lo contrario:

int main(int argc, char *argv[]);
int main(int argc, char **argv); // same as the first
int main();

... en lugar de cualquier versión específica de la plataforma, como este ejemplo (solo para Windows):

#include <windows.h> // defines _TCHAR and _tmain
int _tmain(int argc, _TCHAR* argv[]); // win32 Unicode vs. Multi-Byte

Answer 8

¡Todas las sugerencias anteriores para no utilizar valores de coma flotante para matemáticas enteras valen la pena!

Si desea un "redondeo" entero para valores de coma flotante positivos, de modo que los valores con un componente fraccional por debajo de 0.5 redondeen al siguiente entero más bajo y valores con un componente fraccionario de 0.5 o mayor redondee al siguiente entero más alto, por ejemplo

0.0 = 0
0.1 = 0
0.5 = 1
0.9 = 1
1.0 = 1
1.1 = 1
...etc...    

Agregue 0.5 al valor que está emitiendo.

double f0 = 0.0;
double f1 = 0.1;
double f2 = 0.5;
double f3 = 0.9;

int i0 = ( int )( f0 + 0.5 );  // i0 = 0
int i1 = ( int )( f1 + 0.5 );  // i1 = 0
int i2 = ( int )( f2 + 0.5 );  // i2 = 1
int i3 = ( int )( f3 + 0.5 );  // i3 = 1