Аппроксимация общего делителя, ближайшего к некоторому значению?

Question

Скажем, у нас есть два числа (не обязательно целые числа) x1 и x2. Скажем, пользователь вводит число y. То, что я хочу найти, это число y', близкое к y, так что x1 % y' и x2 % y' очень малы (например, меньше 0.02, но давайте назовем этот номер LIMIT). Другими словами, мне не нужен оптимальный алгоритм, но хорошее приближение.

Я благодарю вас всех за ваше время и усилия, это очень мило!

---

Позвольте мне объяснить, в чем проблема в моем приложении : скажем, дан размер экрана с шириной screenWidth и высотой screenHeight (в пикселях). Я заполняю экран квадратами длиной y'. Скажем, пользователь хочет, чтобы размер квадрата был y. Если y не является делителем screenWidth и / или screenHeight, по бокам экрана будет неиспользуемое пространство, недостаточно большое для размещения квадратов. Если это неиспользуемое пространство мало (например, один ряд пикселей), это не так уж плохо, но если нет, то оно не будет хорошо выглядеть. Как мне найти общие делители screenWidth и screenHeight?

Answer 1

Я не понимаю, как вы можете убедиться, что x1% y 'и x2% y' оба ниже некоторого значения - если x1 простое, ничто не будет ниже вашего предела (если предел ниже 1), кромеx1 (или очень близко) и 1.

Так что единственный ответ, который всегда работает, это тривиальный y '= 1.

Если вы разрешаете нецелые делители, тогда просто выберите y'= 1 / (x1 * x2), поскольку остаток всегда равен 0.

Без ограничения общего делителя целыми числами это может быть что угодно, и весь концепт «наибольший общий делитель» выходит из окна.

Answer 2

Вы хотите разместить максимальное количество равномерно распределенных квадратов внутри фиксированной области.Можно найти оптимальное решение для вашей задачи с помощью простой математики.

Допустим, у вас есть область с шириной = W и высотой = H, и вы пытаетесь подогнать квадраты со сторонами длины = x.Максимальное количество квадратов по горизонтали и вертикали, которые я назову max_hor и max_vert соответственно, это max_hor = floor (W / x) и max_vert = floor (H / x).Если вы рисуете все квадраты бок о бок, без пробелов, в каждой строке и каждом столбце будет отдых.Позволяет вызывать горизонтальные / вертикальные остатки соответственно rest_w и rest_h.Этот случай иллюстрируется на рисунке ниже:

Обратите внимание, что rest_w = W-max_hor x и rest_h = H-max_vert x.

То, что вы хотите, это разделить rest_w и rest_h на равные, генерируя небольшие горизонтальные и вертикальные пробелы размеров space_w и space_h, как показано на рисунке ниже:

Обратите внимание, что space_w = rest_w / (max_hor + 1) и space_h = rest_h / (max_vert + 1).

Это число, которое выищете?

Answer 3

x1 и x2 не очень большие, поэтому простой алгоритм грубой силы должен быть достаточно хорошим.

Разделите x1 и x2 на y и вычислите пол и потолок результатов. Это дает четыре числа: x1f, x1c, y1f, y1c.

Выберите одно из этих чисел, ближайшее к точному значению x1/y (для x1f, x1c) или x2/y (for y1f, y1c). Пусть это будет x1f, например. Установите y' = x1/x1f. Если значения x1%y' и y1%y' не превышают limit, успех (y' является наилучшим приближением). В противном случае добавьте x1f - 1 к пулу из четырех чисел (или y1f - 1, или x1c + 1, или y1c + 1), выберите другой ближайший номер и повторите.

Answer 4

Я считаю, что допустил ошибку, но не понимаю почему. Основываясь на ответе Фила Х , я решил ограничиться целочисленными значениями, но умножить x1 и x2 на степень 10. После этого я разделю обычные целочисленные делители на это число.

В сети я нашел калькулятор общих факторов . Экспериментируя с этим, я понял, что это не даст мне общих делителей ... Я пробовал несколько случаев (x1 = 878000 и x2 = 1440000 и некоторые другие), и ни один из них не дал хороших результатов.

Другими словами, вам, вероятно, придется умножаться на очень большие числа, чтобы достичь результатов, но это сделает расчет очень и очень медленным.

Если у кого-нибудь есть решение этой проблемы, это было бы замечательно. Однако сейчас я решил воспользоваться тем, что screenWidth и screenHeight - это хорошие числа для работы, так как они являются размером экрана компьютера. 900 и 1440 имеют более чем достаточно общих делителей, поэтому я могу работать с этим ...

Спасибо всем за ответы в этой теме и в m y предыдущей теме об оптимальном алгоритме для этой задачи .