Bài toán tháp Hà Nội code C/Cpp Java Python PHP JavaScript

1. Giới thiệu bài toán

Là một trong những bài toán kinh điển dành cho lập trình viên. Tất cả các lập trình viên chuyên nghiệp đề bắt buộc phải biết. Đó là bài toán “tháp Hà Nội”

Tower of Hanoi.gif
Bởi André Karwath aka AkaTác phẩm do chính người tải lên tạo ra, CC BY-SA 2.5, Liên kết

Theo Wikipedia: Tháp Hà Nội là một trò chơi toán học với luật chơi như sau:

Dạng thường gặp nhất của trò chơi này gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Yêu cầu của trò chơi là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:

  • Chỉ có 3 cột để di chuyển.
  • Một lần chỉ được di chuyển một đĩa (không được di chuyển đĩa nằm giữa).
  • Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất).

Tower of Hanoi.jpeg
CC BY-SA 3.0, Liên kết

Đây là một bài toán kinh điển, có nhiều cách giải, cách thông dụng nhất là dùng đệ quy. Chính vì lý do đó, Tháp Hà Nội thường được nhiều ngôn ngữ lấy nó để làm ví cho khả năng hỗ trợ đệ quy của mình.

2. Mã giả (Pseudo code):

void hanoi(n, a, b, c){ // chuyển n đĩa từ a -> c
    if n == 1 {
        print "chuyển từ" a "sang" b 
    } else {
        hanoi(n-1, a, c, b) // chuyển n - 1 đĩa từ a -> b
        hanoi(1, a, b, c) // chuyển đĩa thứ n từ a -> c
        hanoi(n-1, b, a, c) // chuyển n - 1 đĩa từ b -> c
    }
}

3. C/CPP:

a) C

#include<stdio.h>
void
hanoi (int n, char a, char b, char c)
{
  if (n == 1)
    {
      printf ("chuyen tu %c sang %c\n", a, c);
    }
  else
    {
      hanoi (n - 1, a, c, b);
      hanoi (1, a, b, c);
      hanoi (n - 1, b, a, c);
    }
}

int
main ()
{
  char a = 'A', b = 'B', c = 'C';
  int n;
  printf ("Nhap n: ");
  scanf ("%d", &n);
  hanoi (n, a, b, c);
}

b) CPP

#include<iostream>
using namespace std;
void
hanoi (int n, char a, char b, char c)
{
  if (n == 1)
    {
      cout << "chuyen tu " << a << " sang " << c << endl;
    }
  else
    {
      hanoi (n - 1, a, c, b);
      hanoi (1, a, b, c);
      hanoi (n - 1, b, a, c);
    }
};

int
main ()
{
  char a = 'A', b = 'B', c = 'C';
  int n;
  cout << "Nhap n: ";
  cin >> n;
  hanoi (n, a, b, c);
}

4. JAVA:

public class Main
{

  public static void hanoi (int n, char a, char b, char c)
  {
    if (n == 1)
      {
	System.out.println ("chuyen tu " + a + " sang " + c);
      }
    else
      {
	hanoi (n - 1, a, c, b);
	hanoi (1, a, b, c);
	hanoi (n - 1, a, b, c);
      }
  }

  public static void main (String[]args)
  {
    int n = 3;
    hanoi (n, 'A', 'B', 'C');
  }
}

5. Python:

def hanoi(n, a, b, c):
    if n == 1:
        print("chuyen tu", a, "sang", c)
    else:
        hanoi(n-1, a, c, b)
        hanoi(1, a, b, c)
        hanoi(n-1, b, a, c)


n = int(input("Nhap n: "))
hanoi(n, "A", "B", "C")

6. PHP

<?php
function hanoi ($n, $a, $b, $c)
{
  if ($n == 1)
    {
      print "chuyen tu $a sang $c\n";
    }
  else
    {
      hanoi ($n - 1, $a, $c, $b);
      hanoi (1, $a, $b, $c);
      hanoi ($n - 1, $b, $a, $c);
    }
}

hanoi (3, "A", "B", "C");
?>

7. JAVASCRIPT

function
hanoi (n, a, b, c)
{
  if (n == 1)
    {
      console.log ("chuyen tu " + a + " sang " + b);
    }
  else
    {
      hanoi (n - 1, a, c, b);
      hanoi (1, a, b, c);
      hanoi (n - 1, b, a, c);
    }
}

hanoi (3, "A", "B", "C");
Share