技术,瞎侃,健康,休闲……

mahu@cppblog 人类的全部才能无非是时间和耐心的混合物
posts - 11, comments - 13, trackbacks - 0, articles - 12
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

两个汉诺塔解法

Posted on 2006-06-29 22:07 mahudu@cppblog 阅读(579) 评论(2)  编辑 收藏 引用 所属分类: 数据结构、算法

第一个是递归版本的:(没什么意思)

 

#include  < iostream >     
using   namespace  std; 

void  move( char  from,  char  to) 

    cout 
<<  from  <<   "  to  "   <<  to  <<  endl; 
}
 

void  hanoi ( int  n,  char  from,  char  to,  char  bridge) 

    
if (n  ==   1
        move(from, to); 
    
else  
    

        hanoi (n
- 1 , from, bridge, to); 
        move(from ,bridge); 
        hanoi (n
- 1 , bridge, from, to); 
    }
 
}
 

int  main() 

    
int  n; 
     cout 
<<   " input n:\n "
     cin 
>>  n; 
     hanoi (n, 
' A ' ' C ' ' B ' ); 
    
return   0
}
 

 

 

第二个是递归版本的:(没有用栈,因此还比较精妙)

对不起,由于一时疏忽,把两个版本的程序贴成同一个了,十分抱歉,谢谢您的提醒,现更正如下:

#include  < iostream >
using   namespace  std;

void  hanoi( int  n)
{
     
int  i, j, f  =   1 ;
     
int  a  =   1 , b  =  (n % 2 ) ?   3 : 2 ;
     cout 
<<  f  <<   "  from  "   <<   char ( ' A '   -   1   +  a)  <<   "  to  "   
                << char('A' - 1 + b) << endl;
     
for(n = (1<<n) - 1, i = 1; i < n; i += 2)
     
{
           
for(f = 1, j = i; j%2; j/=2, f++);
           
if(f%2)
                  a 
^= b;
           b 
^= a;
           cout 
<< f << " from " << char('A' - 1 + a) << " to "  
                      << char('A' - 1 + b) << endl;
           a 
^= b;
           
if(f%2)
                  b 
^= a;
           cout 
<< f << " from " << char('A' - 1 + a) << " to "  
                    
 << char('A' - 1 + b) << endl;
     }

}


int  main()
{
    
int  n;
    cout 
<<   " input n:  " ;
    cin 
>>  n;
    hanoi(n);

    
return   0 ;
}


 

Feedback

# re: 两个汉诺塔解法  回复  更多评论   

2006-07-04 13:55 by 零碎宇
两个版本貌似一样,请指教

# re: 两个汉诺塔解法  回复  更多评论   

2010-03-30 21:43 by 4525
版本吧 vcbf

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理