ackermann.cpp

此文件实现Ackerman函数的动态规划算法

#include<stdlib.h>
#include<stdio.h>
#define MAX 10

int A( int m,int n )
{
	int val[MAX];
	int ind[MAX];
	
	int i;			// 循环标记
	int depth = 0;		// 循环深度
	
	// val[i] 表示 已求解 A( i,val[i] ) 中 val[i] 的最大值 
	for (i = 0 ; i <= m ; i++) val[i] = -1 ;

	// initialize ind[],ind[i] = A( i,val[i] );
	for (i = 0 ; i <= m ; i++) ind[i] = 1 ;

	while( val[m] < n )					// 只要未达到边界,则继续 while-循环
	{
		ind[0] = ++depth ;				// 每循环一次 刷新 ind[]
		val[0] ++ ;						// 每循环一次 刷新 val[]				

		for ( i = 1 ; i <= m ; i++)
		{
			if ( val[i-1] >= ind[i] )		//  若已求得 val[i]
			{
				val[i] ++ ;						// val[i] 步进
				ind[i] = depth ;				// 结果记入 ind[]
			}
			else break ;					// 若为求得，则退出循环
		}
	}	
	return ind[m];	                    // 到达循环边界，输出结果
}

int main()
{	
	int j,k;

	for( j = 0;j < 5;j++ )
	{
		if(j==0)     
		{
			printf( "A(m,n)" );
			for( k=0;k<9;k++ )
				printf( "    n=%d",k );
			printf("\n");
		}

		printf( "   m=%d",j );
		for( k=0;k<9;k++ )
		{
			if( j==4 && k==2  )		break;
			printf( "%7d",A(j,k) );
		}
		printf("\n");
	}
	getchar();
	return 0;
}