Một số bài tập pascal giải thuật sắp xếp mong sự chỉ giáo

câu 1 DÃY SỐ (Học sinh giỏi, Hà Nội 2008-2009)
Cho dãy số nguyên a1, a2, . . an. Số ap( 1 <= p<= n)  được gọi trung bình cộng trong dãy nếu tồn tại 3 chỉ số i,j,k(1<= i,j.k<=n) đôi mootj khác nhau sao cho ap = (ai+ ạ+ ak) / 3)
Yêu cầu: Cho n và dãy số a1, a2,......an . Hãy tìm số lượng các số trung bình cộng trong dãy
dữ liệu vàò

dòng đầu :
- ghi số nguyên dương  n( 3 <= n  <= 1000
- Dòng thứ hai chứa n số nguyên ai ( |ai | = 10^8Kết quả ra:Số lượng các số trung bình cộng trong dãy.
Dữ liệu vào Kết quả ra
5
4 3 6 3 5 2
Câu 2
 Xét tập F(N) tất cả các số hữu tỷ trong ñoạn [0,1] với mẫu số không vượt quá N (1 <= N <= 100).
Ví dụ tập F(5): 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Sắp xếp các phân số trong tập F(N) theo thứ tự tăng dần, ñưa ra phân số thứ K.

 
T

tengiday

Happy life
Reply: một số bài tập pascal giải thuật sắp xếp mong sự chỉ giáo

Bài 1: Mình nghĩ bài này độ phức tạp là O(n^2 log(n)), tức là ~3 triệu lần để chạy. Để mình tóm tắt thuật toán:
1) Đầu tiên bạn lập 1 mảng 'sum' gồm 3 dòng và n(n-1)/2 cột dùng để tính tổng của a và a[j] nếu i < j. Cái tổng này lưu ở dòng thứ 1. Ở dòng 2 và 3 thì lưu indices i và j nhé. Để có mảng 'sum' này, bạn nên dùng Free Pascal mới đủ bộ nhớ.
2) Sau đó, bạn dùng QuickSort để sort mảng sum này theo cái tổng. Bạn lưu ý khi đổi phần tử thì phải đổi luôn cả 3 dòng.
3) Tiếp theo, chúng ta thử từng a một để xem a có phải là trung bình cộng của 3 số hay không. Tức có nghĩa rằng tìm 3 số sao cho tổng 3 số bằng 3*a. Cách làm là chọn 1 số a[j] trước, 2 số còn lại chúng ta sẽ tìm từ thông tin của mảng 'sum'. Để tìm được, dùng binary search trên mảng 'sum' để tìm số có giá trị 3*a - a[j]. Lưu ý khi tìm thì phải đảm bảo index của j ko trùng với sum[2, ...] và sum[3,...] vì theo đề phải là đôi một khác nhau. Code của đoạn này đại khái là thế này:
Mã: 
count := 0;
for i := 1 to n do
   begin
      s := 3 * a[i];
      for j := 1 to n do
         begin
            // binary search tìm trên mảng 'sum' giá trị là 's - a[j]'.
            // nếu tìm đc thì   count = count + 1   và a[i] chính là trung bình cộng.
         end;
   end;

Bài 2: Bài này mình nghĩ dễ hơn bài 1. Bạn có thể dùng 2 vòng 'for' quét hết. Sau đó QuickSort nó lại là xong. Có thể có phần tử bị trùng thì lúc in ra lưu ý ko in là được.
Thời gian chạy là O(n^2 log(n)). Vì n ko quá 100 nên như thế là đẹp rồi nhé.

PS: Lưu ý cặp trùng nữa nhé.
 
Sửa lần cuối:
Đăng nhập bằng tài khoản VFO hoặc Google

Bài viết mới nhất

Thống kê

Chủ đề
100,754
Bài viết
467,588
Thành viên
339,851
Thành viên mới nhất
Đông Âu

Bài viết được quan tâm nhiều

Top