Мне нужно сделать DFT реального времени, и используемый мною алгоритм является наиболее эффективным, когда количество выборок можно разбить на небольшие факторы.
Предположим, что у меня есть число n и факторы 2, 3, 5. Как найти ближайшее число (по сравнению с n), чья основная факторизация состоит не из чисел, кроме 2,3,5?
n почти всегда ниже 50,000, поэтому грубое форсирование может быть хорошей идеей.
Это не совсем решает проблему, как указано - с учетом целого x, она найдет только ближайшее большее или равное число, у которого нет факторов помимо 2 и 3 (или любой другой заданной пары факторов). Но я думаю, что это мило, и поскольку он работает в O (log x) и O (1), это может быть полезно независимо! Это похоже на концепцию алгоритма линии Брешенема. В псевдокоде:
Почему это работает? Заметим, что во всех случаях у = 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).
Есть ровно 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) );
}
Я не уверен, есть ли какое-либо эффективное решение 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);
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;
};