Cho mảng các góc đại diện cho các miếng của một vòng tròn. Nhiệm vụ: ghép các miếng liên tiếp thành hai phần sao cho chênh lệch góc giữa hai phần nhỏ nhất.
Mô tả bài toán
Cho các góc của các miếng tròn. Cần ghép chúng thành hai phần liên tiếp (phải lấy các miếng liên tiếp nhau) sao cho chênh lệch góc giữa hai phần là nhỏ nhất.
Ví dụ: ang[] = {90, 45, 90, 135}
Kết quả: 90
Giải thích: Phần 1: 90+45=135. Phần 2: 90+135=225. Chênh lệch = 225-135=90.
Phương pháp giải
Góc phần 1 là A, phần 2 là 360-A. Chênh lệch = |A - (360-A)| = 2*|A-180|. Cần tìm A gần 180 nhất bằng cách thử tất cả các đoạn liên tiếp.
Sử dụng kỹ thuật cửa sổ trượt: duyệt mảng, cộng dồn góc A. Khi A >= 180, cập nhật minDiff = min(minDiff, 2*|180-A|), sau đó trừ góc bên trái và dịch cửa sổ.
Ví dụ minh họa (C++)
#include <iostream>
#include <cmath>
using namespace std;
int CalcSmallDiffAng(int ang[], int n) {
int Left = 0, A = 0, minDiff = 360;
for (int i = 0; i < n; i++) {
A += ang[i];
while (A >= 180) {
minDiff = min(minDiff, 2 * abs(180 - A));
A -= ang[Left];
Left++;
}
minDiff = min(minDiff, 2 * abs(180 - A));
}
return minDiff;
}
int main() {
int ang[] = { 90, 45, 90, 135 };
int n = sizeof(ang) / sizeof(ang[0]);
cout << "The smallest difference of angles of two parts of a given circle is "
<< CalcSmallDiffAng(ang, n);
return 0;
}
Đầu ra
The smallest difference of angles of two parts of a given circle is 90