Bài viết sưu tầm

Bộ tam hợp

(Đề thi lớp 9 năm học 2012-2013)

Cho dãy số nguyên a₁, a₂, ..., a_n, các số khác nhau từng đôi một (3 £N £5000; với mọi i ta có |a_i| £10⁶). Bộ ba số a_i, a_j, a_k (i ¹j ¹k) được gọi là Bộ tam hợp nếu có một số bất kỳ trong ba số đó bằng trung bình cộng của hai số còn lại.

Yêu cầu: Hãy đếm số lượng bộ tam hợp và tìm bộ tam hợp có tổng giá trị của ba số là lớn nhất.

Dữ liệu vào:Đọc từ file  TAMHOP.INP có cấu trúc như sau:

- Dòng 1 chứa số N;

- Dòng 2 chứa n số a₁, a₂, ..., a_N  cách nhau ít nhất một dấu cách

Kết quả: Ghi ra file TAMHOP.OUT có cấu trúc như sau:

- Dòng 1 ghi một số nguyên dương là số lượng bộ tam hợp tìm được;

- Dòng 2 ghi tổng giá trị ba số của bộ tam hợp là lớn nhất.

Ví dụ:

Hướng dẫn:

Cách 1:

Để liệt kê tất cả các khả năng ta có thể sử dụng ba vòng lặp lồng nhau như sau.

Procedure duyet;

Begin

count:=0;

For i:=1 To N-2 Do

For j:=i+1 To N-1 Do

For k:=j+1 To N Do

If isOK(i,j,k)Then Inc(Count);

End;

Trong đó hàm isOK(i,j,k) nhận ba tham số đầu vào là ba chỉ số của dãy số có nhiệm vụ kiểm tra ràng buộc, trả về TRUE nếu thỏa mãn ràng buộc, FALSE trong trường ngược lại.

Độ phức tạp của thuật toán: Số trường hợp thử O(N³) nhân với chi phí kiểm tra O(1), do đó độ phức tạp của thuật toán trên là O(N³).

Độ phức tạp là O(N³)

Cách 2:

Sử dụng thuật toán tìm kiếm nhị phân như sau:

- Sắp xếp dãy số theo thứ tự tăng dần (dùng Quick Sort có độ phức tạp O(n.Logn))

- Dùng hai vòng để liệt kê các trường hợp thử cho i và j, khi biết phần tử A[i], A[j] thì sẽ biết được phần tử A[k].

- Dùng tìm kiếm nhị phân để xem A[k] có trong dãy đã sắp xếp trước đó chưa.

Procedure duyet;

Begin

Quicksort; //Sắp xếp dãy số.

count:=0;

For i:=1 To N-2 Do

      For j:=i+1 To N-1 Do

      Begin

               x:=A[j]*2-A[i];

If FindBi(x,j+1,N)Then Inc(Count);

End;

End;

Trong đó hàm FindBi (x,j+1,N) cho kết quả là TRUE nếu tìm thấy x thuộc dãy số từ j+1 đến N, cho kết quả là FALSE trong trường ngược lại.

Độ phức tạp là O(N².LogN)