Một giá trị lặp cho các vị trí cùng kết quả
Đầu vào là dãy `a`; đầu ra là dãy `b` có cùng độ dài, với `b[k]` bằng **số lần giá trị `a[k]` xuất hiện trong cả dãy `a`**. Nếu `a = [4, 2, 4, 7, 2]`, số 4 xuất hiện hai lần, số 2 hai lần và số 7 một lần, nên `b = [2, 2, 2, 1, 2]`. Mỗi vị trí của cùng một giá trị nhận cùng số đếm. Đây là đếm trong toàn bộ dãy, không phải chỉ các lần đứng trước vị trí đang xét.
Tách phép đếm thành hàm nhỏ
```python
def so_lan(x, a):
dem = 0
for v in a:
if v == x:
dem += 1
return dem
def dem_theo_vi_tri(a):
b = []
for x in a:
b.append(so_lan(x, a))
return b
print(dem_theo_vi_tri([4, 2, 4, 7, 2]))
```
Kết quả là `[2, 2, 2, 1, 2]`. Nếu `a=[]` thì vòng ngoài không chạy và kết quả là `[]`. Vòng ngoài có `n` lượt, mỗi lần hàm `so_lan` xem `n` phần tử, nên trường hợp này có bậc `O(n²)`. Phân tách hàm giúp thấy rõ bước con “đếm một giá trị” trong thiết kế làm mịn dần.
Bài luyện
Với `a = [5, 1, 5, 5]`, dãy số lần xuất hiện theo vị trí là gì?
Đó là đếm tích lũy theo vị trí, không phải cả dãy.
5 xuất hiện ba lần, 1 xuất hiện một lần.
Đây là dãy đầu vào.
Không phải mọi giá trị xuất hiện bốn lần.
Lời giải
Trong cả dãy, 5 có ba lần và 1 có một lần; thay từng giá trị bằng số lần của nó được [3,1,3,3].
Bài luyện
`dem_theo_vi_tri([])` trả gì?
Đầu vào không có vị trí nào để ghi 0.
b bắt đầu rỗng, vòng for không chạy.
Hàm trả b.
Duyệt dãy rỗng hợp lệ.
Lời giải
Không có phần tử đầu vào nên không có giá trị cần đếm; b giữ nguyên là [].
Bài luyện
Trong mã bài học, `b[k]` đếm số lần xuất hiện của giá trị nào?
k là vị trí, không nhất thiết là giá trị.
Hàm so_lan nhận đúng phần tử a[k] và cả dãy a.
Mỗi vị trí dùng giá trị của chính nó.
Mã dùng phép ==, không dùng <.
Lời giải
Ở lượt vị trí k, x=a[k]; so_lan(x,a) đếm mọi phần tử của a bằng x.
Đang học