Bài 27. Thực hành thiết kế chương trình theo phương pháp làm mịn dần

Chủ đề 6. Kĩ thuật lập trình – Bài 27. Thực hành thiết kế chương trình theo phương pháp làm mịn dần – sách giáo khoa trang 123 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.

Chủ đề 6. Kĩ thuật lập trình – Bài 26. Phương pháp làm mịn dần trong thiết kế chương trình

Khởi động

Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát khi giải quyết các bài toán cụ thể. Em có thể sử dụng sơ đồ hình cây để mô tả phương pháp này không?

Lời giải:

Phương pháp làm mịn dần, hay còn gọi là phương pháp giảm dần và chinh phục dần là một trong các cách tiếp cận tổng quát để giải quyết các bài toán cụ thể. Sơ đồ hình cây là một công cụ hữu ích để mô tả phương pháp này.

Sơ đồ hình cây là một biểu đồ hình cây đơn giản, thường được sử dụng để minh họa quá trình giải quyết bài toán bằng phương pháp làm mịn dần. Nó gồm các nút đại diện cho các bài toán con, và các nhánh đại diện cho các bước giải quyết bài toán con đó. Các nhánh này có thể tiếp tục được chia nhỏ cho đến khi không thể chia nhỏ hơn nữa (đạt được điều kiện dừng), sau đó các kết quả của các bài toán con được tổng hợp lại để đưa ra kết quả cuối cùng cho bài toán gốc.

Luyện tập

Câu 1. Thiết kế thuật toán cho nhiệm vụ 1 với ý tưởng khác như sau: Dãy A là một hoán vị của dãy các số từ 1 đến n khi và chỉ khi dãy A có độ dài n và mọi số i từ 1 đến n đều nằm trong A.

Lời giải:

Một ý tưởng khác để kiểm tra xem dãy n số có phải là một hoán vị của dãy số 1, 2, …, n hay không là sử dụng tính chất đặc biệt của hoán vị. Ta biết rằng một hoán vị của dãy số từ 1 đến n sẽ có các giá trị từ 1 đến n đúng một lần, tức là không có giá trị lặp lại và không có giá trị bỏ sót. Với ý tưởng này, ta có thể thiết kế thuật toán như sau:

• Đọc dãy số vào mảng a gồm n phần tử.

• Kiểm tra độ dài của dãy a có bằng n không. Nếu không bằng n, in ra “KHÔNG” và kết thúc thuật toán.

• Khởi tạo một mảng visited gồm n phần tử, với giá trị ban đầu là False. Mảng visited này sẽ được sử dụng để đánh dấu các số đã xuất hiện trong dãy a.

• Duyệt qua từng phần tử trong dãy a, đồng thời đánh dấu số đó đã xuất hiện trong dãy a bằng cách đặt giá trị True tại vị trí tương ứng trong mảng visited.

• Kiểm tra mảng visited. Nếu một trong các phần tử của visited là False, tức là có giá trị bị bỏ sót trong dãy a, in ra “KHÔNG” và kết thúc thuật toán.

• Sau khi kiểm tra xong mảng visited, in ra “CÓ” nếu không có giá trị nào bị bỏ sót, ngược lại in ra “KHÔNG“.

– Thuật toán:

def kiemTraHoanVi(a):
    n = len(a)
    visited = [False] * n
    
    # Kiểm tra độ dài của dãy a
    if n != len(set(a)):
        return "KHÔNG"
    
    # Duyệt qua từng phần tử trong dãy a
    for i in a:
        # Nếu số i đã xuất hiện trong dãy a
        if i < 1 or i > n or visited[i-1]:
            return "KHÔNG"
        visited[i-1] = True
    
    # Kiểm tra mảng visited
    if all(visited):
        return "CÓ"
    else:
        return "KHÔNG"

Câu 2. Trong Nhiệm vụ 2, nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn được không?

Lời giải:

Nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn.

Vận dụng

Câu 1. Cho dãy số A = A[0], A[1]. …. A[n — 1]. Thiết kế và viết chương trình kiểm tra trong dãy A có hai phân tử nào trùng nhau hay không. Cần đưa ra câu trả lời là “CÓ” hay “KHÔNG”. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.

Lời giải:

Sử dụng một vòng lặp for để duyệt qua từng phần tử của dãy A từ đầu đến cuối.

Trong mỗi lần lặp, so sánh phần tử hiện tại (A[i]) với các phần tử trước đó (A[0], A[1], …, A[i-1]) để kiểm tra xem có phần tử trùng nhau hay không.

Nếu tìm thấy phần tử trùng nhau, đưa ra kết quả là “CÓ” và kết thúc chương trình.

Nếu không tìm thấy phần tử trùng nhau sau khi đã duyệt qua toàn bộ dãy A, đưa ra kết quả là “KHÔNG”.

def kiemTraTrungLap(A):

    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if A[i] == A[j]:
                return "CÓ"
    return "KHÔNG"

# Đầu vào: Dãy số A
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Gọi hàm để kiểm tra
ket_qua = kiemTraTrungLap(A)

# Đầu ra: Kết quả kiểm tra
print("Có phần tử trùng lặp trong dãy A:", ket_qua)

Câu 2. Xâu kí tự được gọi là đối xứng nêu thay đổi thứ tự ngược lại các kí tự của xâu thì vẫn nhận được dãy ban đầu. Ví dụ xâu “abcdcba” là đối xứng, còn xâu “1011” không là đối xứng. Thiết kế và viết chương trình kiểm tra một xâu kí tự cho trước có là đối xứng hay không. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.

Lời giải:

def kiem_tra_doi_xung(xau):
    # Loại bỏ các kí tự không cần thiết và chuyển đổi xâu về dạng chữ thường
    xau = xau.replace(" ", "").lower()
    
    # So sánh xâu gốc với phiên bản đảo ngược của nó
    if xau == xau[::-1]:
        return "Đối xứng"
    else:
        return "Không đối xứng"

# Nhập xâu kí tự cần kiểm tra
xau = input("Nhập xâu kí tự: ")

# Gọi hàm để kiểm tra
ket_qua = kiem_tra_doi_xung(xau)
print("Xâu đã nhập:", ket_qua)

Xem các bài giải khác: Giải bài tập SGK lớp 11 định hướng Khoa học máy tính – NXB Kết nối tri thức với cuộc sống

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech

Tường Nguyễn