12

我需要做一些实时 DFT，当样本数量可以分解为小因素时，我使用的算法是最有效的。

假设我有一个数字n和因素2, 3, 5。如何找到最接近的数（与 相比n），其素数分解不包含除 以外的数字2,3,5？

n几乎总是低于50,000所以蛮力可能是一个好主意。

4

4 回答 4

4

在 1 到 50000 的范围内，恰好有 265 个数字只能被 2,3,5 整除。所以你可以做一个小表格，然后在表格中查找答案。但是，在我的计算机上，平均需要 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) );
}
于 2016-08-20T03:08:12.797 回答
3

因子对的快速算法

这并不能完全解决上述问题——给定一些整数 x，它只会找到除 2 和 3（或任何其他给定的因子对）之外没有因子的最接近的大于或等于数字。但我认为它很可爱，因为它在 O(log x) 时间和 O(1) 空间中运行，无论如何它可能很有用！它在概念上类似于 Bresenham 线算法。在伪代码中：

  1. 从 b = y = 2^RoundUp(log2(x)) 开始，这确保 b = y >= x。
  2. 如果 y < x 则设置 y = y * 3 并转到 2。
  3. 如果 y < b 则设置 b = y。（b 记录了迄今为止最好的候选人。）
  4. 如果 y 是奇数，则停止并返回 b。
  5. 否则，设置 y = y / 2 并转到 2。

正确性

为什么这行得通？请注意，对于某些 i，我们始终有 y = 2^i*3^j，j >= 0，并且随着时间的推移，i 只会减少，而 j 只会增加。我们在进入步骤 2 时维护的不变量是“已知任何具有 a > i 或 b < j 的值 z = 2^a*3^b 都是无趣的（即，无效或不比某些已经发现的解决方案更好），所以不需要考虑”。当我们第一次到达第 2 步时，这显然是正确的，因为 y 是 2 的幂并且已经 >= x，所以任何数字 z = 2^a*3^b 且 a > i 将至少为 2*y （不管 b）哪个比 y 差；并且任何整数 z 的值都不能小于 y 中 3 的 j = 0 次方。

（陈述这个不变量的另一种方式是“要么我们已经找到了最优解，要么是某个数字 z = 2^a*3^b 且 a <= i 和 b >= j。”）

如果满足第 2 步的条件“y < x”，则 y = 2^i*3^j 不是一个有效的解决方案，因为它太低了。更强烈的是，很明显对于任何 a <= i，2^a*3^j 也不能是有效的解决方案，因为任何这样的解决方案至少与 y 一样低。所以现在我们知道（从不变量）任何满足 (a > i OR b < j) 的对 (a, b) 都是无趣的，并且我们从刚刚成功的“y < x”测试中知道任何对 (a, b) 满足 (a <= i AND b = j) 也无趣。现在考虑满足稍微不同的条件 (a > i OR b < j+1) 的任何对 (a, b)：如果 (a, b) 不满足第一个无趣条件（来自不变量），那么我们有 ( (a > i OR b < j+1) AND !(a > i OR b < j))，简化为 ((a > i OR b < j+1) AND (a <= i AND b > = j)) 通过德摩根规则，然后到 (b < j+1 AND a <= i AND b >= j) （因为使 (a <= i AND b >= j) 为真需要 (a <= i ) 为真，迫使 (a > i) 为假，从而允许从 OR 中消除它），这显然与 (a <= i AND b = j) 相同——但这正是我们刚刚通过“y < x”测试的成功建立了第二种无趣。因此，这确定了满足 (a > i OR b < j+1) 的任何对 (a, b) 都是无趣的——在增加 j 之后，它恰好成为我们想要保留的不变量。i) 为假，因此允许将其从 OR 中消除），这显然与 (a <= i AND b = j) 相同——但这正是我们刚刚建立第二种无趣的条件，通过“y < x”测试的成功。因此，这确定了满足 (a > i OR b < j+1) 的任何对 (a, b) 都是无趣的——在增加 j 之后，它恰好成为我们想要保留的不变量。i) 为假，因此允许将其从 OR 中排除），这显然与 (a <= i AND b = j) 相同——但这正是我们刚刚建立第二种无趣的条件，通过“y < x”测试的成功。因此，这确定了满足 (a > i OR b < j+1) 的任何对 (a, b) 都是无趣的——在增加 j 之后，它恰好成为我们想要保留的不变量。

在第 5 步中减少 i 的理由几乎相同，但相反，所以我不会详细说明。细微的差别是，如果我们进入第 5 步，而不是得到一个无效的解决方案，我们只是有一个至少与 b 中的最佳解决方案一样高的解决方案（请注意，我们在必要时更新了 b 以便这将继续保持），所以它和每一个更高的解决方案（从这一点开始）对我们来说都是无趣的。

算法生成的每个 y 值要么比任何先前生成的值少一个因子 2，要么多一个因子 3，因此很明显，所有生成的 y 值都是不同的。前面段落中的推理表明，唯一没有生成的 y 值是那些已被证明无趣的值。因此，如果算法总是在有限时间内停止，那么它是正确的。下一节将暗示情况确实如此。

运行时间

第 5 步（具有将 i 减 1 的效果）永远不会执行超过 log2(x)+1 次，因为 i 从这个值或更小开始，没有其他影响 i，当 i 达到 0 时，y 将是奇数，导致步骤 4 终止函数。但是步骤 2 中将 j 增加 1 的条件可以触发多少次？

最初 y >= x，因此要达到第 2 步触发所需的 y < x 条件需要执行第 5 步。但是一旦通过第 5 步的某些执行实现了 y < x，它就会在下一次执行时立即撤消第 2 步：这是因为要完全执行第 5 步，我们必须有 y >= x，如果我们将 y 除以 2（在第 5 步）然后乘以 3（在下一步2)，它必须至少和以前一样大，这意味着 y >= x 再次意味着步骤 2 将永远不会连续触发两次，而不会在两者之间执行步骤 5。因此，第 2 步将最多触发第 5 步的次数，即最多 log2(x)+1 次。这将算法的整体运行时间限制在 O(log x)。

笔记

  • 您可以通过将步骤 1 中的 log2() 替换为从 1 开始 y 并不断加倍直到 >= x 的循环来避免浮点运算。这是 O(log x)，因此不会影响时间复杂度。
  • 您可以使用任何其他一对因子。唯一真正的变化是，如果 f 是代码中“替换” 2 的因素，那么步骤 4 应该在 y % f != 0 时停止。
于 2016-08-20T03:21:08.570 回答
1

我不确定是否有任何有效的解决方案。以下是找到最接近 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);
于 2016-08-19T23:26:59.287 回答
0

编辑：

下面的代码找到最接近目标的数字，该数字可被给定因子集中的至少一个数字整除。它没有为明确的目标提供解决方案，即找到只能被一组给定因子整除的最接近的数字。

原来的：

可被 2、3 或 5 整除的数列是OEIS A080671，具有简单的递归公式 a(n+22) = a(n)+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;
};
于 2016-08-20T00:20:56.657 回答