main.cpp

来自「一个我的数据结构解题集合」· C++ 代码 · 共 91 行

#include <stdexcept>
#include <iostream>
#include "Stack.h"
#include "IoUtils.h"

using namespace std;


/* 非递归Ackermann函数
 * 使用Stack来模拟递归
 * 参数m, n必须>=0
 */
long ack_stack(long m, long n) {
	if ( m < 0 || n < 0 )
		throw std::invalid_argument("ack_rec(int, int):\n"
									"\trequirement m>=0 && n>=0 violated.\n");

	Stack<long> argStack;		// 储存尚需计算的m值, n值可以直接计算, 无需储存

	while (true) {
		if ( m == 0 ) {
			if ( argStack.isEmpty() ) {		// 运算结束
				return ++n;
			}
			m = argStack.top();
			argStack.pop();
			++n;
		} else 
		if ( n == 0 ) {
			--m;
			n = 1;
		} else {
			argStack.push(m-1);
			--n;
		}
	}

} // ack_stack(long, long)


/* 递归的Ackermann函数
 * 参数m, n必须>=0
 */
long ack_rec(long m, long n) {
	if ( m < 0 || n < 0 )
		throw std::invalid_argument("ack_rec(int, int):\n"
									"\trequirement m>=0 && n>=0 violated.\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));
	}
	
} // ack_rec(long, long)


int main() {
	int noErrors = 0;

	cout << "输入两个任意正整数(m, n), 输出Ackermann(m, n)的值\n"
		 << "对于溢出不做特别处理\n"
		 << "\t注意: 由于Ackermann使用Stack模拟递归,\n"
		 << "\t      而非使用公式法求解 (Ackermann函数无法用初等函数非递归表示)\n"
		 << "\t      故当(m, n)较大时 (除了0,1,2,3都是比较大的)\n"
		 << "\t      计算可能需要较长时间, 并且可能导致内存不足!\n"
		 << endl;

	try {

		cout << "m = ";
		int m = getNonNegativeInteger();
		cout << "n = ";
		int n = getNonNegativeInteger();

		cout << "Ackermann(m, n) == " << ack_stack(m, n) << endl;

		pause();

	} catch (const std::exception& e) {
		cerr << "捕捉到异常!" << endl;
		cerr << e.what() << endl;
		++noErrors;
	}

	return noErrors;

} // main()