Thuật toán Archive

Bài toán người du lịch

BÀI TOÁN NGƯỜI DU LỊCH Cho n thành phố đánh số từ 1 đến n và m tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi bảng C cấp nxn, ở đây C[i, j] = C[j, i] = Chi phí đi đoạn đường trực tiếp từ thành phối

Thuật toán nhánh cận

Mô hình thuật toán nhánh cận Dựa trên mô hình thuật toán quay lui, ta xây dựng mô hình sau: Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả  năng đánh giá theo từng bước, nếu tại bước thứ i, giá trị thử gán cho x[i]  không có hi vọng tìm thấy

Bài toán xếp hậu (Backtracking)

Bài toán xếp hậu: Xét bàn cờ tổng quát kích thước nxn. Một quân hậu trên bàn cờ có thể ăn được các quân khác nằm tại các ô cùng hàng, cùng cột, hoặc cùng đường chéo. Hãy tìm cách xếp n quân hậu trên bàn cờ sao cho không quân nào ăn quân nào.

Bài toán phân tích số

Bài toán phân tích số: Cho một số nguyên dương n<=30, hãy tìm tất cả cách phân tích số n thành tổng của các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là 1 cách. Cách làm Bài toán phân tích số:  Dùng 1 mảng t[i] để lưu tổng

Liệt kê các chỉnh hợp không lặp chập m của n phần tử

Gần tương tự bài Liệt kê các hoán vị, các bạn có thể tham khảo ở các bài trước. Code tham khảo liệt kê các chỉnh hợp không lặp:  [crayon-5c6f19f89b7ac595835676/]  

Liệt kê tổ hợp

HD: Để liệt kê các tập con k phần tử của tập S = {1,2,…,n} ta có thể đưa về liệt kê các cấu hình x[1…n], ở đây các x[i] thuộc S và x[1] < x[2] < … < x[m]. Ta có nhận xét như sau:   x[m] <= n x[m-1] <= x[m]-1 <= n-1

Liệt kê hoán vị (PP quay lui)

Bài tập: Liệt kê hoán vị của {1,2,…,n} HD: Đáp số có dạng (x1,x2,…,x n). Khả năng của xi là 1,2,…,n Chấp nhận khả năng j của xi: chỉ chấp nhận khi chưa được sử dụng (xi khác x1,…,xi-1). Để theo dõi j sử dụng hay chưa ta dùng một mảng b: b[j]=false là chưa sử

Liệt kê dãy nhị phân (PP quay lui)

Đề bài : Liệt kê dãy nhị phân có độ dài n. HD: Đáp số có dạng (x1,x2,…,x n). Khả năng của xi là 0,1. Chấp nhận khả năng j của xi: luôn chấp nhận. Xác định xi theo j: xi=j. Ghi nhận 1 đáp số: xuất dãy xi. Code tham khảo:  [crayon-5c6f19f89c2e1420213157/]      

Thuật toán Quay lui (Backtracking Algorithms)

Ý tưởng: G/s đáp số của bài toán là một bộ có n thành phần (x1,x2,…,xn) và g/s đã xác định được i-1 thành phần x1,x2,…,xi-1. Để xác định xi, ta xét tất cả các khả năng có thể của xi, đánh số các khả năng này là 1,…,ni. Với mỗi khả năng j của xi ta kiểm

Liệt kê hoán vị (PP Sinh)

Link bài: http://www.spoj.com/PTIT/problems/BCPERMU/ 9807. Liệt kê hoán vị (Cơ bản) Mã bài: BCPERMU Liệt kê hoán vị của n phần tử của một tập gồm các số từ 1->n. Input Dòng duy nhất chứa số n (1<=n<=8) Output Các hoán vị sắp xếp theo thứ tự từ điển tăng dần. Example Input: 3 Output: 123 132
Share