Chinaunix首页 | 论坛 | 博客
  • 博客访问: 194526
  • 博文数量: 44
  • 博客积分: 1515
  • 博客等级: 上尉
  • 技术积分: 480
  • 用 户 组: 普通用户
  • 注册时间: 2007-11-06 16:39
文章分类

全部博文(44)

文章存档

2013年(3)

2012年(2)

2011年(2)

2009年(20)

2008年(17)

我的朋友

分类: C/C++

2009-01-18 19:41:56

//use recruve ,it's easy
int akm_recu( int m, int n )
{
    if( 0 == m )
        return n + 1;
    else if( 0 == n )
        return akm_recu( m - 1, 1 );
    else
        return akm_recu( m - 1, akm_recu( m, n - 1 ) );
};


// not recurve aalgorithms  for ackerman funcition
// use three stack .
// when calc acm( 3,10 ) it take a long time
#define EXISTPARAM 1
#define NOTEXISTPARAM 0
int akm_nrecu( int m, int n )
{
    int ret = 0;
    int ParamM = 0;
    int ParamN = 0;
    int ParamFlag = 0;

    StackPQ stack_m;
    StackPQ stack_n;
    StackPQ  stack_flag;

    stack_m.Push( m );
    stack_n.Push( n );
    stack_flag.Push( EXISTPARAM );

    while( !stack_m.IsEmpty( ) && !stack_n.IsEmpty( ) ) {
        
        ParamM = stack_m.Pop( );
        ParamN = stack_n.Pop( );
        ParamFlag = stack_flag.Pop( );
       
        if( EXISTPARAM == ParamFlag ) {
            if( 0 == ParamM )
                ret = ParamN + 1;
            else if( 0 == ParamN ) {
                stack_m.Push( ParamM - 1 );
                stack_n.Push( 1 );
                stack_flag.Push( EXISTPARAM );
               
            }
            else {
                stack_m.Push( ParamM - 1 );
                stack_n.Push( 0 );
                stack_flag.Push( NOTEXISTPARAM );
               
                stack_m.Push( ParamM );
                stack_n.Push( ParamN - 1 );
                stack_flag.Push( EXISTPARAM );
               
            }
        }
        else {
            stack_m.Push( ParamM );
            stack_n.Push( ret );
            stack_flag.Push( EXISTPARAM );
           
        }
    }

    return ret;
}
阅读(862) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~