Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 3: Thực hành kĩ thuật quay lui

XIN CHÀO MỪNG CÁC EM

ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Ôn bài cũ:

Ý tưởng của kĩ thuật quay lui là gì?

• Kỹ thuật quay lui xây dựng tất cả các khả năng của lời giải bằng cách mở rộng từng thành phần và quay lui, bắt đầu từ lời giải rỗng.
• Với cách làm này, kĩ thuật quay lui có thể xét tất cả các khả năng của lời giải và kiểm tra, đánh giá để chọn nghiệm của bài toán theo ý tưởng của kĩ thuật duyệt.

BÀI 3. THỰC HÀNH

KĨ THUẬT QUAY LUI

Bài toán 1

Trả tiền

Lời giải của bài toán được biểu diễn như thế nào?

• Kết quả chạy chương trình với các dữ liệu đầu vào:

• Viết chương trình như sau:

def updateSolution():

sum = 0

p = []

for i in range(n):

if x[i] == 1:

sum = sum + t[i]

p = p + [i]

if(sum==s):

print(p)

def backtrack(i):

for v in range(2):

x.append(v)

if I == n-1:

updateSolution()

else:

backtrack(i+1)

x.pop()

n, s = map(int,input().split())

t = list(map(int,input().split()))

x = []

backtrack(0)

for v in range(2):

x.append(v)

if I == n-1:

updateSolution()

else:

backtrack(i+1)

x.pop()

n, s = map(int,input().split())

t = list(map(int,input().split()))

x = []

backtrack(0)

Bài toán 2

Liệt kê hoán vị của n phần tử bằng kĩ thuật đệ quy

Hình 1. Chương trình liệt kê hoán vị của n phần tử bằng kĩ thuật đệ quy và màn hình kết quả chạy chương trình với n = 3

• Cho biết số lượng hoán vị của 3, 4 hoặc 5 phần tử là bao nhiêu.
• Em hãy so sánh chương trình liệt kê các dãy bit độ dài n với chương trình liệt kê các hoán vị của n phần tử.
• Cho biết ý nghĩa của câu lệnh x.append(v) và x.pop() trong chương trình.
• Hình 2 mô tả quá trình gọi đệ quy để xây dựng các hoán vị 3 phần tử. Dãy ở hình chữ nhật là dãy hoán vị trong quá trình xây dựng, số trong hình ô van là thứ tự xây dựng. Em hãy cho biết các dãy trong hình chữ nhật chứa dấu

?

HƯỚNG DẪN TRẢ LỜI

a

b

• Chương trình liệt kê các dãy bit độ dài n với chương trình liệt kê các hoán vị của n phần tử đều được áp dụng kĩ thuật đệ quy.

HƯỚNG DẪN TRẢ LỜI

c

d

[1, 2]

[1, 2, 0]

[2, 1]

[2, 1, 0]

LUYỆN TẬP

Câu 1: Chạy chương trình của bài toán “Trả tiền” với đầu vào như sau:

5 200

10 20 50 50 100

Kết quả của bài toán là:

A. [2, 3, 4]

B. [0, 3, 4]

C. [0, 2, 4]

D. [0, 2, 3]

A. [2, 3, 4]

Câu 2: Chương trình sau được dùng để làm gì?

A. Tính tổng số tiền.

B. Liệt kê hoán vị.

C. Chọn mua đồ.

D. Tính tổng số tờ tiền.

B. Liệt kê hoán vị.

Câu 3: Chạy chương trình sau với dự liệu đầu vào n=2. Kết quả của bài toán là:

A. [0,1]

B.[0,1];[1,0]

C. [0, 1, 2]

D. [0,1,2];[2,1,0];[1,2,0]

B.[0,1];[1,0]

Câu 4: Để ghi nhận thêm thành phần ta dùng lệnh nào?

--------------- Còn tiếp ---------------