โปรแกรม C++ หาค่าจำนวนเต็มบวก x ต่ำสุดที่ทำให้ a(x^2) + b(x) + c >= k

สมมติว่าเรามีจำนวนเต็มสี่จำนวน a, b, c และ k เราต้องหาค่า x ที่น้อยที่สุดและเป็นบวก ที่ทำให้สมการต่อไปนี้เป็นจริง:

a*x^2 + b*x + c >= k

ถ้า a = 3, b = 4, c = 5 และ k = 6 ผลลัพธ์จะเป็น 1

เพื่อแก้ปัญหานี้ เราจะใช้วิธีแบ่งครึ่ง (bisection approach) ขีดจำกัดล่างจะเป็น 0 เนื่องจาก x ต้องเป็นจำนวนเต็มบวกขั้นต่ำ

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

int getMinX(int a, int b, int c, int k) {
    int x = INT8_MAX;
    if (k <= c)
        return 0;
    int right = k - c;
    int left = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        int val = (a * mid * mid) + (b * mid);
        if (val > (k - c)) {
            x = min(x, mid);
            right = mid - 1;
        }
        else if (val < (k - c))
            left = mid + 1;
        else
            return mid;
    }
    return x;
}

int main() {
    int a = 3, b = 2, c = 4, k = 15;
    cout << "Minimum value of x is: " << getMinX(a, b, c, k);
}

ผลลัพธ์

Minimum value of x is: 2