IT虾米网

汉诺塔-递归实现详解

qq123 2019年05月10日 编程语言 487 0

汉诺塔(Hanoi)

        汉诺塔,又叫河内塔,是源于印度古代的一个传说。传说神在创造世界的时候做了三根金刚石柱子,并在一个教塔里留下了三根金刚石棒,第一根上面从上到下套着64个按从小到大排列的金盘,神命令庙里的众僧将它们一个个地从这根金刚石棒搬到另一根金刚石棒上,大盘不能放在小盘上。最后64个金盘仍然要按从小到大排列。如下图所示:

           

C语言

#include <iostream> 
using namespace std;  
template<int n>                                 
void hanoi(char a, char b, char c){ 
    hanoi<n - 1>(a, c, b); 
    printf("%c -> %c\n", a, c); 
    hanoi<n - 1>(b, a, c); 
} 
template<> 
void hanoi<1>(char a, char b, char c){ 
    printf("%c -> %c\n", a, c); 
} 
//////////////////////////////////////////////// 
template<int n, char a, char b, char c>     
class hanoi1{ 
public: 
    static int hanoi(){ 
        hanoi1<n-1, a, c, b>::hanoi(); 
        printf("%c -> %c\n", a, c); 
        hanoi1<n-1, b, a, c>::hanoi(); 
    } 
}; 
template<char a, char b, char c> 
class hanoi1<1, a, b ,c>{ 
public: 
    static int hanoi(){ 
        printf("%c -> %c\n", a, c); 
    } 
}; 
int main(){  
    #define N 4 
    cout<<"类模板偏特化:"; 
    hanoi1<N,'A','B','C'>::hanoi(); 
    cout<<endl; 
      
    cout<<"函数模板全特化:"; 
    hanoi<3>('A','B','C');  
    exit(0); 
}

Java

public class Hanoi { 
    /** 
    *  
    * @param n 盘子的数目 
    * @param origin 源座 
    * @param assist 辅助座 
    * @param destination 目的座 
    */ 
    public void hanoi(int n, char origin, char assist, char destination) { 
        if (n == 1) { 
            move(origin, destination); 
        } else { 
            hanoi(n - 1, origin, destination, assist); 
            move(origin, destination); 
            hanoi(n - 1, assist, origin, destination); 
        } 
    } 
  
    // Print the route of the movement 
    private void move(char origin, char destination) { 
        System.out.println("Direction:" + origin + "--->" + destination); 
    } 
  
    public static void main(String[] args) { 
        Hanoi hanoi = new Hanoi(); 
        hanoi.hanoi(3, 'A', 'B', 'C'); 
    } 
}

C#

using System; 
  
class HANOI 
{ 
    private static int time = 0; 
  
    static void Main(string[] args) 
    { 
        Hanoi(3, "x", "y", "z"); 
        Console.WriteLine(time + " Times"); 
        Console.ReadKey(); 
    } 
  
    public static void Hanoi(int n, string x, string y, string z) 
    { 
        if (n == 1) 
        { 
            Console.WriteLine(x + "--->" + z); 
            time++; 
        } 
        else 
        { 
            Hanoi(n - 1, x, z, y); 
            Hanoi(1, x, y, z); 
            Hanoi(n - 1, y, x, z); 
        } 
    } 
}

JavaScript

var hanoi=function(n,from,ass,to){ 
  if(n>0){ 
    hanoi(n-1,from,to,ass); 
    move(n,from,to); 
    hanoi(n-1,ass,from,to); 
  } 
} 
var move=function(n,from,to){ 
 console.log("移动第"+n+"个从"+from+"到"+to); 
} 
hanoi(3,"A","B","C");

 

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

汉诺塔-问题详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。