algorithm - 什么算法可以让一个数字最接近一个可以均匀(在一定范围内)分成两个其他常数的常数？

Question

所以假设我有数字 A=1483 和 B = 635。我的 X=100.0

假设我允许的 margin 是 10.0

获得最接近 X(可以是 float )且余数小于 MARGIN 的 A 和 B 的最佳方法是什么？

对于答案 K。A % K <= MARGIN，B % K <= MARGIN，K 尽可能接近 X，例如 |K - X| < 100

Answer 1

让我们尝试用数学符号来写问题。

您拥有的是欧几里德除法:

A = Q1*X + R1
B = Q2*X + R2

你想找到最小的|x|这样

A = Q1'*(X+x) + R1' , |R1'| <= M
B = Q2'*(X+x) + R2' , |R2'| <= M

为了帮助您找到这样的 x，您有如下关系:

A = Q1*(X+x) + R1-Q1*x
B = Q2*(X+x) + R2-Q2*x

从这里开始，您应该首先专注于如何解决您给出的示例，然后尝试概括。

1483 = 14*100 + 83 = 15*100 - 17
 635 =  6*100 + 35 =  7*100 - 65

您应该取 x > 0 以将 R2 (35) 降低至 10，还是取 x < 0 以将 R1 (-17) 增加至 -10？

在第一种情况下，x 应该在区间 [25/6 , 45/6] 内才能带来 |R2'| <= M，但同时必须在区间 [73/14 , 93/14] 才能带上 |R1'| <= M.

这些间隔是否重叠？

• 如果是，您有解决方案。
• 如果不是，那么您必须进一步尝试(递减商数 Q1' 和/或 Q2')

只需咨询任何体面的解释器(此处为 Squeak/Pharo Smalltalk)

 {25/6 . 45/6. 73/14 . 93/14} sorted
 = {(25/6) . (73/14) . (93/14) . (15/2)}

所以它们重叠，从 x=73/14 开始。
但也许你会在另一个方向上得到更近的 x？

我没有给出算法，只是一个线索，由你继续。但是你会看到增量不一定是随机的(比如 0.001)。