构建分数面试挑战

Question

我最近遇到了以下面试问题,我想知道动态编程方法是否有效,或者/和是否有某种数学洞察力可以使解决方案更容易......它与构建ieee754双倍的方式非常相似.

问题: 有N个双值的向量V. 其中向量的第i个索引处的值等于1/2 ^(i + 1).例如:1/2,1/4,1/8,1/16等......

你要编写一个函数,它将一个双'r'作为输入,其中0 <r <1,并将V的索引输出到stdout,当求和时,它将给出一个最接近值'r'的值,而不是任何其他组合来自矢量V的索引

此外,索引的数量应该是最小的,并且在有两个解决方案的情况下,应该优选最接近零的解.

void getIndexes(std::vector<double>& V, double r)
{
 .... 
}

int main()
{
   std::vector<double> V;
   // populate V...
   double r = 0.3;
   getIndexes(V,r);
   return 0;
}

注意:似乎有一些SO'er没有完全阅读这个问题的心情.所以请大家注意以下几点:

1. 解决方案,也就是总和可能大于r - 因此任何策略从r逐步减去分数,直到它达到零或接近零是错误的

2. 有r的例子,其中有2个解,即| r-s0 | == | r-s1 | 并且s0 <s1 - 在这种情况下应该选择s0,这使问题稍微困难一些,因为背包式解决方案往往首先贪婪高估.

3. 如果您认为这个问题很简单,那么您很可能还没有理解它.因此,再次阅读这个问题是个好主意.

编辑(Matthieu M.): 2个例子V = {1/2, 1/4, 1/8, 1/16, 1/32}

• r = 0.3, S = {1, 3}
• r = 0.256652, S = {1}

Answer 1

算法

考虑目标数量r和一组F分数{1/2, 1/4, ... 1/(2^N)}.让最小的部分1/(2^N)表示P.

那么最优总和将等于:

S = P * round(r/P)

也就是说,最佳总和S将是可用的最小分数的某个整数倍P.最大错误err = r - S是± 1/2 * 1/(2^N).没有更好的解决方案是可能的,因为这需要使用小于的数字1/(2^N),这是集合中的最小数字F.

由于分数F都是2的幂倍数P = 1/(2^N),因此任何整数倍P可以表示为分数的总和F.要获得应该使用的分数列表,请round(r/P)以二进制编码整数,并1在kth二进制位置读取"包括kth解决方案中的分数".

例:

拿走r = 0.3和F作为{1/2, 1/4, 1/8, 1/16, 1/32}.

1. 将整个问题乘以32.

   以r = 9.6和F为{16, 8, 4, 2, 1}.

2. 舍r入到最接近的整数.

   拿r = 10.

3. 编码10为二进制整数(五位)

   10 = 0b 0 1 0 1 0    ( 8 + 2 )
           ^ ^ ^ ^ ^
           | | | | |
           | | | | 1
           | | | 2
           | | 4
           | 8
           16
   

4. 将每个二进制位与分数相关联.

      = 0b 0 1 0 1 0    ( 1/4 + 1/16 = 0.3125 )
           ^ ^ ^ ^ ^
           | | | | |
           | | | | 1/32
           | | | 1/16
           | | 1/8
           | 1/4
           1/2
   

证明

考虑通过将所涉及的所有数字相乘来转换问题,2**N以便所有分数变为整数.

原来的问题:

考虑r范围内的目标数字0 < r < 1和分数列表{1/2, 1/4, .... 1/(2**N).查找总计为分数列表的子集S,以便error = r - S最小化.

成为以下等效问题(乘以后2**N):

考虑r范围内的目标编号0 < r < 2**N和整数 列表{2**(N-1), 2**(N-2), ... , 4, 2, 1}.查找总计为整数列表的子集S,以便error = r - S最小化.

选择总和为给定数字的2的幂(尽可能小的误差)只是整数的二进制编码.因此,该问题减少为整数的二进制编码.

• 的溶液存在:任何正的浮点数r,0 < r < 2**N,可以转换为一个整数,并以二进制形式表示.
• 最优性:解的整数版本中的最大误差是舍入误差±0.5.(在原始问题中,最大错误是±0.5 * 1/2**N.)
• 唯一性:对于任何正(浮点)数,都有唯一的整数表示,因此是唯一的二进制表示.(可能的例外0.5=见下文.)

实现(Python)

此函数将问题转换为整数等价,舍r入为整数,然后读取整数的二进制表示r以获得所需的分数.

def conv_frac (r,N):
    # Convert to equivalent integer problem.
    R = r * 2**N
    S = int(round(R))

    # Convert integer S to N-bit binary representation (i.e. a character string
    # of 1's and 0's.) Note use of [2:] to trim leading '0b' and zfill() to
    # zero-pad to required length.
    bin_S = bin(S)[2:].zfill(N)

    nums = list()
    for index, bit in enumerate(bin_S):
        k = index + 1
        if bit == '1':
            print "%i : 1/%i or %f" % (index, 2**k, 1.0/(2**k))
            nums.append(1.0/(2**k))
    S = sum(nums)
    e = r - S

    print """
    Original number        `r` : %f
    Number of fractions    `N` : %i (smallest fraction 1/%i)
    Sum of fractions       `S` : %f
    Error                  `e` : %f
    """ % (r,N,2**N,S,e)

样本输出:

>>> conv_frac(0.3141,10)
1 : 1/4 or 0.250000
3 : 1/16 or 0.062500
8 : 1/512 or 0.001953

    Original number        `r` : 0.314100
    Number of fractions    `N` : 10 (smallest fraction 1/1024)
    Sum of fractions       `S` : 0.314453
    Error                  `e` : -0.000353

>>> conv_frac(0.30,5)
1 : 1/4 or 0.250000
3 : 1/16 or 0.062500

    Original number        `r` : 0.300000
    Number of fractions    `N` : 5 (smallest fraction 1/32)
    Sum of fractions       `S` : 0.312500
    Error                  `e` : -0.012500

附录:0.5问题

如果r * 2**N结束0.5,则可以向上或向下舍入.也就是说,有两种可能的表示形式作为分数之和.

如果像原始问题陈述中那样,您希望使用最少分数的表示(即1二进制表示中的最小位数),只需尝试两种舍入选项并选择哪一种更经济.

Answer 2

也许我很笨......

我可以看到这里唯一的问题是,总和(1/2)^(i+1)为i在[0..n)那里n趋向于无穷大给出1.这个简单的事实证明,(1/2)^i总是优于sum (1/2)^j对j中[i+1, n),无论n是.

因此,在寻找我们的指数时,似乎我们没有太多选择.让我们开始吧i = 0

• 要么r是优越的2^-(i+1),所以我们需要它
• 或者是劣质,我们需要选择是否2^-(i+1)或sum 2^-j用于j在[i+2, N]最接近(推迟到后者在平等的情况下)

可能成本高昂的唯一步骤是获得总和,但它可以一次性预先计算(甚至可以预先计算).

// The resulting vector contains at index i the sum of 2^-j for j in [i+1, N]
// and is padded with one 0 to get the same length as `v`
static std::vector<double> partialSums(std::vector<double> const& v) {
    std::vector<double> result;

    // When summing doubles, we need to start with the smaller ones
    // because of the precision of representations...

    double sum = 0;
    BOOST_REVERSE_FOREACH(double d, v) {
        sum += d;
        result.push_back(sum);
    }

    result.pop_back(); // there is a +1 offset in the indexes of the result

    std::reverse(result.begin(), result.end());

    result.push_back(0); // pad the vector to have the same length as `v`

    return result;   
}

// The resulting vector contains the indexes elected
static std::vector<size_t> getIndexesImpl(std::vector<double> const& v,
                                          std::vector<double> const& ps,
                                          double r)
{
  std::vector<size_t> indexes;

  for (size_t i = 0, max = v.size(); i != max; ++i) {
      if (r >= v[i]) {
          r -= v[i];
          indexes.push_back(i);
          continue;
      }

      // We favor the closest to 0 in case of equality
      // which is the sum of the tail as per the theorem above.
      if (std::fabs(r - v[i]) < std::fabs(r - ps[i])) {
          indexes.push_back(i);
          return indexes;
      }
  }

  return indexes;
}

std::vector<size_t> getIndexes(std::vector<double>& v, double r) {
    std::vector<double> const ps = partialSums(v);
    return getIndexesImpl(v, ps, r);
}

代码在ideone上运行(带有一些调试输出).请注意,因为0.3它给出:

0.3:
   1: 0.25
   3: 0.0625
=> 0.3125

这与其他答案略有不同.

Answer 3

对向量进行排序并搜索与 r 可用的最接近的分数。存储该索引，从 r 中减去该值，然后对 r 的余数重复。迭代直到到达r，或者找不到这样的索引。

例子 ：

0.3 - 可用的最大值为 0.25。（索引2）。现在余数是0.05

0.05 - 可用的最大值为 0.03125 - 余数为 0.01875

ETC。

等等，每一步都是在排序数组中进行 O(logN) 搜索。步骤数也将是 O(logN) 总复杂度将是 O(logN^2)。