akm.cpp

这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本

#include <stack>
using namespace std;
typedef pair<int, int> StackNode;	// pair.first for m, and second for n
typedef stack<StackNode> NodeStack;	// Stack

/************************************************************************/
/* Non-recursive solution                                               */
/************************************************************************/
int akm(int m, int n)
{
	if ((m < 0) || (n < 0))	return 0;

	int ret;
	NodeStack s;

	/*
	 *	Push the first node when start to active the process.
	 */
	StackNode node(m, n);
	s.push(node);

	while (!s.empty())
	{
		m = s.top().first, n = s.top().second;
		if (0 == m)
		{
			/*
			 *	(1) akm(m, n) = n+1, if m == 0
			 *		Just pop stack.
			 */
			s.pop();
			ret = n+1;
			/*
			 *	NOTE: When stack is NOT empty, what should we do? SEE (3).
			 */
			if (!s.empty())
			{
				s.top().second = ret;
			}
		}
		else if (0 == n)
		{
			/*
			 *	(2) akm(m, n) = akm(m-1, 1), if m != 0 and n == 0
			 *      We need NOT push another node, just change the top one. Why?
			 */
			(s.top().first)--;
			s.top().second = 1;
		}
		else
		{
			/*
			 *	(3) akm(m, n) = akm(m-1, akm(m, n-1)), if m != 0 and n != 0
			 *		Change the top node and push another one. Why?
			 */
			(s.top().first)--;

			node.first = m, node.second = n-1;
			s.push(node);
		}
	}
	return ret;
}

/************************************************************************/
/* Recursive solution                                                   */
/************************************************************************/
int akm_recurve(int m, int n)
{
	if ((m < 0) || (n < 0))
	{
		return 0;
	}

	if (0 == m) 
	{
		return n+1;
	}
	else if (0 == n)
	{
		return akm_recurve(m-1, 1);
	}
	else
	{
		return akm_recurve(m-1, akm_recurve(m, n-1));
	}
}

int main(int argc, char* argv[])
{
	if (argc != 3)
	{
		printf("\nUsage: akm <m> <n>\n");
		return -1;
	}

	int m = atoi(argv[1]), n = atoi(argv[2]);
	printf("\nnon-recursive ret\t= %d", akm(m, n));
	printf("\nrecursive ret\t\t= %d\n", akm_recurve(m, n));
	return 0;
}