3

我们正在寻找一种算法来在 O(N) 下解决这个问题。

给定两个实数 a 和 b（不失一般性，您可以假设它们都在 0 和 1 之间）找到一个介于 -N 和 N 之间的整数 n 以最小化表达式：

|an - b - 圆形(an - b)|

我们认为欧几里得算法可能适用于此，但无法弄清楚。看起来应该有比通过对整数 n 进行详尽搜索更快的方法来做到这一点。

注意：在我们的情况下，a 和 b 可能会经常变化，因此可以为查找表修复 a 和 b，它会变得有点难看，因为 N 也可以变化。还没有详细查看查找表，看看我们可以将它作为 N 的函数得到多小。

4

4 回答 4

1

You are effectively searching for the integer N that makes the expression aN - b as close as possible to an integer. Are a and b fixed? If yes you can pre-compute a lookup table and have O(1) :-)

If not consider looking for the N that makes aN close to I + b for all integers I.

于 2012-01-25T22:43:27.647 回答
1

您可以计算比率 a/b 的连分数。当分母大于N或近似值足够好时，您可以停止。

// Initialize:
double ratio = a / b;
int ak = (int)(ratio);
double remainder = ratio - ak;

int n0 = 1;
int d0 = 0;

int n1 = ak;
int d1 = 1;

do {
    ratio = 1 / remainder;
    ak = (int)ratio;
    int n2 = ak * n1 + n0;
    int d2 = ak * d1 + d0;
    n0 = n1;
    d0 = d1;
    n1 = n2;
    d1 = d2;
    remainder = ratio - ak;
} while (d1 < N);

n您正在寻找的值是d0（或者d1如果它仍然小于N）。

这不一定给你最小的解决方案，但它可能是一个非常好的近似值。

于 2012-01-25T23:47:08.127 回答
1

听起来您可能正在寻找诸如连分数之类的东西...

它们有什么关系？假设你可以用有理数 b1/b2 代替 b。现在您正在寻找整数 n 和 m，使得 an-b1/b2 大约为 m。换句话说，你正在寻找 n 和 m 使得 (m+(b1/b2))/n = (mb2+b1)/nb1，一个有理数，大约是 a。设置 a1 = mb2+b1 和 a2 = nb1。从连分式逼近中找到 a1 和 a2 的值并求解 n 和 m。

另一种方法可能是这样的：

  1. 为 a 和 b 找到一个好的有理近似值：a ~ a1/a2 和 b ~ b1/b2。
  2. 对 n 和 m 求解 n(a1/a2)-(b1/b2) = m。

我不太确定它会起作用。a 所需的精度取决于 n 和 b。

于 2012-01-25T23:07:51.170 回答
0

首先，让我们考虑一个更简单的情况，其中 b=0 且 0 < a < 1。F(a,n) = |an-round(an)|

让 step_size = 1

Step 1. Let v=a
Step 2. Let period size p = upper_round( 1/v ).
Step 3. Now, for n=1..p, there must be a number i such that F(v,i) < v.
Step 4. v = F(v,i), step_size = stepsize * i
Step 5. Go to step 2

如您所见，您可以将 F(v, *) 降低到您想要的任何级别。最终解决方案 n = step_size。

于 2012-01-25T23:10:21.890 回答