Существует ли алгоритм поиска ближайшего числа с небольшими факторами?

Ответ 1

Быстрый алгоритм для пар факторов

Это не совсем решает проблему, как указано - с учетом целого x, она найдет только ближайшее большее или равное число, у которого нет факторов помимо 2 и 3 (или любой другой заданной пары факторов). Но я думаю, что это мило, и поскольку он работает в O (log x) и O (1), это может быть полезно независимо! Это похоже на концепцию алгоритма линии Брешенема. В псевдокоде:

• Начнем с b = y = 2 ^ RoundUp (log2 (x)), что гарантирует, что b = y >= x.
• Если y < х, то положим у = у * 3 и перейдем к 2.
• Если y < b затем установите b = y. (b показывает лучший кандидат до сих пор.)
• Если y нечетно, остановите и верните b.
• В противном случае установите y = y/2 и перейдите к 2.

Корректность

Почему это работает? Заметим, что во всех случаях у = 2 ^ я * 3 ^ j для некоторого i, j > 0 и что со временем я только когда-либо уменьшается, а j только когда-либо возрастает. Инвариант, который мы поддерживаем при входе на этап 2, "Любое значение z = 2 ^ a * 3 ^ b, имеющее a > я или b, как известно, неинтересно (т.е. Неверно или не лучше чем какое-то уже обнаруженное решение), и поэтому не нужно рассматривать" . Это, очевидно, верно в первый раз, когда мы приходим к шагу 2, так как y является степенью 2 и уже >= x, поэтому любое число z = 2 ^ a * 3 ^ b с a > я тогда будет по крайней мере 2 * y (независимо от b), который хуже y; и ни одно целое z не может иметь меньше j = 0 степеней 3 в y.

(Другой способ сформулировать этот инвариант: "Либо мы уже нашли оптимальное решение, либо это некоторое число z = 2 ^ a * 3 ^ b с <= я и b >= j." )

Если условие на шаге 2 выполняется "y < x" , то y = 2 ^ я * 3 ^ j не является допустимым решением, поскольку оно слишком мало. Более ясно, что ясно, что для любого a <= i, 2 ^ a * 3 ^ j также не может быть допустимым решением, так как любое такое решение не менее, чем y. Итак, теперь мы знаем (от инварианта), что любая пара (a, b), удовлетворяющая (a > я OR b < j), неинтересна, и мы знаем из теста "y < x" , что только что удалось, что любая пара ( a, b), удовлетворяющих (a <= я AND b = j), также неинтересны. Теперь рассмотрим любую пару (a, b), удовлетворяющую слегка отличающемуся условию (a > я OR b < j + 1): если (a, b) не удовлетворяет первому условию (от инварианта) для неинтересности, то мы имеем ((a > я OR b < j + 1) AND! (a > я OR b < j)), что упрощает ((a > я OR b < j + 1) AND (a <= я И b >= j)) через правило Де Моргана, а затем (b < j + 1 AND a <= я AND b >= j) (поскольку создание (a <= я AND b >= j) истинно требует (a <= i) быть истинным, заставляя (a > i) быть ложным и, таким образом, позволяя исключить его из OR), который, очевидно, совпадает с (a <= я AND b = j) - но это именно то условие, для которого мы только что установили второй вид неинтересности, благодаря успеху теста "y < x" . Таким образом, это устанавливает, что любая пара (a, b), удовлетворяющая (a > я OR b < j + 1), неинтересна, что после приращения j становится именно инвариантом, который мы хотим сохранить.

Обоснование для уменьшения я на шаге 5 почти одинаково, но наоборот, поэтому я не буду подробно останавливаться на нем. Небольшое различие заключается в том, что если мы перейдем к шагу 5, вместо того, чтобы иметь недействительное решение, у нас просто есть решение, которое по крайней мере выше, чем лучшее решение в b (обратите внимание, что мы обновили b, если это необходимо, чтобы это продолжалось hold), и поэтому оно и каждое высшее решение (с этой точки) неинтересны нам.

Каждое значение y, сгенерированное алгоритмом, имеет один коэффициент меньше 2 или еще один коэффициент 3, чем любое ранее сгенерированное значение, поэтому ясно, что все сгенерированные значения y различны. Обоснование в предыдущих параграфах устанавливает, что единственные значения y, которые не генерируются, - это те, которые оказались неинтересными. Таким образом, если алгоритм всегда останавливается за конечное время, это верно. Следующий раздел будет означать, что это действительно так.

Время работы

Шаг 5 (который приводит к уменьшению я на 1) никогда не выполняет больше, чем log2 (x) +1 раз, так как я начинается с этого значения или меньше, ничто иное не влияет на i, а когда я достигает 0, y будет быть нечетным, заставляя шаг 4 прекратить выполнение функции. Но сколько раз может быть условие на шаге 2, которое увеличивает j на 1 огонь?

Изначально y >= x, поэтому достижение y < x, необходимое для шага 2 для стрельбы, требует выполнения шага 5. Но как только y < x достигается посредством некоторого выполнения шага 5, он немедленно отменяется при следующем выполнении шага 2: это потому, что для того, чтобы выполнить этап 5 вообще, мы должны были иметь y >= x, и если мы разделим y на 2 (на этом шаге 5), а затем умножьте его на 3 (на следующем шаге 2), он обязательно будет, по крайней мере, таким же большим, как и ранее, подразумевая, что y >= x снова, в свою очередь, подразумевая, что шаг 2 никогда не будет срабатывать дважды подряд без выполнения шага 5 между ними. Таким образом, шаг 2 будет срабатывать не чаще, чем шаг 5, т.е. Не более log2 (x) +1 раз. Это ограничивает общее время выполнения алгоритма в O (log x).

Примечания

• Вы можете избежать арифметики с плавающей запятой, заменив log2() на шаге 1 циклом, который запускает y в 1 и удваивает его до тех пор, пока он не станет = = x. Это O (log x), и это не повредит временной сложности.
• Вы можете использовать любую другую пару факторов. Единственное реальное изменение заключается в том, что если f является фактором, "заменяющим" 2 в коде, тогда шаг 4 должен вместо этого останавливаться, когда y% f!= 0.

Ответ 2

Есть ровно 265 чисел, которые делятся только на 2,3,5 в диапазоне от 1 до 50000. Таким образом, вы можете сделать небольшую таблицу и посмотреть ответ в таблице. Однако на моем компьютере требуется около 6,5 микросекунд, чтобы найти ближайшее 2-3-5-факторизуемое число для данного номера, поэтому я бы сказал, что грубая сила достаточно хороша.

int isValid( int n )
{
    while ( n%2 == 0 )
        n /= 2;
    while ( n%3 == 0 )
        n /= 3;
    while ( n%5 == 0 )
        n /= 5;

    return n == 1;
}

int findBest( int n )
{
    for ( int i = 0; i < n; i++ )
    {
        if ( isValid(n+i) )
            return n+i;
        if ( isValid(n-i) )
            return n-i;
    }
    return 0;   // should never get here
}

int main( void )
{
    for ( int n = 1; n <= 50000; n++ )
        printf( "%d->%d\n", n,findBest(n) );
}

Ответ 3

Я не уверен, есть ли какое-либо эффективное решение this.Bowow - это метод грубой силы для нахождения ближайшего числа до n.

    int diff=Integer.MAX_VALUE;
    int num=0;
    public void closestNumber(int n,int curr)
    {
        if(diff < Math.abs(n -curr) && curr  >= n)
        return;
        if(diff >= Math.abs(n -curr))
        {
            diff = Math.abs(n -curr);
            num=curr;
        }
        closestNumber(n,curr*2);
        closestNumber(n,curr*3);
        closestNumber(n,curr*5);

    }


closestNumber(n,1);

System.out.println("closest number: "+num);

Ответ 4

Edit:

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

Оригинал:

Ряд чисел, делящихся на 2, 3 или 5, OEIS A080671 и имеет простую рекурсивную формулу a (n + 22) = (п) +30. Кроме того, серия удобно имеет только одноцелые пробелы. Это означает, что вы можете просто определить, находится ли ваш номер в одном из этих пробелов и выбрать либо следующее, либо следующее целое число.

class NumberFinder
{
public:
    NumberFinder()
    {
        for (int i = 0; i < 2 * 3 * 5; i++)
        {
            bool hasSmallFactors =
                (i % 2 == 0) ||
                (i % 3 == 0) ||
                (i % 5 == 0);
            series.push_back(hasSmallFactors);
        }
    }

    int Find(int n)
    {
        int x = n % (2 * 3 * 5);
        if (series[x]) return n; // already good
        return n + 1; // guaranteed to be good
    }

private:
    vector<bool> series;
};

Это также может быть обобщено на любой набор желаемых факторов:

class NumberFinder
{
public:
    NumberFinder(vector<int> factors)
    {
        product = 1;
        for (auto factor : factors) product *= factor;
        for (int i = 0; i < product; i++)
        {
            bool hasSmallFactors = false;
            for (auto factor : factors)
            {
                if (i % factor == 0) hasSmallFactors = true;
            }
            series.push_back(hasSmallFactors);
        }
    }

    int Find(int n)
    {
        int lo = n;
        int hi = n;
        bool found = series[n % product];
        while (!found)
        {
            if (--lo < 0) lo = 0;
            hi++;
            found = series[hi % product] || series[lo % product];
        }
        if (series[lo % product]) return lo;
        return hi;
    }

private:
    int product;
    vector<bool> series;
};