daily pastebin goal
66%
SHARE
TWEET

Untitled

a guest Jul 22nd, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstring>
  4.  
  5. #define MAX_M 10
  6. #define MAX_N 1000000
  7. #define VERBOSE false
  8.  
  9. // ------------------------------------------------------------
  10. // Ackermann sample with memoization technique for optimization
  11. // ------------------------------------------------------------
  12.  
  13. using namespace std;
  14.  
  15. int res[MAX_M][MAX_N];
  16. long long calls = 0;
  17. long long peakM = 0;
  18. long long peakN = 0;
  19. bool warned = false;
  20.  
  21. int ack(int m, int n) {
  22.  
  23.     if(!warned && (m > MAX_M-1 || n > MAX_N-1)) {
  24.         // the space allocated is not enough for memoization, fall back to recursion
  25.         warned = true;
  26.         cout << "\n\t:: YOU SHOULD INCREASE MAX_M OR MAX_N TO GET CORRECT RESULTS ::\n\n";
  27.     }
  28.     // memoization: return if previously calculated
  29.     else if(res[m][n] != -1) return res[m][n];
  30.  
  31.     if(VERBOSE){
  32.         calls++;
  33.         if(peakM < m) peakM = m;
  34.         if(peakN < n) peakN = n;
  35.     }
  36.  
  37.     int ans;
  38.  
  39.     if (m == 0)
  40.         ans = n + 1;
  41.     else if (n == 0)
  42.         ans = ack(m - 1, 1);
  43.     else
  44.         ans = ack(m - 1, ack(m, n - 1));
  45.  
  46.     res[m][n] = ans;        // save result
  47.     return ans;
  48. }
  49.  
  50. int main(int argc, char **argv) {
  51.  
  52.     // set whole memoization matrix to -1
  53.     memset(res, -1, sizeof(res[0][0]) * MAX_M * MAX_N);
  54.  
  55.     int i, j;
  56.     for (i = 0; i < 6; i++) {
  57.         for (j = 0; j < 6; j++) {
  58.             cout << "Ackermann(" << i << "," << j << ") = " << ack(i,j) << "\n";
  59.             if (VERBOSE) {
  60.                 cout << "\t" << calls << " calls, with max M=" << peakM << " and N=" << peakN << "\n\n";
  61.                 calls = 0;
  62.             }
  63.         }
  64.     }
  65.  
  66. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top