最大除数使得两个数除以它的数值相同？

Question

我有一个算法可以解释为将数字行分成相同数量的块.为简单起见,我会坚持使用[0,1],它将被分割为:

0|----|----|----|----|1

我需要做的是取一个数字范围[j,k]并找到最大数量的块,N,最多到某个最大值M,这将分割数字线,使[j,k]仍然全部落入同样的"垃圾箱".这比它听起来更棘手,因为范围可以像这样跨越一个箱子:

    j|-|k
0|----|----|----|----|1

因此,在完全包含范围之前,您可能必须达到相当低的数字.更重要的是,随着箱柜数量的增加,范围可能会移入和移出单个箱柜,因此存在局部最小值.

显而易见的答案是从M箱开始,并减少数量,直到范围落入单个箱.但是,我想知道是否有比列举所有可能的划分更快的方法,因为我的最大数量可以合理地大(8000万左右).

有更好的算法吗？

Answer 1

在这里我想给出另一个启发式，它与 btilly 的不同。

任务是找到整数m，n使得m / n <= j < k <= (m + 1) / n，n尽可能大（但仍低于M）。

直观上，该分数最好m / n接近j。这导致了使用连分数的想法。

我提出的算法非常简单：

1. 使用减号计算 的所有连分数j（以便分数始终j从上方逼近），直到分母超过M；
2. 对于每个这样的分数，找到满足和 的m / n最大整数，并将分数替换为;i >= 0k <= (m * i + 1) / (n * i)n * i <= Mm / n(m * i) / (n * i)
3. 在2的所有分数中，找出分母最大的那个。

j该算法在和中不对称k。因此，存在一个类似的k版本，通常不应给出相同的答案，以便您可以从两个结果中选择较大的一个。

示例：这里我将采用 btilly 的示例：j = 0.6和k = 0.65，但我将采用M = 10.

我将首先执行j程序。为了计算 的连分式展开式j，我们计算：

  0.6
= 0 + 0.6
= 0 + 1 / (2 - 0.3333)
= 0 + 1 / (2 - 1 / (3 - 0))

由于0.6是有理数，因此展开式以有限多个步骤终止。相应的分数是：

0 = 0 / 1
0 + 1 / 2 = 1 / 2
0 + 1 / (2 - 1 / 3) = 3 / 5

计算步骤2中的相应i值，我们将三个派别替换为：

0 / 1 = 0 / 1
1 / 2 = 3 / 6
3 / 5 = 6 / 10

最大分母由 给出6 / 10。

继续上面的例子，相应的k过程如下：

  0.65
= 1 - 0.35
= 1 - 1 / (3 - 0.1429)
= 1 - 1 / (3 - 1 / (7 - 0))

因此相应的分数：

1 = 1 / 1
1 - 1 / 3 = 2 / 3
1 - 1 / (3 - 1 / 7) = 13 / 20

通过第2步，我们得到：

1 / 1 = 2 / 2
2 / 3 = 6 / 9
13 / 20 = 0 / 0 (this is because 20 is already bigger than M = 10)

最大分母由 给出6 / 9。

编辑：实验结果。

令我惊讶的是，该算法的效果比我想象的要好。

我做了以下实验，忽略了边界M（相当于，可以取M足够大的值）。

在每一轮中，我(j, k)在 的区间内[0, 1)生成一对均匀分布的随机数j < k。如果差值k - j小于1e-4，我就丢弃这一对，使这一轮无效。否则，我使用朴素算法计算真实结果trueN，并使用我的算法计算启发式结果heurN，并将它们添加到统计数据中。这适用于 1e6 轮。

结果如下：

effective round     =  999789
sum of trueN        =  14013312
sum of heurN        =  13907575
correct percentage  =  99.2262 %
average quotient    =  0.999415

是等于 的correct percentage有效回合的百分比，是所有有效回合的商的平均值。trueNheurNaverage quotientheurN / trueN

因此，该方法在 99% 以上的情况下给出了正确答案。

我也用较小的M值做了实验，结果是相似的。