Từ phần đầu nhỏ hơn đến phần đầu đang xét
Xét dãy số A không rỗng. Hàm minmax(A,k) trả hai giá trị: nhỏ nhất và lớn nhất trong A[0] tới A[k], với 0≤k<len(A).
Khi k=0, phần đầu chỉ có một phần tử; cả hai giá trị đều bằng A[0]. Khi k>0, lấy cặp nhỏ nhất/lớn nhất của A[0] tới A[k−1], rồi so sánh thêm với A[k].
Trả đồng thời hai giá trị
```python
def minmax(A, k):
if k == 0:
return A[0], A[0]
low, high = minmax(A, k - 1)
return min(low, A[k]), max(high, A[k])
```
Ví dụ A=[1.62,1.48,1.75], gọi minmax(A,2):
| Phần đầu | (Nhỏ nhất, lớn nhất) |
|---|---|
| [1.62] | (1.62,1.62) |
| [1.62,1.48] | (1.48,1.62) |
| [1.62,1.48,1.75] | (1.48,1.75) |
Bước cuối chỉ cần so sánh 1.75 với hai giá trị đã có, không tìm lại toàn bộ phần đầu. Hàm trả các giá trị, chưa trả tên hay vị trí của bản ghi chứa chúng.
Dãy rỗng chưa có min/max để trả
Với một phần tử, chẳng hạn A=[1.62], lời gọi k=0 trả (1.62,1.62). Với A=[], không có A[0] và không có giá trị nhỏ nhất/lớn nhất theo yêu cầu đang xét. Vì vậy phải kiểm dãy có dữ liệu trước khi gọi với k=len(A)−1.
Nếu nhiều phần tử cùng đạt min hoặc max, cặp giá trị trả về vẫn xác định. Việc chọn bản ghi nào trong các bản ghi bằng nhau cần một quy tắc riêng; bài đọc–ghi tệp tiếp theo chọn bản ghi xuất hiện đầu tiên.
Bài luyện
Với A=[1.62,1.48,1.75], minmax(A,1) trả cặp nào?
Thứ tự trả là nhỏ nhất trước, lớn nhất sau.
Đó là các chỉ số, khác loại kết quả của hàm.
Chỉ xét A[0] và A[1].
1.75 ở ngoài phần đầu kết thúc tại chỉ số 1.
Lời giải
k=1 chỉ xét phần đầu [1.62,1.48]. Giá trị nhỏ nhất là 1.48 và lớn nhất là 1.62, nên cặp trả về là (1.48,1.62).
Bài luyện
Với A=[1.62], vì sao cơ sở phải trả (A[0],A[0])?
Dãy ấy chỉ có một phần tử.
Số 0 không thuộc dữ liệu, không được tự thêm.
Hàm trả hai giá trị, không trả chỉ số.
Hai kết quả có thể bằng nhau.
Lời giải
Phần đầu tại k=0 chỉ gồm A[0]. Không có giá trị nào khác để so sánh, nên cả min và max đều bằng A[0].
Bài luyện
Trước khi gọi minmax(A,len(A)-1), trường hợp nào cần được chặn theo điều kiện của hàm?
Dãy rỗng không có A[0] hay kết quả min/max đang yêu cầu.
Cơ sở k=0 xử lí đúng một phần tử.
So sánh min/max vẫn dùng được khi có giá trị bằng nhau.
Thuật toán không đòi thứ tự đầu vào riêng.
Lời giải
Nếu A=[], len(A)−1=−1 và không thuộc điều kiện 0≤k<len(A). Cần báo chưa có dữ liệu trước lời gọi, thay vì tự trả 0 làm min/max.
Đang học