Предположим, что у нас есть набор удвоений s, что-то вроде этого:
1.11, 1.60, 5.30, 4.10, 4.05, 4.90, 4.89
Теперь мы хотим найти наименьший положительный целочисленный масштабный коэффициент x, чтобы любой элемент s, умноженный на x, находился в пределах одной десятой от целого числа.
Извините, если это не очень понятно - просим уточнить, если это необходимо.
Пожалуйста, ограничьте ответы на языки C-стиля или алгоритмический псевдокод.
Спасибо!
Вы ищете нечто, называемое одновременным диофантовым приближением. Обычное утверждение состоит в том, что вам даны действительные числа a_1, ..., a_n и положительные реальные epsilon, и вы хотите найти целые числа P_1, ..., P_n и Q, чтобы |Q*a_j - P_j| < epsilon, надеюсь, с Q как можно меньше.
Это очень хорошо изученная проблема с известными алгоритмами. Однако вы должны знать, что NP-сложно найти наилучшее приближение с помощью Q < q, где Q - это еще одна часть спецификации. Насколько мне известно, это не относится к вашей проблеме, потому что у вас есть фиксированный epsilon и вы хотите наименьший Q, а не наоборот.
Одним из алгоритмов проблемы является алгоритм восстановления решетки Ленстра-Ленстры - Ловаша. Интересно, могу ли я найти хорошие ссылки для вас. Эти примечания к классу упоминают проблему и алгоритм, но, вероятно, не имеют прямой помощи. В Википедии есть довольно подробная страница по алгоритму, включая довольно большой список реализаций.
Чтобы ответить на модифицированный вопрос Влада (если вы хотите получить точные целые числа после умножения), ответ известен. Если ваши числа являются рациональными a1/b1, a2/b2, ..., aN/bN, а сокращения фракций (ai и bi относительно простые), то число, которое нужно умножить на, является наименьшим общим кратным b1, ..., bN.
Это не полный ответ, но некоторые предложения:
Примечание. Я использую "s" для масштабного коэффициента и "x" для удвоений.
Прежде всего, спросите себя, не работает ли грубая сила. Например. попробуйте s = 1, затем s = 2, затем s = 3 и т.д. s
У нас есть список чисел x [i] и допуск t = 1/10. Мы хотим найти наименьшее натуральное число s, такое, что для каждого x [i] существует целое число q [i] такое, что | s * x [i] - q [i] | < т.
Прежде всего заметим, что если мы можем создать упорядоченный список для каждого x [i], достаточно просто объединить их, чтобы найти наименьший s, который будет работать для всех них. Во-вторых, заметим, что ответ зависит только от дробной части x [i].
Переставляя вышеприведенный тест, имеем | x - q/s | < т/с. То есть мы хотим найти "хорошее" рациональное приближение для x в том смысле, что приближение должно быть лучше, чем t/s. Математики изучили вариант этого, где критерий "хорошего" заключается в том, что он должен быть лучше любого с меньшим значением "s", и лучший способ его найти - это усечения продолжение фракции.
К сожалению, это не совсем то, что вам нужно, так как, как только вы попадаете под свою толерантность, вам необязательно продолжать улучшаться - такая же толерантность будет работать. Следующая очевидная вещь - использовать это, чтобы перейти к первому числу, которое будет работать, и сделать грубую силу оттуда. К сожалению, для любого числа наибольшее из первых может быть 5, так что вы не купите столько всего. Однако этот метод найдет вас, который работает, а не самый маленький. Можем ли мы использовать это, чтобы найти меньший, если он существует? Я не знаю, но он установит верхний предел для принудительного принуждения.
Кроме того, если вам нужно, чтобы допуск для каждого x был < t, то это означает, что допуск для продукта всех x должен быть равным < т ^ п. Это может позволить вам многое пропустить и установить разумный нижний предел для принудительного принуждения.