• API
• FAQ
• Tools
• Archive
daily pastebin goal
36%
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.

Top