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

Question

Предположим, у нас есть набор значений типа double s , что-то вроде этого:

1.11, 1.60, 5.30, 4.10, 4.05, 4.90, 4.89

Теперь мы хотим найти наименьший положительный целочисленный масштабный коэффициент x , который любой элемент из s , умноженный на x , находится в пределах одной десятой целого числа .

Извините, если это не очень ясно, пожалуйста, попросите разъяснений, если это необходимо.

Пожалуйста, ограничьте ответы на языки стиля C или алгоритмический псевдокод.

Спасибо!

Answer 1

Вы ищете что-то под названием одновременное диофантово приближение . Обычное утверждение состоит в том, что вам даны действительные числа a_1, ..., a_n и положительное действительное число epsilon, и вы хотите найти целые числа P_1, ..., P_n и Q, чтобы |Q*a_j - P_j| < epsilon, возможно, с Q как можно меньшим.

Это очень хорошо изученная проблема с известными алгоритмами. Тем не менее, вы должны знать, что NP-трудно найти лучшее приближение с Q < q, где q - другая часть спецификации. Насколько я понимаю, это не относится к вашей проблеме, потому что у вас есть фиксированный epsilon и вы хотите наименьшее Q, а не наоборот.

Один алгоритм для этой задачи - это алгоритм Ленстраса-Ловаша-Ловаша. Интересно, смогу ли я найти какие-нибудь хорошие ссылки для вас. В этих примечаниях к классу упоминаются проблема и алгоритм, но, вероятно, они не помогут. В Википедии есть довольно подробная страница об алгоритме, включая довольно большой список реализаций.

Answer 2

Чтобы ответить на модифицированный вопрос Влада (если вы хотите точные целые числа после умножения), ответ известен. Если ваши числа являются рациональными a1/b1, a2/b2, ..., aN/bN, с уменьшенными дробями (ai и bi относительно простые числа), то число, на которое нужно умножить, является наименьшим общим кратным b1, ..., bN.

Answer 3

Это не полный ответ, но некоторые предложения:

Примечание: я использую "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», и лучший способ найти их - это усечения непрерывного расширения дроби <a href="http://en.wikipedia.org/wiki/Continued_fraction" rel="nofollow">.1012 *.

К сожалению, это не совсем то, что вам нужно, поскольку, когда вы попадаете под свою терпимость, вам не обязательно продолжать становиться все лучше и лучше - такая же терпимость будет работать.Следующая очевидная вещь состоит в том, чтобы использовать это, чтобы перейти к первому числу, которое будет работать, и применить грубую силу оттуда.К сожалению, для любого числа наибольшее первое s может быть 5, так что это не так уж и много.Тем не менее, этот метод найдет вам работающие, но не самые маленькие.Можем ли мы использовать эти s, чтобы найти меньший, если он существует?Я не знаю, но он установит верхний предел для грубой силы.

Кроме того, если вам нужно, чтобы допуск для каждого x был