[Bài toán] Xây dựng đường sắt

Bài toán: Bộ xây dựng đang có kế hoạch xây dựng hệ thống đường sắt nối liền các thành phố với nhau, sao cho chỉ có duy nhất 1 tuyến đường sắt nối liền hai thành phố bất kỳ. Sau khi nhiên cứu tính toán chi phí xây dựng các tuyến đường sắt nối liền các thành phố, bộ xây dựng thu...

[Bài tập mẫu] Đa giác số

Bài toán: Trên vòng tròn đánh dấu n điểm phân biệt. Các điểm này được chọn làm n đỉnh của đa giác lồi P. Vẽ tất cả các đường chéo của đa giác P. Cho N là một họ gồm n số nguyên dương. Mỗi số của họ N sẽ được viết bên cạnh một đỉnh của đa giác P. Ta gọi việc làm này là phân...

[Bài tập mẫu] Con đường Tùng - Trúc.

[Bài toán] Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng,dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất...

[Bài toán] Xếp hậu

Bài toán:  Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ n x n sao cho chúng không ăn được nhau bằng thuật toán Back Track. Giải. Bàn cờ có n hàng được đánh số từ 0 đến n-1, n cột được đánh số từ 0 đến n-1; Bàn cờ có n*2 -1 đường chéo xuôi được đánh số từ 0 đến 2*n...

[Bài toán] Liệt kê các hoán vị của tập n phần tử bằng thuật toán Back Track

     Biểu diễn hoán vị dưới dạng p1, p2,.., pn, trong đó pi nhận giá trị từ 1 đến n và pi≠pj với i≠j. Các giá trị từ 1 đến n lần lượt được đề cử cho pi, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy, cần phải ghi nhớ với mỗi giá trị j xem...

[Bài toán] Liệt kê các tập con k phần tử của tập n phần tử bằng thuật toán Back Track

Lý thuyết Back Track bạn có thể xem thêm ở đây.      Biểu diễn tập con k phần tử dưới dạng c1, c2,.., ck, trong đó 1< c1các giá trị đề cử cho ci là từ ci-1+ 1 cho đến n - k + i. Cần thêm vào c0= 0. Các giá trị đề cử này mặc nhiên được chấp nhận mà không cần phải...