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 bài tập trang 80 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 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần
Câu 27.1
Cho trước dãy số A, cần tìm một phần tử được lặp lại nhiều nhất đồng thời với số lần lặp trong A. Ví dụ nếu A = [1, 3, 5, 0, 1, 2, 3, 4, 10, 1] thì lời giải cần trả về bộ giá trị (1, 3).
Với bài toán trên, một người thiết kế đã phác thảo các bước thực hiện như sau:
1) Thiết lập hàm lap(x) tính số lần lặp của phần tử x trong A.
2) Thiết lập dãy B, các phần tử của B là số lần lặp tương ứng của các phần tử của A.
3) Tính giá trị max của B, từ đó tìm ra phần tử tương ứng của A.
Em hãy chi tiết hoá các bước trên, từ đó tìm ra lời giải của bài toán.
Trả lời:
1) Hàm lap(x,A) thiết lập như sau:
def lap(x,A):
S = 0
for k in A:
if k == x:
S = S + 1
return S2) Bước này có thể chi tiết hoá thành các lệnh như sau:
B = []
for x in A:
B.append(x)3) Bước này chi tiết hóa như sau:
M = max(B)
index = B.index(M)
return A[index], MLời giải hoàn chỉnh của bài toán:
def lap(x, A):
S = 0
for k in A:
if k == x:
S = S + 1
return S
def tim_lap(A):
B = []
for x in A:
B.append(lap(x, A))
M = max(B)
index = B.index(M)
return A[index], M
A = [1, 3, 5, 0, 1, 2, 3, 4, 10, 1]
print(tim_lap(A))Câu 27.2
Việc giải bài toán sắp xếp danh sách A được phác thảo các bước thực hiện như sau:
1) Tìm tất cả các cặp chỉ số (i, j) của danh sách A với i<j.
2) Với mỗi cặp chỉ số (i, j) đã tìm được trong bước trên, nếu A[i] > A[j] thì đổi chỗ hai phần tử này.
Em hãy chi tiết hoá các công việc trên, từ đó tìm ra lời giải của bài toán.
Trả lời:
1) Đoạn chương trình sau sẽ tìm tất cả các cặp chỉ số như vậy, ở đây n là độ dài mảng A:
for i in range(n):
for j in range(i + 1, n):2) Chi tiết hóa công việc 2) như sau;
if A[i] > A[j]:
A[i], A[j] = A[j], A[i]Kết hợp lại có chương trình hoàn chỉnh như sau:
def sapXep(A):
n = len(A)
for i in range(n):
for j in range(i+1, n):
if A[i] > A[j]:
A[i], A[j] = A[j], A[i]
return A
A = [4, 2, 7, 1, 9, 3]
sapXep(A)
print("Mảng sau khi sắp xếp:", A)Câu 27.3
Thiết kế thuật toán và chương trình cho bài toán sau bằng phương pháp làm mịn dần, hãy mô tả chi tiết các bước:
Cho trước dãy số A, viết chương trình kiểm tra xem dãy A có phải là đơn điệu tăng hay không. Dãy A được gọi là đơn điệu tăng nếu thoả mãn: A[0] ≤ A[1] ≤ … ≤ A[n-1].
Trả lời:
Có thể thiết kế bài toán trên theo phương pháp làm mịn dần theo các bước như sau:
1) Duyệt một lượt các phần tử của dãy A.
2) Kiểm tra xem tại vị trí duyệt có phá vỡ tính đơn điệu tăng hay không.
3) Nếu tại bước 2 bị phá vỡ thì trả về False.
4) Nếu thực hiện xong bước 2, 3 mà không thấy phá vỡ đơn điệu thì trả về True.
Các bước trên sẽ tương ứng với chương trình sau:
def kiemTraDayTang(A):
n = len(A)
for i in range(n-1):
if A[i] > A[i+1]:
return False
return TrueCâu 27.4
Thiết kế thuật toán và chương trình cho bài toán sau bằng phương pháp làm mịn dần, hãy mô tả chi tiết các bước:
Cho trước dãy số A bất kì. Cần thiết lập dãy số B có tính chất sau: Các phần tử của B sẽ khác nhau từng đối một và mỗi số của B đều có thể phân tích thành tổng của hai số lấy từ dãy A.
Trả lời:
Có thể thiết kế bài toán trên theo phương pháp làm mịn dần theo các bước như sau:
1) Thiết lập dãy B rỗng.
2) Duyệt trên tất cả các cặp chỉ số (i, j) của dãy A.
3) Kiểm tra nếu A[i] + A[j] chưa có trong B thì bổ sung giá trị này vào B.
4) Kết thúc và trả về dãy B.
Kết quả việc chi tiết hoá các công việc trên có thể như chương trình sau:
def ptTong(A):
n = len(A)
B = []
for i in range(n):
for j in range(n):
if A[i] + A[j] not in B:
B.append(A[i] + A[j])
return BCâu 27.5
Thiết kế thuật toán và chương trình cho bài toán sau bằng phương pháp làm mịn dần, hãy mô tả chi tiết các bước:
Cho trước hai xâu kí tự s1 và s2. Tìm xâu s dài nhất sao cho xâu s đồng thời là phần đầu (prefix) của cả hai xâu s1 và s2.
Trả lời:
Có thể thiết kế bài toán trên theo phương pháp làm mịn dần theo các bước như sau:
1) Thiết lập xấu rỗng s.
2) Duyệt đồng thời theo các kí tự của s1 và s2 từ trái sang phải, cho đến khi kết thúc một trong 2 xâu s1, s2 và dừng khi gặp vị trí khác nhau giữa hai xâu. Trong quá trình duyệt, duyệt tới đâu thì nối với s tới đó.
3) Khi kết thúc duyệt thì dừng chương trình, trả về xâu s.
Kết quả việc chi tiết hoá các công việc trên có thể như chương trình sau:
def prefix(s1, s2):
s = " "
i = 0
while i <= min(len(s1),len(s2)) and s1[1] == s2[i]:
s = s + s1[i]
i = i + 1
return sCâu 27.6
Viết chương trình nhập danh sách họ tên các bạn lớp em. Danh sách này được lưu trong tệp văn bản HS.inp, mỗi dòng ghi tên đầy đủ của một học sinh bao gồm cả họ, tên đệm và tên. Sau đó, nhập từ bàn phím một họ, ví dụ nhập “Nguyễn”. Chương trình kiểm tra và thông báo, ví dụ: Lớp em có 4 bạn họ Nguyễn.
Trả lời:
def tach_Ho(s):
hoTen = s.split()
return hoTen[0]
def nhapDL(fi):
f = open(fi, encoding="UTF-8")
A = [s.strip() for s in f.readlines()] # Đọc dữ liệu và loại bỏ khoảng trắng ở hai đầu
f.close()
return A
def find(A, ho):
count = 0
for s in A:
if tach_Ho(s) == ho:
count = count + 1
return count
# Chương trình chính
fi = "HS.inp"
DS = nhapDL(fi)
ho = input("Nhập một họ: ")
C = find(DS, ho)
print("Lớp em có", C, " bạn họ", ho)Câu 27.7*
Bài toán tương tự Câu 27.6, nhưng câu hỏi là nhập tên và kiểm tra theo tên của học sinh.
Trả lời:
def tach_Ten(s):
hoTen = s.split()
return hoTen[-1] #chỉ số - 1 tương đương chỉ số len(-1)
def nhapDL(fi):
f = open(fi, encoding = "UTF-8")
A = [s for s in f]
A = [s.strip() for s in f.readlines()] # Đọc dữ liệu và loại bỏ khoảng trắng ở hai đầu
f.close()
return A
def find(A, Ten):
count = 0
for s in A:
if tach_Ten(s) == Ten:
count = count + 1
return count
#chương trình chính
fi = "HS.inp"
DS = nhapDL(fi)
Ten = input("Nhập một tên: ");
C = find(DS, Ten)
print("Lớp em có", C," bạn tên", Ten)Xem các bài giải khác: Giải Sách Bài Tập Lớp 11 Khoa Học Máy Tính 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
