MÔ PHỎNG GIẢI BÀI THÁP HANOI
2.1 GIỚI THIỆU :
Tháp Hà Nội là một từ được biết đến nhiều trên thế giới, vì nó được biết là một trò chơi được phát minh bởi nhà toán học Edouard Lucas. Mặc dù trong khoảng 10 năm từ 1883 đến 1891, trong các báo và sách, E. Lucas đã chỉ ra sự thú vị và quan trọng của bài toán này cũng như mối quan hệ của nó trong các lĩnh vực khác (dãy truy hồi, lí thuyết đồ thị, hệ đếm cơ số 2, ...) bài toán tháp Hà Nội được xem là bài toán căn bản có nội dung toán học và là bài mở đầu cho người học lập trình.
Bài toán Tháp Hà Nội cổ điển:
Cho 3 cột A, B, C với cột A chứa 3 đĩa. Thuật toán: Chuyển đĩa số 1 từ cột A sang cột B, chuyển đĩa số 2 sang cột C, chuyển đĩa số 1 từ cột B sang cột C. Khi ấy đĩa số 1 nằm trên đĩa số 2, cọc B trống. Chuyển đĩa số 3 từ cột A sang cột B. Lặp lại ba bước trên để giải bài toán cho 2 đĩa: chuyển đĩa số 1 và 2 cho nằm lên trên đĩa số 3 trên cột B Tiếp tục làm như vậy cho trường hợp 4, 5, 6, … đĩa
2.2 CÁCH THỨC THỰC HIỆN:
Nhiều cách giải đã được phát triển trong bài toán tháp Hà Nội. Ở đây giới thiệu một cách giải thực tế.
Lần lượt di chuyển đĩa 1 và một trong những đĩa lớn hơn. Nếu có hai đĩa lớn hơn thì phải chuyển đĩa nhỏ lên đĩa lớn. Khi chuyển một đĩa số lẻ, luôn chuyển nó một cọc theo chiều kim đồng hồ; khi chuyển một đĩa số chẵn, luôn chuyển nó một cọc ngược chiều kim đồng hồ.Một cách dễ hơn để nhớ cách giải là chú ý đĩa nhỏ nhất sẽ được chuyển mỗi lần di chuyển thứ hai, và luôn được chuyển theo cùng chiều. Trong các lần chuyển đĩa nhỏ nhất, chỉ có một lần chuyển hợp lệ mà không phải chuyển đĩa nhỏ nhất thêm một lần nữa.
2.3 QUY TRÌNH:
Chương trình áp dụng giải thuật AKT, mội trạng thái được mô tả bằng mảng hai chiều. Để ước lượng đối với trạng thái của trò chơi, ta sẽ tính trạng thái của cột thứ ba. Tại một trạng thái, thì số bước để đưa cột thứ ba về đúng như trạng thái đích là bao nhiêu? Ta thấy tại một trạng thái của cột thứ ba thì có một số đĩa nằm đúng vị trí của nó, và cũng có một số đĩa không nằm đúng vị trí của nó. Số lượt để ta có thể đưa cột thứ ba về đúng trạng thái đích bằng tổng số lượt mang những đĩa không đúng vị trí ra khỏi cột thứ ba cộng với số lượt mang những đĩa còn lại vào cho đúng vị trí của nó trong cột thứ ba.
Mặc dù thuật giải tương đối đơn giản, bài toán với n đĩa sẽ cần ít nhất 2n-1 lần di chuyển. Tuy nhiên với số lượng Cọc nhiều hơn 3 thì vẫn chưa biết được sẽ cần ít nhất bao nhiêu lần di chuyển để giải bài toán. Do vậy việc áp dụng bước tiến dãy (tiếng Anh sequential advancement) để xác định vị trí của một số lượng lớn các đĩa trên ba cọc sau một số lớn tuỳ ý các bước tiến là không thực tế. Lời giải tối ưu cho bài toán Tháp Hà Nội với bốn cọc hay nhiều hơn vẫn còn là một bài toán mở
Chỉ được di chuyển đĩa nằm trên cùng (không được di chuyển các đĩa nằm giữa).Đĩa có kích thước lớn hơn không thể được đặt trên đĩa có kích thước nhỏ hơn.
XEM THÊM ==> Hướng dẫn cài đặt chi tiết
HƯỚNG DẪN CÀI ĐẶT
Thắc mắc gì các bạn liên hệ gmail để được hỗ trợ thêm...
Nguồn: Topcode.vn
