Tailieumoi.vn giới thiệu giải Chuyên đề Tin học lớp 11 Bài 2: Kĩ thuật quay lui sách Cánh diều hay, chi tiết giúp học sinh xem và so sánh lời giải từ đó biết cách làm Chuyên đề học tập Tin học 11. Mời các bạn đón xem:
Giải Chuyên đề Tin học 11 Bài 2: Kĩ thuật quay lui
Lời giải:
Đề giải quyết bài toán mua đồ bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài n, với mỗi dãy bit tương ứng với một phương án mua, ta tiến hành tính tổng giá để kiểm tra ràng buộc không vượt quá T (đồng) và tính tổng mức độ yêu thích để chọn phương án tối ưu.
1. Bài toán Mua đồ tổng quát
Lời giải:
Lời giải bài toán này có thể biểu diễn bằng 1 dãy bit độ dài n (n là số lượng đồ vật), trong đó bit thứ i (0 ≤ i ≤ n - 1) bằng 1 hoặc 0 tương ứng là vật thứ i được chọn hoặc không chọn
Ví dụ: dãy bit (1, 0, 0, 1, 0) tương ứng với cách chọn đồ dùng số 0 và 3 với tổng giá là 10 +9 = 19 (nghìn đồng) và mức độ yêu thích là 7 + 6 = 13; dãy bit (1, 1, 0, 0, 1) tương ứng với cách chọn đồ dùng số 0, 1 và 4 có tổng giá là 10 + 5 + 5 = 20 (nghìn đồng) và mức độ yêu thích là 7 + 2 + 3 = 12.
Để giải quyết bài toán Mua đồ tổng quát bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài n, với mỗi dãy bit tương ứng với một phương án mua, ta tiến hành tính tổng giá để kiểm tra ràng buộc không vượt quá T (đồng) và tính tổng mức độ yêu thích đề chọn phương án tối ưu.
2. Liệt kê dãy bit độ dài n bằng kĩ thuật đệ quy
Lời giải:
Dãy bit độ dài n có dạng X = (x0, x1...xn-1), trong đó xi bằng 0 hoặc 1 (0 ≤ i ≤ n-1) có thể mô tả theo cách đệ quy như sau:
- Nếu n > 0 thì phần tử đầu tiên của dãy bằng 0 hoặc 1 và n - 1 phần tử sau là dãy bit độ dài n – 1.
- Ngược lại, nếu n = 0 thì dãy bit độ dài n là dãy rỗng
Việc xây dựng các dãy nhị phân theo thuật toán đệ quy như sau:
1. Bắt đầu từ X rỗng, lệnh x = [] và gọi thủ tục đệ quy backtrack(0) để xây dựng bắt đầu phần tử 0.
2. Thành phần i (0 ≤ i ≤ n-1) sẽ lần lượt nhận giá trị 0 và 1 bằng lệnh for v in range(2): Với mỗi giá trị của v, thành phần i được ghi nhận vào xi của X bằng lệnh x.append(v), lệnh này đẩy v vào cuối X. Sau đó tiếp tục gọi để quy để xây dựng các thành phần còn lại (từ thành phần xi+1... đến thành phần xn-1).
3. Để xét được khả năng tiếp theo, hành động quay lui được thực hiện bằng cách loại bỏ nhị phân thành phần cuối cùng của X bằng lệnh x.pop(). Việc quay lui cũng được diễn ra khi đang xây dựng thành phần xi mà xi đã lần lượt nhận cả hai giá trị 0 và 1, khi đó thành phân xi sẽ bị loại khỏi X và lùi về để xét khả năng tiếp theo cho thành phần xi-1
3. Kĩ thuật quay lui
Lời giải:
Nhập chương trình sau và đọc kết quả xuất ra màn hình.
Lời giải:
n = int(input("Nhap n:"))
if ( n<2 or n % 2 == 0or n % 3 == 0 or n % 5 == 0):
print("không phải số nguyên tố ")
else:print("là số nguyên tố")
a) Kĩ thuật quay lui không thể, liệt kê tất cả các trường hợp có thể xảy ra để tìm được nghiệm của bài toán.
b) Khi cài đặt kĩ thuật quay lui, bắt buộc phải sử dụng kĩ thuật đệ quy.
c) Kĩ thuật quay lui là một kĩ thuật theo ý tưởng của kĩ thuật duyệt.
Lời giải:
Trong những câu sau đây, câu sau đúng khi nói về kĩ thuật quay lui:
a) Kĩ thuật quay lui không thể, liệt kê tất cả các trường hợp có thể xảy ra để tìm được nghiệm của bài toán.
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Cánh diều hay, chi tiết khác:
Bài 3: Thực hành kĩ thuật quay lui
Bài 4: Thực hành tổng hợp kĩ thuật duyệt
Bài 5: Thực hành kĩ thuật quay lui giải bài toán xếp hậu