Advertisement
Guest User

Untitled

a guest
May 25th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.59 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement