thap ha noi

Slide 1: 

GIẢI THUẬT BÀI TOÁN THÁP HÀ NỘI  Sinh viên thực hiện: Trần Huy Hoàng

Slide 2: 

Lịch sử bài toán Tháp Hà Nội Có thể còn ít người Việt Nam biết Tháp Hà Nội, nhưng rất nhiều thanh niên sinh viên trên toàn thế giới lại biết đến nó. Đó là vì, Tháp Hà Nội là tên một bài toán rất nổi tiếng trong Chương trình khoa học tính toán (Computing Science) dành cho sinh viên những năm đầu tại các trường đại học ở nhiều nơi trên thế giới. Tương truyền rằng ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi viễn đông, thành phố Hà Nội của Việt Nam, vị quân sư của Hoàng đế vừa qua đời, Hoàng đế cần một vị quân sư mới thay thế. Bản thân Hoàng đế cũng là một nhà thông thái, nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ được phong làm quân sư. Bài toán của Hoàng đế là: cho n cái đĩa (ngài không nói chính xác là bao nhiêu) và ba cái trục: A là trục nguồn, B là trục đích, và C là trục trung chuyển. Những cái đĩa có kích cỡ khác nhau và có lỗ ở giữa để có thể lồng vào trục, theo quy định "nhỏ trên lớn dưới". Đầu tiên, những cái đĩa này được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ các đĩa sang trục B, với điều kiện chuyển từng cái một và luôn phải đảm bảo quy định "nhỏ trên lớn dưới", biết rằng trục C được phép sử dụng làm trục trung chuyển? Từ đó bài toán (Trò chơi) Tháp Hà Nội ra đời và được người đời sau truyền bá rộng rãi.

Slide 3: 

Khái quát về bài toán Tháp Hà Nội hay trò chơi Tháp Hà Nội:Dạng thường gặp nhất của bài toán 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 (cột). 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.

Slide 4: 

Nội dung & quy luật của bài toán Tháp Hà Nội: + Một lần chỉ được di chuyển một đĩ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. + Thứ tự và vị trí đĩa ở cột đích phải giống với thứ tự và vị trí đĩa ở cột nguồn. Minh họa:

Slide 5: 

4 3 2 1 THUẬT GIẢI ĐỆ QUY + Đặt tên các cột là I, II, III -- những tên này có thể chuyển ở các bước khác nhau (Quy ước: I - là Cột Nguồn, II - là Cột Đích, III - là Cột Trung gian) + Gọi n là tổng số đĩa đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng) Minh họa:

Slide 6: 

Để chuyển n đĩa từ Cột I sang Cột II thì cần: Bước 1: Chuyển n-1 đĩa từ Cột I (khởi đầu) sang Cột III (trung gian). Chỉ còn lại đĩa có giá trị bằng n trên Cột I. Bước 2: Chuyển đĩa có giá trị bằng n (lớn nhất) từ Cột I sang Cột II. Bước 3: Chuyển n-1 đĩa từ Cột III sang Cột II cho chúng nằm trên đĩa có giá trị n. Phương pháp trên được gọi là thuật giải đệ quy: để tiến hành bước 1 và 3, áp dụng lại thuật giải cho n-1. Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ áp dụng cho n = 1. Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ Cột I sang Cột III. 3 2 1

Slide 7: 

4 3 2 1 Đối với 4 đĩa cũng thực hiện theo các bước & với n đĩa cũng làm tương tự như vậy Đã sắp xếp 4 đĩa về cột đích theo đúng quy tắc !

Slide 8: 

/* Chuong trinh bai toan Thap Ha Noi */ #include<stdio.h> #include<conio.h> //Khai bao 3 bien tuong ung 3 cot. void dichuyen(int n, int cot1, int cot2, int cot3) { if(n==1) printf("\n\tCot %d -> Cot %d\n", cot1, cot2); else { dichuyen(n-1, cot1, cot3, cot2); dichuyen(1, cot1, cot2, cot3); dichuyen(n-1, cot3, cot2, cot1); } } Dưới đây là đoạn Code chương trình Tháp Hà Nội Bước 1: Chuyển n-1 đĩa từ Cột I (khởi đầu) sang Cột III (trung gian). Chỉ còn lại đĩa có giá trị bằng n trên cột I. Bước 2: Chuyển đĩa có giá trị bằng n (lớn nhất) từ Cột I sang Côt II. Bước 3: Chuyển n-1 đĩa từ Cột III sang Cột II cho chúng nằm trên đĩa có giá trị n.

Slide 9: 

void main() //Ham chinh { clrscr(); int n, cot1=1, cot2=2, cot3=3; printf("Nhap vao so dia can sap xep: "); scanf("%d",&n); dichuyen(n, cot1, cot2, cot3); getch(); }

Slide 10: 

#include<stdio.h> #include<conio.h> void dichuyen(int n, int cot1, int cot2, int cot3) { if(n==1) printf("\n\tCot %d -> Cot %d\n", cot1, cot2); else { dichuyen(n-1, cot1, cot3, cot2); dichuyen(1, cot1, cot2, cot3); dichuyen(n-1, cot3, cot2, cot1); } } void main() { clrscr(); int n, cot1=1, cot2=2, cot3=3; printf("Nhap vao so dia can sap xep: "); scanf("%d",&n); dichuyen(n, cot1, cot2, cot3); getch(); } Đoạn Code chương trình hoàn chỉnh

Slide 11: 

CẢM ƠN QUÝ THẦY CÔ VÀ CÁC BẠN ĐÃ THEO DÕI PHẦN THUYẾT TRÌNH !