如何用C++找到Fibonacci序列？

Question

我正在尝试解决项目Euler上的问题2.问题是:

"Fibonacci序列中的每个新术语都是通过添加前两个术语生成的.从1和2开始,前10个术语将是:

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

通过考虑Fibonacci序列中的值不超过四百万的项,找到偶数项的总和."

我试图用C++解决这个问题.

到目前为止,这是我的代码

#include <iostream>
 using namespace std;

int main()
{
    //ANSWER = 4613732
    int max = 4000000;
    int n;
    int sum;

    for(n=0; n<=max;)
    {
        while(n%2 == 0)
        {
            n = (n-1)+(n-2);
        }
    }
    sum = n+=0;
    cout << sum << endl;
    return 0;
}

正如你所看到的,我知道正确的答案,从搜索它来检查我的答案.这段代码我刚刚运行,从未显示答案.任何人都可以给我提示如何达到这个答案,并帮助改进我的C++代码.提前致谢!

Answer 1

这是一种你不应该遵循的方法.(注意:这篇文章是一个笑话,但我很认真不遵循这种方法.尝试在你的C++理解水平上理解这种方法也是不明智的.)

#include <iostream>

struct Fib
{
  template<int n, int first=1, int second=1> struct Eval { enum {value = Eval<n-1, first, second>::value + Eval<n-2, first, second>::value}; };
  template<int first, int second> struct Eval<1, first, second> { enum {value = second}; };
  template<int first, int second> struct Eval<0, first, second> { enum {value = first}; };

};
struct SpecificFib
{
  template<int n> struct Eval { enum{ value = Fib::template Eval<n, 1, 2>::value }; };
};

template<int... values> struct Sequence {};
template<typename Seq, int n> struct Append;
template<int... values, int n> struct Append<Sequence<values...>, n> { typedef Sequence<values...,n> type; };
template<typename Seq, int n> struct Prepend;
template<int... values, int n> struct Prepend<Sequence<values...>, n> { typedef Sequence<n, values...> type; };

template<typename Func,typename Seq,typename Test=void> struct Filter;

template<typename Func,int first, int... values>
struct Filter<Func,Sequence<first,values...>,typename std::enable_if< Func::template Eval<first>::value>::type>
{
  typedef typename Prepend<typename Filter<Func,Sequence<values...>>::type,first>::type type;
};

template<typename Func,int first, int... values>
struct Filter<Func,Sequence<first,values...>,typename std::enable_if< !Func::template Eval<first>::value>::type>
{
  typedef typename Filter<Func,Sequence<values...>>::type type;
};
template<typename Func> struct Filter<Func,Sequence<>> { typedef Sequence<> type; };

struct IsEven {
  template<int n> struct Eval { enum{ value = !(n%2) }; };
};

template<typename Func,typename Seq> struct Map;
template<typename Func,int first, int... values>
struct Map<Func, Sequence<first,values...>>
{
  typedef Sequence<values...> Tail;
  typedef typename Map<Func,Tail>::type TailMapped;
  enum { firstMapped = Func::template Eval<first>::value };

  typedef typename Prepend<TailMapped,firstMapped>::type type;
};
template<typename Func>
struct Map<Func,Sequence<>>
{
  typedef Sequence<> type;
};

template<int begin, int end>
struct generate_sequence
{
  template<int current, int... values>
  struct helper: helper<current-1, current-1, values...> {};
  template<int... values>
  struct helper<begin, values...>
  {
    typedef Sequence<values...> type;
  };
  typedef typename helper<end>::type type;
};
template<typename Seq> struct Sum;
template<int first, int... values> struct Sum<Sequence<first, values...>> { enum {value = first + Sum<Sequence<values...>>::value}; };
template<> struct Sum<Sequence<>> { enum {value = 0}; };

template<typename Seq1, typename Seq2=Sequence<>>
struct Reverse { typedef Seq2 type; };

template<int first, int... values, typename Seq2>
struct Reverse<Sequence<first,values...>, Seq2>:Reverse<Sequence<values...>, typename Prepend<Seq2,first>::type> {};

template<typename Seq, char sep=','> struct PrintHelper;
template<int first, int second, int... values, char sep> struct PrintHelper<Sequence<first,second,values...>, sep>:PrintHelper<Sequence<second,values...>, sep>
{
  PrintHelper() { std::cout << sep << first; }
};
template<int last, char sep> struct PrintHelper<Sequence<last>, sep>:PrintHelper<Sequence<>, sep>
{
  PrintHelper() { std::cout << last; }
};
template<char sep> struct PrintHelper<Sequence<>,sep> { PrintHelper() {} void Do() const {} };
template<typename Seq, char sep=','> struct Print: PrintHelper< typename Reverse<Seq>::type, sep >
{};

typedef typename generate_sequence<0, 10>::type ZeroTo9;
typedef typename Map<SpecificFib,ZeroTo9>::type First10Fibs;
typedef typename Filter<IsEven,First10Fibs>::type First10FibsThatAreEven;

template<typename Sequence>
void PrintSomeInfo( std::string const& name )
{
  std::cout << name << " {";
  Print<Sequence>();
  std::cout << "} sums to " << Sum<Sequence>::value << "\n";
}
int main()
{
  PrintSomeInfo<ZeroTo9>("Zero to 9");
  PrintSomeInfo<First10Fibs>("First 10 fibs");
  PrintSomeInfo<First10FibsThatAreEven>("First 10 fibs that are even");
}

我希望有所帮助.

我上面正在做的是模板编程.我正在使用相当过于强大的C++类型系统来推断答案,这样如果编译器正确编译Sum<Sequence>::value,它将是单个编译时值.

从技术上讲,这是用C++编写的问题的答案.作为奖励,它将有O(1)运行时间.:)

...

更严重的是.您需要一步一步地解决您的问题.

编写一个程序,输出序列的前10个元素.我会说"像上面那样",但你应该以你理解的方式去做.