Tìm d để tối đa hóa số lượng 0 trong mảng c[i] = d*a[i] + b[i] trong C++

Khái niệm

Cho hai mảng M số nguyên. Xét mảng C với phần tử i-th là d*a[i] + b[i], trong đó d là số thực tùy ý. Tìm d sao cho mảng C có số lượng 0 lớn nhất, và in ra số lượng 0 đó.

Đầu vào

a[] = {15, 40, 45} b[] = {4, 5, 6}

Đầu ra

Giá trị d: -0.133333 Số 0 trong mảng C: 1 Nếu chọn d = -0.133333 thì có một 0 trong C, đây là tối đa.

Phương pháp

Các bước:

• Viết lại phương trình: d = -b[i]/a[i]
• Dùng bảng băm (hash table) đếm số lần xuất hiện nhiều nhất của số thực để tìm d.
• Số lượng 0 sẽ là số lần xuất hiện nhiều nhất + (số cặp a[i] và b[i] đều bằng 0).

Ví dụ

// C++ tìm d và số 0 trong mảng C
#include <bits/stdc++.h>
using namespace std;

void findDandZeros1(int a[], int b[], int m){
    unordered_map<long double, int> mpp1;
    int count1 = 0;
    for (int i = 0; i < m; i++) {
        if (b[i] != 0 && a[i] != 0) {
            long double val1 = (long double)(-1.0 * b[i]) / (long double)(a[i]);
            mpp1[val1] += 1;
        }
        else if (b[i] == 0 && a[i] == 0)
            count1 += 1;
    }
    int maxi1 = 0;
    for (auto it : mpp1)
        maxi1 = max(it.second, maxi1);
    for (auto it : mpp1) {
        if (it.second == maxi1) {
            cout << "Giá trị d: " << it.first << endl;
            break;
        }
    }
    cout << "Số 0 trong mảng C: " << maxi1 + count1;
}

int main(){
    int a[] = { 15, 40, 45 };
    int b[] = { 4, 5, 6 };
    int m = sizeof(a) / sizeof(a[0]);
    findDandZeros1(a, b, m);
    return 0;
}

Đầu ra

Giá trị d: -0.133333 Số 0 trong mảng C: 1