C++ HW9-2 for WallPower

使用動態記憶體，計算費氏數列，並與未使用動態記憶的比較時間。
執行結果如下。

參考答案。

#include <iostream>
#include <time.h>
using namespace std;
 
long long fib(long long n);
long long fib2(long long n);
long long num;
long long *temp;
 
int main()
{
 cout << "請輸入n值";
 cin >> num;
 double START, END;
 START = clock();                                    //前置time.h start紀錄開啟時間 
 temp = new long long[num];                          //將temp設成一陣列要求num個整數記憶體空間用int 輸出超過 2147483647 會出問題  
              //大概在輸入46~48之間 改成long long 可以存15位數...
 for (int i = 0; i < num; i++)                       //清除記憶體資料為0 
  *(temp + i) = 0;
 cout << fib(num - 1) << endl;
 delete temp;                                         //釋放記憶體空間 
 END = clock();                                      //程式結束的時間 可以把這個程式代進普通沒用記憶體儲存的遞迴 可以看時間差多少  
 cout << (END - START) << "ms" << endl;              //計算作業時間 
 
 START = clock();                                    //普通費氏 
 cout << fib2(num - 1) << endl;
 END = clock();
 cout << (END - START) << "ms" << endl;
 
 system("pause");
 return 0;
}
 
long long fib(long long n)                          //費氏記憶體遞迴 
{
 if (*(temp + n) != 0)                              //記憶體內如果有先前資料 回傳使用 (不用再跑一次1+1 2+1 3+2...) 
  return *(temp + n);
 if (n == 0 || n == 1)                               //temp陣列第一數第二數為1 回傳1 
 {
  *temp = 1;
  *(temp + 1) = 1;
  return 1;
 }
 return *(temp + n) = fib(n - 1) + fib(n - 2);       //如果記憶體內無資料 重新算一次儲存並回傳  
}
 
long long fib2(long long n)                          //普通費氏遞迴 其實沒有long long的必要 但我懶的改 
{
 if (n == 0 || n == 1)
  return 1;
 else
  return fib2(n - 1) + fib2(n - 2);
}