So I'm learning C++. I've got my "C++ Programming Language" and "Effective C++" out and I'm running through Project Euler. Problem 1...dunzo. Problem 2...not so much. I'm working in VS2008 on a Win32 Console App.
所以我正在学习C ++。我有“C ++编程语言”和“有效的C ++”,我正在运行Project Euler。问题1 ... dunzo。问题2 ......不是那么多。我在Win32控制台应用程序上使用VS2008。
Whats the Sum of all even terms of the Fibonacci Sequence under 4 million?
什么是斐波纳契数列的所有偶数项的总和低于400万?
It wasn't working so I cut down to a test case of 100...
它没有工作,所以我减少到100的测试用例......
Here's what I wrote...
这是我写的......
// 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));
}
And here's the output...
这是输出......
Project Euler Problem 2:
项目欧拉问题2:
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:
Fibonacci序列中的每个新术语都是通过添加前两个术语生成的。从1和2开始,前10个术语将是:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
1,2,3,5,8,13,21,34,55,89 ......
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
找出序列中所有偶数项的总和,不超过四百万。
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
Answer: 990 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
So I have three columns of debug code...the number returned from the generate function, (int)generatedNumber, and (int)generatedNumber % 2
所以我有三列调试代码...从generate函数返回的数字,(int)generatedNumber和(int)generatedNumber%2
So on the 11th term we have
所以在我们的第11个学期
55,54,0
Why does (int)55 = 54?
为什么(int)55 = 54?
Thanks
8 个解决方案
#1
56
Casting to int truncates the number - same as if you'd called floor(currentFib). So even if currentFib is 54.999999... (a number so close to 55 that it will be rounded up when printed), (int)currentFib will produce 54.
转换为int会截断数字 - 就像你调用floor(currentFib)一样。所以即使currentFib是54.999999 ...(一个接近55的数字,它将在打印时被四舍五入),(int)currentFib将产生54。
#2
13
Due to floating point rounding, that 55 row is computing something like 54.99999. Casting double to int truncates the .99999 right off.
由于浮点舍入,55行计算类似于54.99999。将double转换为int会截断.99999。
On my machine, printing a column displaying (currentFib-(int)currentFib) shows errors on the order of 1.42109e-14. So it's more like 0.999999999999986.
在我的机器上,打印显示(currentFib-(int)currentFib)的列显示的顺序为1.42109e-14。所以它更像是0.999999999999986。
#3
4
Okay, short answer is that under no condition should (int)55 == 54, so you need to start asking yourself what the associated line of code is really doing.
好的,简短的回答是,在任何情况下都不应该(int)55 == 54,所以你需要开始问自己相关的代码行是什么。
First question: how strongly does == bind compared to a typecast?
第一个问题:与类型转换相比,==绑定有多强?
#4
4
Shog9 has it right, using the type double for a problem like this is not the best way to go if you are going to cast things to ints. If your compiler supports it you should use a long long or some other 64 bit integer type, that will almost certainly hold the result of the sum of all the even terms less than 4 million of the Fibonacci sequence.
Shog9是正确的,使用double类型来解决这个问题,如果你要将内容转换为int,这不是最好的方法。如果您的编译器支持它,您应该使用long long或其他64位整数类型,这几乎肯定会保留所有偶数项的总和小于4百万Fibonacci序列的结果。
If we use the fact that the Fibonacci sequence follows the pattern odd odd even odd odd even... something as follows should do the trick.
如果我们使用Fibonacci序列遵循奇数奇偶偶奇数偶数的事实......如下所示应该做的伎俩。
...
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";
....
that should do the trick, there might be even faster ways but this one is pretty direct and easy to read.
应该做的伎俩,可能会有更快的方式,但这个方式非常直接,易于阅读。
Looking at it I realize that you could probably get away with a standard unsigned 32 bit integer as the sum number but I will leave it as is just in case.
看着它,我意识到你可能会使用标准的无符号32位整数作为和数,但我将保留它以防万一。
Additionally your code makes a large number of function calls to the generate nth Fibonacci number function. A decent optimizing compiler will inline these calls but if it doesn't then things will slow down since function calls are more expensive than other techniques.
此外,您的代码会对生成第n个Fibonacci数函数进行大量函数调用。一个体面的优化编译器将内联这些调用,但如果没有,那么事情会变慢,因为函数调用比其他技术更昂贵。
#5
2
I agree 100% with shog9's answer - with the algorithm you used to calculate Fibonacci, you have to be really careful with floating point values. I found that the page cubbi.com: fibonacci numbers in c++ seems to show other ways of obtaining them.
我同意100%的shog9的答案 - 使用你用来计算Fibonacci的算法,你必须非常小心浮点值。我发现c ++中的页面cubbi.com:fibonacci数字似乎显示了获取它们的其他方法。
I looked around for a good idea on how to make your implementation of GenerateNthFibonacciNumber handle cases where it returns the double 54.999999, but when you cast to an int or a long you get 54.
我四处寻找一个关于如何使你的GenerateNthFibonacciNumber处理它返回双54.999999的情况的好主意,但是当你转换为int或long时你得到54。
I came across what appears to be a reasonable solution at C++ Rounding, which I have adapted below in your code.
我在C ++ Rounding中遇到了似乎是合理的解决方案,我在下面的代码中进行了调整。
Also, It's not a huge deal, but you may want to precalculate PHI, then either pass it as a parameter or reference it as a global - now you are recalculating it every time you call the function.
此外,这不是一个大问题,但您可能想要预先计算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);
}
Finally, here's how I rewrote your Solve() method so that GenerateNthFibonacciNumber(FibIndex) is only called in one place in the code. I also added the column with the current running total of the even Fibonacci terms to your output:
最后,这是我如何重写你的Solve()方法,以便只在代码中的一个地方调用GenerateNthFibonacciNumber(FibIndex)。我还在输出中添加了当前运行总计甚至Fibonacci项的列:
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;
}
#6
2
I know this is not going to help with your real question, but you mentioned you're learning C++. I would recommend keeping as close to ANSI as possible, for learning purposes. I think that's /Za on MSVC (which is what you're probably using), or -ansi -pedantic on GCC.
我知道这对你的真实问题没有帮助,但你提到你正在学习C ++。出于学习目的,我建议尽可能接近ANSI。我认为这是MSVC上的/ Za(这是你可能正在使用的),或者是GCC上的-ansi -pedantic。
In particular, you should be using one of these signatures for main until you have a good (platform-specific) reason to do otherwise:
特别是,您应该使用其中一个签名作为main,直到您有一个良好的(平台特定的)原因,否则:
int main(int argc, char *argv[]);
int main(int argc, char **argv); // same as the first
int main();
...instead of any platform-specific version, such as this (Windows-only) example:
...而不是任何特定于平台的版本,例如此(仅限Windows)示例:
#include <windows.h> // defines _TCHAR and _tmain
int _tmain(int argc, _TCHAR* argv[]); // win32 Unicode vs. Multi-Byte
#7
2
All the above suggestions not to use floating point values for integer mathematics are worth noting!
所有上述建议不使用整数数学的浮点值值得注意!
If you want integer "rounding" for positive floating point values so that values with a fractional component below 0.5 round to the next lowest integer, and values with a fractional component of 0.5 or greater round to the next higher integer, e.g.
如果希望对正浮点值进行整数“舍入”,以使得小数分量低于0.5的值舍入到下一个最低整数,并且小数分量为0.5或更大的值舍入到下一个更高的整数,例如
0.0 = 0
0.1 = 0
0.5 = 1
0.9 = 1
1.0 = 1
1.1 = 1
...etc...
Add 0.5 to the value you are casting.
将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
#8
0
Break the code for generatring, at times float number dont behave the way we think when used in a long expression...break the code and check it.
打破generatring的代码,有时浮点数不会像我们在长表达式中使用时那样思考...打破代码并检查它。
#1
56
Casting to int truncates the number - same as if you'd called floor(currentFib). So even if currentFib is 54.999999... (a number so close to 55 that it will be rounded up when printed), (int)currentFib will produce 54.
转换为int会截断数字 - 就像你调用floor(currentFib)一样。所以即使currentFib是54.999999 ...(一个接近55的数字,它将在打印时被四舍五入),(int)currentFib将产生54。
#2
13
Due to floating point rounding, that 55 row is computing something like 54.99999. Casting double to int truncates the .99999 right off.
由于浮点舍入,55行计算类似于54.99999。将double转换为int会截断.99999。
On my machine, printing a column displaying (currentFib-(int)currentFib) shows errors on the order of 1.42109e-14. So it's more like 0.999999999999986.
在我的机器上,打印显示(currentFib-(int)currentFib)的列显示的顺序为1.42109e-14。所以它更像是0.999999999999986。
#3
4
Okay, short answer is that under no condition should (int)55 == 54, so you need to start asking yourself what the associated line of code is really doing.
好的,简短的回答是,在任何情况下都不应该(int)55 == 54,所以你需要开始问自己相关的代码行是什么。
First question: how strongly does == bind compared to a typecast?
第一个问题:与类型转换相比,==绑定有多强?
#4
4
Shog9 has it right, using the type double for a problem like this is not the best way to go if you are going to cast things to ints. If your compiler supports it you should use a long long or some other 64 bit integer type, that will almost certainly hold the result of the sum of all the even terms less than 4 million of the Fibonacci sequence.
Shog9是正确的,使用double类型来解决这个问题,如果你要将内容转换为int,这不是最好的方法。如果您的编译器支持它,您应该使用long long或其他64位整数类型,这几乎肯定会保留所有偶数项的总和小于4百万Fibonacci序列的结果。
If we use the fact that the Fibonacci sequence follows the pattern odd odd even odd odd even... something as follows should do the trick.
如果我们使用Fibonacci序列遵循奇数奇偶偶奇数偶数的事实......如下所示应该做的伎俩。
...
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";
....
that should do the trick, there might be even faster ways but this one is pretty direct and easy to read.
应该做的伎俩,可能会有更快的方式,但这个方式非常直接,易于阅读。
Looking at it I realize that you could probably get away with a standard unsigned 32 bit integer as the sum number but I will leave it as is just in case.
看着它,我意识到你可能会使用标准的无符号32位整数作为和数,但我将保留它以防万一。
Additionally your code makes a large number of function calls to the generate nth Fibonacci number function. A decent optimizing compiler will inline these calls but if it doesn't then things will slow down since function calls are more expensive than other techniques.
此外,您的代码会对生成第n个Fibonacci数函数进行大量函数调用。一个体面的优化编译器将内联这些调用,但如果没有,那么事情会变慢,因为函数调用比其他技术更昂贵。
#5
2
I agree 100% with shog9's answer - with the algorithm you used to calculate Fibonacci, you have to be really careful with floating point values. I found that the page cubbi.com: fibonacci numbers in c++ seems to show other ways of obtaining them.
我同意100%的shog9的答案 - 使用你用来计算Fibonacci的算法,你必须非常小心浮点值。我发现c ++中的页面cubbi.com:fibonacci数字似乎显示了获取它们的其他方法。
I looked around for a good idea on how to make your implementation of GenerateNthFibonacciNumber handle cases where it returns the double 54.999999, but when you cast to an int or a long you get 54.
我四处寻找一个关于如何使你的GenerateNthFibonacciNumber处理它返回双54.999999的情况的好主意,但是当你转换为int或long时你得到54。
I came across what appears to be a reasonable solution at C++ Rounding, which I have adapted below in your code.
我在C ++ Rounding中遇到了似乎是合理的解决方案,我在下面的代码中进行了调整。
Also, It's not a huge deal, but you may want to precalculate PHI, then either pass it as a parameter or reference it as a global - now you are recalculating it every time you call the function.
此外,这不是一个大问题,但您可能想要预先计算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);
}
Finally, here's how I rewrote your Solve() method so that GenerateNthFibonacciNumber(FibIndex) is only called in one place in the code. I also added the column with the current running total of the even Fibonacci terms to your output:
最后,这是我如何重写你的Solve()方法,以便只在代码中的一个地方调用GenerateNthFibonacciNumber(FibIndex)。我还在输出中添加了当前运行总计甚至Fibonacci项的列:
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;
}
#6
2
I know this is not going to help with your real question, but you mentioned you're learning C++. I would recommend keeping as close to ANSI as possible, for learning purposes. I think that's /Za on MSVC (which is what you're probably using), or -ansi -pedantic on GCC.
我知道这对你的真实问题没有帮助,但你提到你正在学习C ++。出于学习目的,我建议尽可能接近ANSI。我认为这是MSVC上的/ Za(这是你可能正在使用的),或者是GCC上的-ansi -pedantic。
In particular, you should be using one of these signatures for main until you have a good (platform-specific) reason to do otherwise:
特别是,您应该使用其中一个签名作为main,直到您有一个良好的(平台特定的)原因,否则:
int main(int argc, char *argv[]);
int main(int argc, char **argv); // same as the first
int main();
...instead of any platform-specific version, such as this (Windows-only) example:
...而不是任何特定于平台的版本,例如此(仅限Windows)示例:
#include <windows.h> // defines _TCHAR and _tmain
int _tmain(int argc, _TCHAR* argv[]); // win32 Unicode vs. Multi-Byte
#7
2
All the above suggestions not to use floating point values for integer mathematics are worth noting!
所有上述建议不使用整数数学的浮点值值得注意!
If you want integer "rounding" for positive floating point values so that values with a fractional component below 0.5 round to the next lowest integer, and values with a fractional component of 0.5 or greater round to the next higher integer, e.g.
如果希望对正浮点值进行整数“舍入”,以使得小数分量低于0.5的值舍入到下一个最低整数,并且小数分量为0.5或更大的值舍入到下一个更高的整数,例如
0.0 = 0
0.1 = 0
0.5 = 1
0.9 = 1
1.0 = 1
1.1 = 1
...etc...
Add 0.5 to the value you are casting.
将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
#8
0
Break the code for generatring, at times float number dont behave the way we think when used in a long expression...break the code and check it.
打破generatring的代码,有时浮点数不会像我们在长表达式中使用时那样思考...打破代码并检查它。