有没有一种算法可以找到最近的只有小因子的数字？
Is there an algorithm to find the nearest number with only small factors?
我需要做一些实时 DFT，当样本数量可以分解成小因子时，我使用的算法是最有效的。
假设我有一个数字 n 和因数 2, 3, 5。如何找到最接近的数字（与 n 相比），其质因数分解不包含除 2,3,5 以外的数字？
n 几乎总是低于 50,000，因此暴力破解可能是个好主意。
我不确定是否有任何有效的解决方案 this.Below 是寻找最接近 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);
编辑：
下面的代码找到最接近目标的数字，该数字可被给定一组因素中的至少一个数字整除。它没有为明确的目标提供解决方案，即找到可被一组给定因子整除的最接近 的数字。
原文：
可被 2、3 或 5 整除的数列是 OEIS A080671 并且有一个简单的递归公式 a(n+22) = a(n)+30。此外，该系列很方便地只有一个整数间隙。这意味着您可以简单地确定您的数字是否位于这些间隙之一和 select 下一个或上一个整数。
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;
};
在 1 到 50000 的范围内，正好有 265 个数字只能被 2,3,5 整除。所以你可以做一个小 table，然后在 table 中查找答案].但是，在我的计算机上，平均需要 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) );
}
因子对的快速算法
这并不能完全解决所陈述的问题——给定一些整数 x，它只会找到最近的大于或等于除 2 和 3（或任何其他给定的 对个因素）。但我认为它很可爱，因为它在 O(log x) 时间和 O(1) space 内运行，无论如何它都可能有用！它在概念上类似于 Bresenham 线算法。在伪代码中：
- 从 b = y = 2^RoundUp(log2(x)) 开始，它确保 b = y >= x。
- 如果 y < x 则设置 y = y * 3 并转到 2。
- 如果 y < b 则设置 b = y。 (b 记录目前为止最好的候选人。)
- 如果 y 是奇数则停止并且 return b.
- 否则，设置 y = y / 2 并转到 2。
正确性
为什么这行得通？请注意，在任何时候，对于某些 i，j >= 0，我们都有 y = 2^i*3^j，并且随着时间的推移，i 只会减少，而 j 只会增加。我们在步骤 2 的入口处维护的不变量是 "Any value z = 2^a*3^b having a > i or b < j is known to be uninteresting (i.e., invalid or no better than some already-discovered solution), and so doesn't need to be considered"。这在我们第一次到达步骤 2 时显然是正确的，因为 y 是 2 的幂并且已经 >= x，所以任何数字 z = 2^a*3^b 和 > i 将至少是 2*y （不考虑 b）哪个比 y 差；并且任何整数 z 都不能少于 y 中 3 的 j = 0 次方。
（另一种表示此不变量的方法是 "Either we have already found the optimal solution, or it is some number z = 2^a*3^b with a <= i and b >= j."）
如果第 2 步的条件 "y < x" 得到满足，则 y = 2^i*3^j 不是有效解，因为它太低了。更重要的是，对于任何 a <= i，2^a*3^j 显然也不是有效解，因为任何此类解至少与 y 一样低。所以现在我们知道（从不变量）任何对 (a, b) 满足 (a > i OR b < j) 是无趣的，并且我们从 "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 )) 通过 De Morgan 规则，然后到 (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 之后，它恰好成为我们想要保留的不变量。
在第5步中递减i的理由几乎相同，但相反，所以我不再赘述。细微的差别在于，如果我们进行到第 5 步，而不是有一个 无效 解决方案，我们只是有一个至少与 b 中的最佳解决方案一样高的解决方案（注意我们如有必要，更新 b 以便它继续成立），因此它和每个更高的解决方案（从这一点开始）对我们来说都是无趣的。
算法生成的每个 y 值要么比任何先前生成的值少一个 2 的因数，要么多一个 3 的因数，因此很明显所有生成的 y 值都是不同的。前面段落中的推理表明，唯一生成的 y 值 not 是那些已被证明无趣的值。因此，如果算法总是在有限时间内停止，则它是正确的。下一节将暗示确实如此。
运行 时间
第 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 是代码中的因子 "replacing" 2，那么当 y % f != 0.
时，步骤 4 应该停止
我需要做一些实时 DFT，当样本数量可以分解成小因子时，我使用的算法是最有效的。
假设我有一个数字 n 和因数 2, 3, 5。如何找到最接近的数字（与 n 相比），其质因数分解不包含除 2,3,5 以外的数字？
n 几乎总是低于 50,000，因此暴力破解可能是个好主意。
我不确定是否有任何有效的解决方案 this.Below 是寻找最接近 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);
编辑：
下面的代码找到最接近目标的数字，该数字可被给定一组因素中的至少一个数字整除。它没有为明确的目标提供解决方案，即找到可被一组给定因子整除的最接近 的数字。
原文：
可被 2、3 或 5 整除的数列是 OEIS A080671 并且有一个简单的递归公式 a(n+22) = a(n)+30。此外，该系列很方便地只有一个整数间隙。这意味着您可以简单地确定您的数字是否位于这些间隙之一和 select 下一个或上一个整数。
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;
};
在 1 到 50000 的范围内，正好有 265 个数字只能被 2,3,5 整除。所以你可以做一个小 table，然后在 table 中查找答案].但是，在我的计算机上，平均需要 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) );
}
因子对的快速算法
这并不能完全解决所陈述的问题——给定一些整数 x，它只会找到最近的大于或等于除 2 和 3（或任何其他给定的 对个因素）。但我认为它很可爱，因为它在 O(log x) 时间和 O(1) space 内运行，无论如何它都可能有用！它在概念上类似于 Bresenham 线算法。在伪代码中：
- 从 b = y = 2^RoundUp(log2(x)) 开始，它确保 b = y >= x。
- 如果 y < x 则设置 y = y * 3 并转到 2。
- 如果 y < b 则设置 b = y。 (b 记录目前为止最好的候选人。)
- 如果 y 是奇数则停止并且 return b.
- 否则，设置 y = y / 2 并转到 2。
正确性
为什么这行得通？请注意，在任何时候，对于某些 i，j >= 0，我们都有 y = 2^i*3^j，并且随着时间的推移，i 只会减少，而 j 只会增加。我们在步骤 2 的入口处维护的不变量是 "Any value z = 2^a*3^b having a > i or b < j is known to be uninteresting (i.e., invalid or no better than some already-discovered solution), and so doesn't need to be considered"。这在我们第一次到达步骤 2 时显然是正确的，因为 y 是 2 的幂并且已经 >= x，所以任何数字 z = 2^a*3^b 和 > i 将至少是 2*y （不考虑 b）哪个比 y 差；并且任何整数 z 都不能少于 y 中 3 的 j = 0 次方。
（另一种表示此不变量的方法是 "Either we have already found the optimal solution, or it is some number z = 2^a*3^b with a <= i and b >= j."）
如果第 2 步的条件 "y < x" 得到满足，则 y = 2^i*3^j 不是有效解，因为它太低了。更重要的是，对于任何 a <= i，2^a*3^j 显然也不是有效解，因为任何此类解至少与 y 一样低。所以现在我们知道（从不变量）任何对 (a, b) 满足 (a > i OR b < j) 是无趣的，并且我们从 "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 )) 通过 De Morgan 规则，然后到 (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 之后，它恰好成为我们想要保留的不变量。
在第5步中递减i的理由几乎相同，但相反，所以我不再赘述。细微的差别在于，如果我们进行到第 5 步，而不是有一个 无效 解决方案，我们只是有一个至少与 b 中的最佳解决方案一样高的解决方案（注意我们如有必要，更新 b 以便它继续成立），因此它和每个更高的解决方案（从这一点开始）对我们来说都是无趣的。
算法生成的每个 y 值要么比任何先前生成的值少一个 2 的因数，要么多一个 3 的因数，因此很明显所有生成的 y 值都是不同的。前面段落中的推理表明，唯一生成的 y 值 not 是那些已被证明无趣的值。因此，如果算法总是在有限时间内停止，则它是正确的。下一节将暗示确实如此。
运行 时间
第 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 是代码中的因子 "replacing" 2，那么当 y % f != 0. 时，步骤 4 应该停止