SHARE
TWEET

Untitled

a guest May 25th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdint>
  2. #include <iostream>
  3. #include <list>
  4. #include <stack>
  5. #include <unordered_map>
  6.  
  7. using std::size_t;
  8.  
  9. size_t ack_rec(size_t m, size_t n)
  10. {
  11.     if (m == 0)
  12.         return n + 1;
  13.     else if (n == 0)
  14.         return ack_rec(m - 1, 1);
  15.     else
  16.         return ack_rec(m - 1, ack_rec(m, n - 1));
  17. }
  18.  
  19. size_t ack_stack(size_t m, size_t n)
  20. {
  21.     std::stack<size_t> args;
  22.     args.push(m);
  23.     args.push(n);
  24.     while(args.size() > 1) {
  25.         size_t n = args.top();
  26.         args.pop();
  27.         size_t m = args.top();
  28.         args.pop();
  29.         if (m == 0)
  30.             args.push(n + 1);
  31.         else if (n == 0) {
  32.             args.push(m - 1);
  33.             args.push(1);
  34.         } else {
  35.             args.push(m - 1);
  36.             args.push(m);
  37.             args.push(n - 1);
  38.         }
  39.     }
  40.     return args.top();
  41. }
  42.  
  43. namespace std
  44. {
  45. template<>
  46. class hash<std::pair<size_t, size_t>> {
  47.     size_t operator()(const std::pair<size_t, size_t>& x) const
  48.     {
  49.         return hash<size_t>()(x.first) ^ hash<size_t>()(x.second);
  50.     }
  51. };
  52. }
  53.  
  54. size_t ack_memo(size_t m, size_t n)
  55. {
  56.     static std::unordered_map<std::pair<size_t, size_t>, size_t> memo;
  57.     if (memo.count(std::pair<size_t, size_t>(m, n)) > 0)
  58.         return memo[std::pair<size_t, size_t>(m, n)];
  59.     else if (m == 0)
  60.         return n + 1;
  61.     else if (n == 0) {
  62.         size_t res = ack_memo(m - 1, 1);
  63.         memo.emplace(std::pair<size_t, size_t>(m, n), res);
  64.         return res;
  65.     } else {
  66.         size_t res = ack_memo(m - 1, ack_memo(m, n - 1));
  67.         memo.emplace(std::pair<size_t, size_t>(m, n), res);
  68.         return res;
  69.     }
  70. }
  71.  
  72. size_t ack_print(size_t m, size_t n)
  73. {
  74.     std::list<size_t> args({m, n});
  75.     std::cout << " A(" << m << "," << n << ")" << endl;
  76.     while(args.size() > 1) {
  77.         auto iter = args.rbegin();
  78.         size_t n = *iter, m = *(++iter);
  79.         args.pop_back(); args.pop_back();
  80.         if (m == 0)
  81.             args.push_back(n + 1);
  82.         else if (n == 0) {
  83.             args.push_back(m - 1);
  84.             args.push_back(1);
  85.         } else {
  86.             args.push_back(m - 1);
  87.             args.push_back(m);
  88.             args.push_back(n - 1);
  89.         }
  90.        
  91.         std::cout << "=";
  92.         auto it = args.begin();
  93.         for (int i = 0; i < args.size() - 1; ++i) {
  94.             std::cout << "A(" << *it << ",";
  95.             ++it;
  96.         }
  97.         std::cout << *it << std::string(args.size() - 1, ')') << std::endl;
  98.     }
  99.     return *(args.begin());
  100. }
  101.  
  102. int main()
  103. {
  104.     std::cout << ack_rec(3, 3) << std::endl
  105.               << ack_stack(3, 3) << std::endl
  106.               << ack_memo(3, 3) << std::endl;
  107.     ack_print(3, 3);
  108.     return 0;
  109. }
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