Почему (int) 55 == 54 в C ++?

Question

Итак, я изучаю C ++. У меня есть «Язык программирования C ++» и «Эффективный C ++», и я работаю через Project Euler. Задача 1 ... Дунзо. Проблема 2 ... не так много. Я работаю в VS2008 над консольным приложением Win32.

Какова сумма всех четных членов последовательности Фибоначчи до 4 миллионов?

Это не сработало, поэтому я сократил до 100 ...

Вот что я написал ...

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

А вот и вывод ...

Project Euler Задача 2:

Каждый новый термин в Фибоначчи последовательность генерируется путем добавления предыдущие два срока. Начиная с 1 и 2, первые 10 слагаемых будут:

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

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

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
Ответ: 99

Итак, у меня есть три столбца кода отладки ... число, возвращаемое из функции generate, (int) generateNumber и (int) generateNumber% 2

Итак, на 11-м семестре мы имеем

55,54,0

Почему (int) 55 = 54?

Спасибо

Answer 1

Приведение к int усекает номер - так же, как если бы вы звонили floor(currentFib). Таким образом, даже если currentFib равно 54.999999 ... (число, настолько близкое к 55, что при печати оно будет округлено в большую сторону), (int)currentFib даст 54.

Answer 2

Из-за округления с плавающей запятой эта строка 55 вычисляет что-то вроде 54.99999. Приведение двойного к int сокращает .99999 сразу.

На моей машине печать столбца с отображением (currentFib-(int)currentFib) показывает ошибки порядка 1.42109e-14. Так что это больше похоже на 0.999999999999986.

Answer 3

Shog9 делает это правильно, использование типа double для решения проблемы, подобной этой, не лучший способ, если вы собираетесь приводить вещи в целые числа. Если ваш компилятор поддерживает его, вы должны использовать длинный длинный или какой-либо другой 64-битный целочисленный тип, который почти наверняка будет содержать результат суммы всех четных членов, меньших 4 миллионов последовательности Фибоначчи.

Если мы используем тот факт, что последовательность Фибоначчи следует шаблону: нечетное, нечетное, нечетное, нечетное, нечетное. Четное ... что-то следующее должно сделать свое дело.

...
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";
....

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

Глядя на это, я понимаю, что вы, вероятно, могли бы обойтись без стандартного 32-разрядного целого числа без знака в качестве числа суммы, но я оставлю это как есть на всякий случай.

Кроме того, ваш код выполняет большое количество вызовов функции для генерации n-й функции числа Фибоначчи. Приличный оптимизирующий компилятор встроит эти вызовы, но если этого не произойдет, все замедлится, поскольку вызовы функций стоят дороже, чем другие методы.

Answer 4

Хорошо, короткий ответ: ни при каких условиях (int) 55 == 54, поэтому вам нужно начать спрашивать себя, что в действительности делает связанная строка кода.

Первый вопрос: насколько сильно связывается == по сравнению с типом?

Answer 5

Все вышеперечисленные предложения не использовать значения с плавающей запятой для целочисленной математики заслуживают внимания!

Если вы хотите целочисленное «округление» для положительных значений с плавающей запятой, чтобы значения с дробным компонентом ниже 0,5 округлились до следующего наименьшего целого числа, а значения с дробным компонентом 0,5 или более округлились до следующего более высокого целого числа, например 1003 *

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

Добавьте 0,5 к значению, которое вы разыгрываете.

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

Answer 6

Я знаю, что это не поможет с вашим реальным вопросом, но вы упомянули, что изучаете C ++. Я бы порекомендовал держать как можно ближе к ANSI для целей обучения. Я думаю, что /Za на MSVC (что вы, вероятно, используете), или -ansi -pedantic на GCC.

В частности, вы должны использовать одну из этих сигнатур для main, пока у вас не будет веской (специфичной для платформы) причины поступить иначе:

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

... вместо любой версии для конкретной платформы, такой как этот (только для Windows) пример:

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

Answer 7

Я согласен на 100% с ответом shog9 - с алгоритмом, который вы использовали для вычисления Фибоначчи, вы должны быть очень осторожны с значениями с плавающей запятой. Я обнаружил, что страница cubbi.com: числа Фибоначчи в c ++ , кажется, показывает другие способы их получения.

Я искал хорошую идею о том, как заставить вашу реализацию GenerateNthFibonacciNumber обрабатывать случаи, когда она возвращает двойное 54.999999, но когда вы приводите к int или long, вы получаете 54.

Я наткнулся на то, что кажется разумным решением при C ++ округлении , которое я адаптировал ниже в вашем коде.

Кроме того, это не огромная сделка, но вы можете предварительно рассчитать PHI, а затем либо передать ее в качестве параметра, либо ссылаться на нее как глобальную - теперь вы пересчитываете ее каждый раз, когда вызываете функцию .

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

Наконец, вот как я переписал ваш метод Solve (), чтобы GenerateNthFibonacciNumber (FibIndex) вызывался только в одном месте кода. Я также добавил столбец с текущей промежуточной суммой четных терминов Фибоначчи к вашему выводу:

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 8

Сломать код для порождающей строки, иногда число с плавающей запятой не ведет себя так, как мы думаем, когда используется в длинном выражении ... разбить код и проверить его.