fork download
copy 
  1. int arr[50];
  2.  
  3. int f(int a, int b=0) {
  4.    if (b==-1) return 1;
  5.    if (a==1) return 0;
  6.    if (a==2) return 2;
  7.    int r=f(a-2, arr[a-1]);
  8.    int l=f(a-1, arr[a-2]);
  9.    return (l+r);
  10. }
  11.  
  12. #include <vector>
  13. int f2(int a, int b=0) {
  14.    static std::vector<int> m(100, -1);
  15.    if (b==-1) return 1;
  16.    if (a==1) return 0;
  17.    if (a==2) return 2;
  18.    if (m.at(a) != -1) return m[a];
  19.    int r = f2(a-2, arr[a-1]);
  20.    int l = f2(a-1, arr[a-2]);
  21.    m[a] = l+r;
  22.    return l+r;
  23. }
  24.  
  25. #include <iostream>
  26. #include <ctime>
  27. int main() {
  28.    const int num_test = 42;
  29.  
  30.    clock_t begin = clock();
  31.    int s=0;
  32.    for(int i=1; i<num_test; ++i)
  33.       s += f(i);
  34.    clock_t diff = clock()-begin;
  35.    std::cout << s << ':' << double(diff)/CLOCKS_PER_SEC << '\n';
  36.  
  37.    begin = clock();
  38.    s=0;
  39.    for(int i=1; i<num_test; ++i)
  40.       s += f2(i);
  41.    diff = clock()-begin;
  42.    std::cout << s << ':' << double(diff)/CLOCKS_PER_SEC << '\n';
  43. }
Success #stdin #stdout 3.33s 3016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
535828590:3.33
535828590:0
https://ideone.com/hhmPVd
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!