Как я могу минимизировать два целых числа, чтобы их произведение было меньше определенного значения?

Question

Учитывая два целых числа, как я могу минимизировать их так, чтобы их произведение было меньше, чем какое-либо другое значение, при этом сохраняя их относительное соотношение?

Это формальная проблема. Практическая проблема заключается в следующем: у меня есть разрешение пикселей ширины / высоты, содержащее случайные значения (от 1 до 8192 для любого измерения). Я хочу настроить пары значений так, чтобы их произведение не превышало некоторого общего количества пикселей (например, 1000000), и мне нужно убедиться, что соотношение сторон настроенного разрешения остается прежним (например, 1.7777).

Наивный подход состоит в том, чтобы просто запустить al oop, где я каждый раз вычитаю 1 из ширины, регулируя высоту в соответствии с соотношением сторон, пока их произведение не окажется ниже порогового значения. Пример:

int wid = 1920;
int hei = 1080;
float aspect = wid / (float)hei;
int maxPixels = 1000000;
while (wid * hei > maxPixels)
{
    wid -= 1;
    hei = wid / aspect;
}

Конечно, должен быть более аналитический подход к этой проблеме, хотя?

Answer 1

mascoj придумал ответ , но вот интерпретация в кодовой форме:

#include <utility>
#include <numeric>
#include <cmath>
#include <iostream>

// Mathsy stuff

std::pair<uint64_t, uint64_t> ReduceRatio(const uint64_t W, const uint64_t H)
{
    const double D = std::gcd(W, H);
    return {W/D, H/D};
}

std::pair<uint64_t, uint64_t> Maximise(const uint64_t C, const uint64_t W, const uint64_t H)
{
    const auto [x, y] = ReduceRatio(W, H);
    const uint64_t F = std::floor(std::sqrt(C/double(x*y)));

    const uint64_t A = x*F;
    const uint64_t B = y*F;

    return {A, B};
}


// Test harness

void Test(const uint64_t MaxProduct, const uint64_t W, const uint64_t H)
{
    const auto [NewW, NewH] = Maximise(MaxProduct, W, H);

    std::cout << W << "\u00D7" << H << " (" << (W*H) << " pixels)";

    if (NewW > W)
        std::cout << '\n';
    else
        std::cout << " => " << NewW << "\u00D7" << NewH << " (" << (NewW * NewH) << " pixels)\n";
}

int main()
{
    Test(100000, 1024, 768);
    Test(100000, 1920, 1080);
    Test(500000, 1920, 1080);
    Test(1000000, 1920, 1080);
    Test(2000000, 1920, 1080);
    Test(4000000, 1920, 1080);
}

// g++ -std=c++17 -O2 -Wall -pedantic -pthread main.cpp && ./a.out
// 1024×768 (786432 pixels) => 364×273 (99372 pixels)
// 1920×1080 (2073600 pixels) => 416×234 (97344 pixels)
// 1920×1080 (2073600 pixels) => 928×522 (484416 pixels)
// 1920×1080 (2073600 pixels) => 1328×747 (992016 pixels)
// 1920×1080 (2073600 pixels) => 1872×1053 (1971216 pixels)
// 1920×1080 (2073600 pixels)

Answer 2

Редактировать: неверное прочтение исходного вопроса.

Еще один способ сформулировать ваш вопрос с помощью W и H, что является самым большим a и b, таким, что a/b = W/H и a*b < C где C - ваш лимит на

. Для этого найдите D = gcd(W,H) или наибольший общий делитель W и H. Наибольший общий знаменатель обычно находится с помощью евклидова алгоритма.

Установите x = W/D и y = H/D, это минимальное решение с тем же соотношением.

Чтобы получить максимумы при C, начнем с неравенства F*x*F*y <= C, где F будет нашим масштабным коэффициентом для x и y

Алгебра:

F^2 <= C/(x*y)

F <= sqrt(C/(x*y))

Поскольку мы хотим, чтобы F было целым числом и строго меньше указанного выше,

F = floor(sqrt(C/(x*y)))

Это даст вам новое решение A = x*F и B = y*F где A*B < C и A/B = W/H.