Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <cstring>
- #define MAX_M 10
- #define MAX_N 1000000
- #define VERBOSE false
- // ------------------------------------------------------------
- // Ackermann sample with memoization technique for optimization
- // ------------------------------------------------------------
- using namespace std;
- int res[MAX_M][MAX_N];
- long long calls = 0;
- long long peakM = 0;
- long long peakN = 0;
- bool warned = false;
- int ack(int m, int n) {
- if(!warned && (m > MAX_M-1 || n > MAX_N-1)) {
- // the space allocated is not enough for memoization, fall back to recursion
- warned = true;
- cout << "\n\t:: YOU SHOULD INCREASE MAX_M OR MAX_N TO GET CORRECT RESULTS ::\n\n";
- }
- // memoization: return if previously calculated
- else if(res[m][n] != -1) return res[m][n];
- if(VERBOSE){
- calls++;
- if(peakM < m) peakM = m;
- if(peakN < n) peakN = n;
- }
- int ans;
- if (m == 0)
- ans = n + 1;
- else if (n == 0)
- ans = ack(m - 1, 1);
- else
- ans = ack(m - 1, ack(m, n - 1));
- res[m][n] = ans; // save result
- return ans;
- }
- int main(int argc, char **argv) {
- // set whole memoization matrix to -1
- memset(res, -1, sizeof(res[0][0]) * MAX_M * MAX_N);
- int i, j;
- for (i = 0; i < 6; i++) {
- for (j = 0; j < 6; j++) {
- cout << "Ackermann(" << i << "," << j << ") = " << ack(i,j) << "\n";
- if (VERBOSE) {
- cout << "\t" << calls << " calls, with max M=" << peakM << " and N=" << peakN << "\n\n";
- calls = 0;
- }
- }
- }
- }
Add Comment
Please, Sign In to add comment