Chúng ta sẽ phát triển chương trình C++ tìm trung vị (median) của hai mảng đã sắp xếp sử dụng phương pháp tìm kiếm nhị phân (Binary Search).
Thuật toán
Bắt đầu
Hàm median() với cả hai mảng và chỉ số bắt đầu/kết thúc của mỗi mảng, nhận hai mảng và các phần tử tương ứng làm tham số.
A) Tính độ dài mảng là e1 - s1, ở đây e1 và s1 là chỉ số cuối và đầu.
B) Nếu độ dài là 2 hoặc 1, tính trung vị của các mảng theo độ dài chẵn/lẻ, in kết quả.
C) Kiểm tra nếu cả hai trung vị riêng lẻ bằng nhau, nếu có thì in kết quả.
D) Nếu hai điều kiện trên đúng thì kiểm tra nếu m1 > m2 thì trung vị kết hợp sẽ nằm ở nửa đầu mảng đầu tiên hoặc nửa sau mảng thứ hai.
E) Nếu m1 < m2 thì trung vị kết hợp sẽ nằm ở nửa sau mảng đầu tiên hoặc nửa đầu mảng thứ hai.
F) Gọi median() đệ quy với chỉ số bắt đầu/kết thúc cập nhật.
Kết thúc
Mã ví dụ
#include <iostream>
using namespace std;
void median(float a1[], int s1, int e1, float a2[], int s2, int e2) {
float m1, m2;
if((e1-s1+1)%2 == 0) {
if(e1-s1 == 1) {
m1 = ((a1[s1]a2[e2]?a1[e1]:a2[e2]))/2;
cout << m1;
return;
}
m1 = (a1[(e1+s1)/2]+a1[(e1+s1)/2+1])/2;
m2 = (a2[(e2+s2)/2]+a2[(e2+s2)/2+1])/2;
if(m1 == m2) {
cout << m1;
return;
} else {
if(m1 > m2)
median(a1, s1, (e1+s1)/2+1, a2, (e2+s2)/2, e2);
else
median(a1, (e1+s1)/2, e1, a2, s2, (e2+s2)/2+1);
}
} else {
if(e1-s1 == 0) {
m1 = (a1[s1]+a2[s2])/2;
cout << m1;
return;
}
m1 = a1[(e1+s1)/2];
m2 = a2[(e2+s2)/2];
if(m1 == m2) {
cout << m1;
return;
} else {
if(m1 > m2)
median(a1, s1, (e1+s1)/2, a2, (e2+s2)/2, e2);
else
median(a1, (e1+s1)/2, e1, a2, s2, (e2+s2)/2);
}
}
return;
}
int main() {
int n1,n2,i;
cout << "\nNhập số phần tử cho mảng 1: ";
cin >> n1;
float a1[n1];
for(i = 0; i < n1; i++) {
cout << "Nhập phần tử mảng 1 " << i+1 << ": ";
cin >> a1[i];
}
cout << "\nNhập số phần tử cho mảng 2: ";
cin >> n2;
float a2[n2];
for(i = 0; i < n2; i++) {
cout << "Nhập phần tử mảng 2 " << i+1 << ": ";
cin >> a2[i];
}
cout << "Trung vị là ";
median(a1, 0, n1-1, a2, 0, n2-1);
return 0;
}
Kết quả đầu ra
Nhập số phần tử cho mảng 1: 5 Nhập phần tử mảng 1 1: 6 Nhập phần tử mảng 1 2: 7 Nhập phần tử mảng 1 3: 9 Nhập phần tử mảng 1 4: 10 Nhập phần tử mảng 1 5: 11 Nhập số phần tử cho mảng 2: 5 Nhập phần tử mảng 2 1: 60 Nhập phần tử mảng 2 2: 70 Nhập phần tử mảng 2 3: 90 Nhập phần tử mảng 2 4: 100 Nhập phần tử mảng 2 5: 110 Trung vị là 35