Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdint>
- #include <iostream>
- #include <list>
- #include <stack>
- #include <unordered_map>
- using std::size_t;
- size_t ack_rec(size_t m, size_t n)
- {
- if (m == 0)
- return n + 1;
- else if (n == 0)
- return ack_rec(m - 1, 1);
- else
- return ack_rec(m - 1, ack_rec(m, n - 1));
- }
- size_t ack_stack(size_t m, size_t n)
- {
- std::stack<size_t> args;
- args.push(m);
- args.push(n);
- while(args.size() > 1) {
- size_t n = args.top();
- args.pop();
- size_t m = args.top();
- args.pop();
- if (m == 0)
- args.push(n + 1);
- else if (n == 0) {
- args.push(m - 1);
- args.push(1);
- } else {
- args.push(m - 1);
- args.push(m);
- args.push(n - 1);
- }
- }
- return args.top();
- }
- namespace std
- {
- template<>
- class hash<std::pair<size_t, size_t>> {
- size_t operator()(const std::pair<size_t, size_t>& x) const
- {
- return hash<size_t>()(x.first) ^ hash<size_t>()(x.second);
- }
- };
- }
- size_t ack_memo(size_t m, size_t n)
- {
- static std::unordered_map<std::pair<size_t, size_t>, size_t> memo;
- if (memo.count(std::pair<size_t, size_t>(m, n)) > 0)
- return memo[std::pair<size_t, size_t>(m, n)];
- else if (m == 0)
- return n + 1;
- else if (n == 0) {
- size_t res = ack_memo(m - 1, 1);
- memo.emplace(std::pair<size_t, size_t>(m, n), res);
- return res;
- } else {
- size_t res = ack_memo(m - 1, ack_memo(m, n - 1));
- memo.emplace(std::pair<size_t, size_t>(m, n), res);
- return res;
- }
- }
- size_t ack_print(size_t m, size_t n)
- {
- std::list<size_t> args({m, n});
- std::cout << " A(" << m << "," << n << ")" << endl;
- while(args.size() > 1) {
- auto iter = args.rbegin();
- size_t n = *iter, m = *(++iter);
- args.pop_back(); args.pop_back();
- if (m == 0)
- args.push_back(n + 1);
- else if (n == 0) {
- args.push_back(m - 1);
- args.push_back(1);
- } else {
- args.push_back(m - 1);
- args.push_back(m);
- args.push_back(n - 1);
- }
- std::cout << "=";
- auto it = args.begin();
- for (int i = 0; i < args.size() - 1; ++i) {
- std::cout << "A(" << *it << ",";
- ++it;
- }
- std::cout << *it << std::string(args.size() - 1, ')') << std::endl;
- }
- return *(args.begin());
- }
- int main()
- {
- std::cout << ack_rec(3, 3) << std::endl
- << ack_stack(3, 3) << std::endl
- << ack_memo(3, 3) << std::endl;
- ack_print(3, 3);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement