Ai biết code sử dụng giải thuật AKT để giải bài toán tháp Hanoi không ạ
Các em còn nhớ bài toán này chứ? Chúng ta có ba cọc A, B, C và một số đĩa có kích thước khác nhau được xếp chồng lên nhau theo thứ tự từ lớn nhất ở dưới cùng đến nhỏ nhất ở trên cùng trên cọc A. Nhiệm vụ của chúng ta là di chuyển toàn bộ chồng đĩa này sang cọc C, tuân thủ hai quy tắc sau:
1. Chỉ được di chuyển từng đĩa một.
2. Không được đặt một đĩa lớn hơn lên trên một đĩa nhỏ hơn.
Các em có thể hình dung ra bài toán rồi đúng không nào?
Trong sách giáo khoa Tin học lớp 12 của chúng ta, bài toán này thường được giải bằng phương pháp đệ quy. Phương pháp này rất hiệu quả và thể hiện rõ tư duy giải quyết vấn đề theo từng bước nhỏ.
Bây giờ, chúng ta sẽ đi vào chi tiết cách giải bằng đệ quy nhé.
Chúng ta sẽ định nghĩa một hàm, ví dụ gọi là \(ThapHanoi(n, nguon, dich, trung_gian)\).
Ở đây:
* \(n\) là số lượng đĩa cần di chuyển.
* \(nguon\) là cọc chứa đĩa ban đầu.
* \(dich\) là cọc đích mà chúng ta muốn chuyển đĩa đến.
* \(trung_gian\) là cọc tạm thời để hỗ trợ việc di chuyển.
Bây giờ, chúng ta sẽ xem xét từng bước của giải thuật đệ quy này.
Trường hợp cơ sở (điều kiện dừng của đệ quy):
Nếu \(n\) bằng 0 (tức là không có đĩa nào cần di chuyển), thì chúng ta không làm gì cả. Hàm kết thúc.
Bước đệ quy:
Nếu \(n\) lớn hơn 0, chúng ta thực hiện các bước sau:
1. Di chuyển \(n-1\) đĩa từ cọc \(nguon\) sang cọc \(trung_gian\): Để làm được điều này, chúng ta gọi lại hàm \(ThapHanoi\) với các tham số mới:
\(ThapHanoi(n-1, nguon, trung_gian, dich)\)
Các em thấy không, ở bước này, cọc đích ban đầu (\(dich\)) bây giờ lại trở thành cọc trung gian, và cọc trung gian ban đầu (\(trung_gian\)) lại trở thành cọc đích.
2. Di chuyển đĩa thứ \(n\) (đĩa lớn nhất trong số \(n\) đĩa) từ cọc \(nguon\) sang cọc \(dich\): Đây là bước di chuyển thực tế mà chúng ta muốn thực hiện. Trong mã giả, chúng ta sẽ ghi là “Di chuyển đĩa \(n\) từ \(nguon\) sang \(dich\)”.
3. Di chuyển \(n-1\) đĩa từ cọc \(trung_gian\) sang cọc \(dich\): Sau khi đĩa lớn nhất đã được đặt sang cọc đích, chúng ta cần di chuyển \(n-1\) đĩa vừa rồi đã đặt tạm thời ở cọc \(trung_gian\) sang cọc \(dich\). Chúng ta lại gọi hàm \(ThapHanoi\) với các tham số:
\(ThapHanoi(n-1, trung_gian, dich, nguon)\)
Ở bước này, cọc trung gian ban đầu (\(trung_gian\)) trở thành cọc nguồn, cọc đích ban đầu (\(dich\)) vẫn là cọc đích, và cọc nguồn ban đầu (\(nguon\)) trở thành cọc trung gian.
Như vậy, mỗi lần gọi đệ quy, chúng ta lại giảm \(n\) đi 1, cho đến khi \(n\) bằng 0 thì dừng lại.
Các em có thể lấy ví dụ với 3 đĩa để thử phân tích nhé.
Cô sẽ viết mã giả cho các em dễ hình dung hơn:
FUNCTION ThapHanoi(n, nguon, dich, trung_gian):
IF n > 0 THEN
// Bước 1: Di chuyển n-1 đĩa từ nguon sang trung_gian, sử dụng dich làm trung gian
ThapHanoi(n-1, nguon, trung_gian, dich)
// Bước 2: Di chuyển đĩa thứ n từ nguon sang dich
PRINT “Di chuyển đĩa ” + n + ” từ cọc ” + nguon + ” sang cọc ” + dich
// Bước 3: Di chuyển n-1 đĩa từ trung_gian sang dich, sử dụng nguon làm trung gian
ThapHanoi(n-1, trung_gian, dich, nguon)
END IF
END FUNCTION
Để gọi hàm này cho bài toán ban đầu, ví dụ có 3 đĩa, chúng ta sẽ gọi:
\(ThapHanoi(3, ‘A’, ‘C’, ‘B’)\)
Các em có câu hỏi nào về phần giải thích này không? Nếu có, cứ mạnh dạn hỏi nhé. Quan trọng là các em hiểu rõ bản chất của giải thuật đệ quy này.
Tài liệu hướng dẫn thực hành CÀI ĐẶT THUẬT TOÁN AKT CHO BÀI TOÁN THÁP HÀ NỘI 1. Thuật toán AKT Bước 1 Mở đỉnh đầu tiên S, gán g(S) = 0 Sử dụng tri thức bổ sung để ước tính hàm h(S) Tính f(S) = g(S) + h(S) Bước 2 Chọn đỉnh mở có f là nhỏ nhất và gọi đỉnh đó là N Nếu N là đích: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N). Dừng (Success). Nếu không tồn tại đỉnh mở nào: cây biểu diễn vấn đề không tồn tại đường đi tới mục tiêu. Dừng (Fail). Nếu có 2 đỉnh mở trở lên có cùng giá trị f nhỏ nhất: ta phải kiểm tra xem những đỉnh đó có đỉnh nào là đích hay không. Nếu có: Đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N). Dừng. Nếu không có: chọn ngẫu nhiên một trong các đỉnh đó và gọi đó là đỉnh N. Bước 3 Đóng đỉnh N, mở mọi đỉnh sau N. Với mỗi đỉnh sau N, tính: g(S) = g(N) + gt(S->N) Sử dụng tri thức bổ sung để tính h(S). f(S) = g(S) + h(S). Bước 4 Quay lại Bước 2. 2. Cấu trúc dữ liệu typedef struct { char Dia[MAXDIA]; int SoDia; }COT; typedef struct { COT Cot[MAXCOT]; int SoCot; int TrangThai; int DinhTruoc; int g, h; }DINH; DINH O[MAX]; int nO; Ý nghĩa: O: Là tập các đỉnh trên cây tìm kiếm. nO: Số lượng đỉnh trên cây tìm kiếm. DINH. Cot: Sự phân phối các đĩa trên tháp. DINH. SoCot: Số tháp ban đầu. DINH. TrangThai: 1
Tài liệu hướng dẫn thực hành = 0 : Nếu là đỉnh mở. = 1 : Nếu là đỉnh đóng. DINH. DinhTruoc: Trả về thứ tự của đỉnh trước đó. DINH. g, h: Lượng giá 1 đỉnh. 3. Hướng dẫn cài đặt 3.1 Hàm lượng giá Dữ liệu vào: 1 đỉnh P trên cây tìm kiếm. Dữ liệu ra: Giá trị H của đỉnh P. int TinhH(DINH P) { Trả về giá trị h của 1 đỉnh. } 3.2 Hàm tìm kiếm void Solve() { DINH O[MAXDINH]; int nO; int Thoat; // Thoat = 1: Tìm thành công. // Thoat = 2: Tìm thất bại. // Thoat = 3: Không có lời giải. // Thoat = 0: Đang trong quá trình tìm kiếm Khởi tạo mảng đỉnh O O[0].Cot O[0].SoCot O[0].DinhTruoc = -1 O[0].TrangThai = 0 O[0]. g = 0 O[0]. h = TinhH(O[0]) nO = 1 Thoat = 0; while (Thoat == 0) { t = chỉ số đỉnh mở trong O có f (lấy g + h) nhỏ nhất. Nếu không tìm được t thì Thoat = 3 Thuật giải dừng, không có lời giải cho bài toán Đóng đỉnh O[t]. (O[t].TrangThai = 1) Gọi S1[0..k] là tập đỉnh sau O[t] không nằm trong O. Với mỗi S1[i]: i=0..k Nếu nO>MAX Thoat = 2 Thuật giải dừng, không đủ không gian để tìm lời giải. Đưa S1[i] vào O nO++ 2
Tài liệu hướng dẫn thực hành O[nO-1] ← S1[i] O[nO-1].TrangThai = 0 O[nO-1].DinhTruoc = t Nếu S1[i] là đích thì Nho = nO-1 Thoat = 1 Thuật giải dừng, thành công } Nếu Thoat = 1 Dựa vào thông tin đỉnh trước in ra các cách biến đổi Ngược lại Không tìm được lời giải } 4. Mở rộng Dùng cấu trúc dữ liệu động (danh sách liên kết). Xây dựng 1 template về danh sách liên kết, gọi là List Định nghĩa lại cấu trúc dữ liệu: typedef struct { char Dia[MAXDIA]; int SoDia; }COT; typedef struct { List DinhSau; DINH *DinhTruoc; }CANH; typedef struct { COT Cot[MAXCOT]; int SoCot; int TrangThai; List Canh; }DINH; List O Tối ưu cách lưu 1 đỉnh.
Ai biết code sử dụng giải thuật AKT để giải bài toán tháp Hanoi
Tài liệu hướng dẫn thực hành CÀI ĐẶT THUẬT TOÁN AKT CHO BÀI TOÁN THÁP HÀ NỘI 1. Thuật toán AKT Bước 1 Mở đỉnh đầu tiên S, gán g(S) = 0 Sử dụng tri thức bổ sung để ước tính hàm h(S) Tính f(S) = g(S) + h(S) Bước 2 Chọn đỉnh mở có f là nhỏ nhất và gọi đỉnh đó là N Nếu N là đích: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N). Dừng (Success). Nếu không tồn tại đỉnh mở nào: cây biểu diễn vấn đề không tồn tại đường đi tới mục tiêu. Dừng (Fail). Nếu có 2 đỉnh mở trở lên có cùng giá trị f nhỏ nhất: ta phải kiểm tra xem những đỉnh đó có đỉnh nào là đích hay không. Nếu có: Đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N). Dừng. Nếu không có: chọn ngẫu nhiên một trong các đỉnh đó và gọi đó là đỉnh N. Bước 3 Đóng đỉnh N, mở mọi đỉnh sau N. Với mỗi đỉnh sau N, tính: g(S) = g(N) + gt(S->N) Sử dụng tri thức bổ sung để tính h(S). f(S) = g(S) + h(S). Bước 4 Quay lại Bước 2. 2. Cấu trúc dữ liệu typedef struct { char Dia[MAXDIA]; int SoDia; }COT; typedef struct { COT Cot[MAXCOT]; int SoCot; int TrangThai; int DinhTruoc; int g, h; }DINH; DINH O[MAX]; int nO; Ý nghĩa: O: Là tập các đỉnh trên cây tìm kiếm. nO: Số lượng đỉnh trên cây tìm kiếm. DINH. Cot: Sự phân phối các đĩa trên tháp. DINH. SoCot: Số tháp ban đầu. DINH. TrangThai: 1
Tài liệu hướng dẫn thực hành = 0 : Nếu là đỉnh mở. = 1 : Nếu là đỉnh đóng. DINH. DinhTruoc: Trả về thứ tự của đỉnh trước đó. DINH. g, h: Lượng giá 1 đỉnh. 3. Hướng dẫn cài đặt 3.1 Hàm lượng giá Dữ liệu vào: 1 đỉnh P trên cây tìm kiếm. Dữ liệu ra: Giá trị H của đỉnh P. int TinhH(DINH P) { Trả về giá trị h của 1 đỉnh. } 3.2 Hàm tìm kiếm void Solve() { DINH O[MAXDINH]; int nO; int Thoat; // Thoat = 1: Tìm thành công. // Thoat = 2: Tìm thất bại. // Thoat = 3: Không có lời giải. // Thoat = 0: Đang trong quá trình tìm kiếm Khởi tạo mảng đỉnh O O[0].Cot O[0].SoCot O[0].DinhTruoc = -1 O[0].TrangThai = 0 O[0]. g = 0 O[0]. h = TinhH(O[0]) nO = 1 Thoat = 0; while (Thoat == 0) { t = chỉ số đỉnh mở trong O có f (lấy g + h) nhỏ nhất. Nếu không tìm được t thì Thoat = 3 Thuật giải dừng, không có lời giải cho bài toán Đóng đỉnh O[t]. (O[t].TrangThai = 1) Gọi S1[0..k] là tập đỉnh sau O[t] không nằm trong O. Với mỗi S1[i]: i=0..k Nếu nO>MAX Thoat = 2 Thuật giải dừng, không đủ không gian để tìm lời giải. Đưa S1[i] vào O nO++ 2
Tài liệu hướng dẫn thực hành O[nO-1] ← S1[i] O[nO-1].TrangThai = 0 O[nO-1].DinhTruoc = t Nếu S1[i] là đích thì Nho = nO-1 Thoat = 1 Thuật giải dừng, thành công } Nếu Thoat = 1 Dựa vào thông tin đỉnh trước in ra các cách biến đổi Ngược lại Không tìm được lời giải } 4. Mở rộng Dùng cấu trúc dữ liệu động (danh sách liên kết). Xây dựng 1 template về danh sách liên kết, gọi là List Định nghĩa lại cấu trúc dữ liệu: typedef struct { char Dia[MAXDIA]; int SoDia; }COT; typedef struct { List DinhSau; DINH *DinhTruoc; }CANH; typedef struct { COT Cot[MAXCOT]; int SoCot; int TrangThai; List Canh; }DINH; List O Tối ưu cách lưu 1 đỉnh. 3https://sharecode.vn/source-code/source-code-ai-thap-ha-noi-su-dung-akt-bang-c-27661.htm#Download