c++ - 构建分数面试挑战

Question

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

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

您将编写一个函数，该函数将一个双倍“r”作为输入，其中 0 < r < 1，并将 V 的索引输出到标准输出，当求和时将给出一个比任何其他组合最接近值“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'ers 没有完全阅读问题的心情。所以让大家注意以下几点：

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)读取为“在解决方案中包含分数”。1kthkth

例子：

取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}Serror = 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)for iin [0..n)where的总和n趋于无穷大1。这个简单的事实证明(1/2)^i总是优于sum (1/2)^jfor jin [i+1, n)，不管n是什么。

因此，在寻找我们的指数时，我们似乎没有太多选择。让我们从i = 0

• 要么r优于2^-(i+1)，因此我们需要它
• 或者它是次等的，我们需要选择2^-(i+1)OR sum 2^-jfor jin[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

冒着被否决的风险，这个问题似乎相当简单。只需从您可以产生的最大和最小数字开始，V依次调整每个索引，直到您有两个可能最接近的答案。然后评估哪个是更好的答案。

这是未经测试的代码（使用我不写的语言）：

void getIndexes(std::vector<double>& V, double r)
{
  double v_lower = 0;
  double v_upper = 1.0 - 0.5**V.size();
  std::vector<int> index_lower;
  std::vector<int> index_upper;

  if (v_upper <= r)
  {
    // The answer is trivial.
    for (int i = 0; i < V.size(); i++)
      cout << i;
    return;
  }

  for (int i = 0; i < N; i++)
  {
    if (v_lower + V[i] <= r)
    {
      v_lower += V[i];
      index_lower.push_back(i);
    }

    if (r <= v_upper - V[i])
      v_upper -= V[i];
    else
      index_upper.push_back(i);
  }

  if (r - v_lower < v_upper - r)
    printIndexes(index_lower);
  else if (v_upper - r < r - v_lower)
    printIndexes(index_upper);
  else if (v_upper.size() < v_lower.size())
    printIndexes(index_upper);
  else
    printIndexes(index_lower);
}

void printIndexes(std::vector<int>& ind)
{
  for (int i = 0; i < ind.size(); i++)
  {
    cout << ind[i];
  }
}

我得到这份工作了吗！:D

（请注意，这是一个可怕的代码，它依赖于我们确切地知道 V 中有什么......）

Answer 4

我首先要说我确实相信这个问题是微不足道的......

（等到所有的石头都被扔掉）

是的，我确实阅读了 OP 的编辑，该编辑说如果我这么认为我必须重新阅读这个问题。因此，我可能会遗漏一些我看不到的东西——在这种情况下，请原谅我的无知并随时指出我的错误。

我不认为这是一个动态编程问题。冒着听起来幼稚的风险，为什么不尝试r在搜索索引时保留两个估计值 - 即低估和高估。毕竟，如果r不等于可以从 的元素计算的任何总和，V它将位于该类型的两个总和之间。我们的目标是找到这些总和并报告哪个更接近r。

我拼凑了一些快速而肮脏的 Python 代码来完成这项工作。它报告的答案对于 OP 提供的两个测试用例是正确的。请注意，如果它return的结构使得必须始终返回至少一个索引 - 即使最佳估计根本没有索引。

def estimate(V, r):
  lb = 0               # under-estimation (lower-bound)
  lbList = []
  ub = 1 - 0.5**len(V) # over-estimation = sum of all elements of V
  ubList = range(len(V))

  # calculate closest under-estimation and over-estimation
  for i in range(len(V)):
    if r == lb + V[i]:
      return (lbList + [i], lb + V[i])
    elif r == ub:
      return (ubList, ub)
    elif r > lb + V[i]:
      lb += V[i]
      lbList += [i]
    elif lb + V[i] < ub:
      ub = lb + V[i]
      ubList = lbList + [i]
  return (ubList, ub) if ub - r < r - lb else (lbList, lb) if lb != 0 else ([len(V) - 1], V[len(V) - 1])

# populate V
N = 5 # number of elements
V = []
for i in range(1, N + 1):
  V += [0.5**i]

# test
r = 0.484375 # this value is equidistant from both under- and over-estimation
print "r:", r
estimate = estimate(V, r)
print "Indices:", estimate[0]
print "Estimate:", estimate[1]

注意：写完我的答案后，我注意到这个答案遵循相同的逻辑。唉!

Answer 5

不知道你有没有测试用例，试试下面的代码。这是一种动态规划方法。

1] exp: given 1/2^i, find the largest i as exp. Eg. 1/32 returns 5.
2] max: 10^exp where exp=i.
3] create an array of size max+1 to hold all possible sums of the elements of V.
   Actually the array holds the indexes, since that's what you want.
4] dynamically compute the sums (all invalids remain null)
5] the last while loop finds the nearest correct answer.

这是代码：

public class Subset {

public static List<Integer> subsetSum(double[] V, double r) {
    int exp = exponent(V);
    int max = (int) Math.pow(10, exp);
    //list to hold all possible sums of the elements in V
    List<Integer> indexes[] = new ArrayList[max + 1];
    indexes[0] = new ArrayList();//base case
    //dynamically compute the sums
    for (int x=0; x<V.length; x++) {
        int u = (int) (max*V[x]);
        for(int i=max; i>=u; i--) if(null != indexes[i-u]) {
            List<Integer> tmp = new ArrayList<Integer>(indexes[i - u]);
            tmp.add(x);
            indexes[i] = tmp;
        }
    }
   //find the best answer
    int i = (int)(max*r);
    int j=i;
    while(null == indexes[i] && null == indexes[j]) {
        i--;j++;
    }
      return indexes[i]==null || indexes[i].isEmpty()?indexes[j]:indexes[i];
}// subsetSum

private static int exponent(double[] V) {
    double d = V[V.length-1];
    int i = (int) (1/d);
    String s = Integer.toString(i,2);
    return s.length()-1;
}// summation

public static void main(String[] args) {
    double[] V = {1/2.,1/4.,1/8.,1/16.,1/32.};
    double r = 0.6, s=0.3,t=0.256652;
    System.out.println(subsetSum(V,r));//[0, 3, 4]
    System.out.println(subsetSum(V,s));//[1, 3]
    System.out.println(subsetSum(V,t));//[1]
}
}// class

下面是运行代码的结果：

For 0.600000  get 0.593750 => [0, 3, 4]
For 0.300000  get 0.312500 => [1, 3]
For 0.256652  get 0.250000 => [1]
For 0.700000  get 0.687500 => [0, 2, 3]
For 0.710000  get 0.718750 => [0, 2, 3, 4]

Answer 6

该解决方案实现多项式时间近似算法。该程序的输出与另一个解决方案的输出相同。

#include <math.h>                                                                                                                                             
#include <stdio.h>                                                                                                                                            
#include <vector>                                                                                                                                             
#include <algorithm>                                                                                                                                          
#include <functional>                                                                                                                                         

void populate(std::vector<double> &vec, int count)                                                                                                            
{                                                                                                                                                             
    double val = .5;                                                                                                                                          
    vec.clear();                                                                                                                                              
    for (int i = 0; i < count; i++) {                                                                                                                         
        vec.push_back(val);                                                                                                                                   
        val *= .5;                                                                                                                                            
    }                                                                                                                                                         
}                                                                                                                                                             

void remove_values_with_large_error(const std::vector<double> &vec, std::vector<double> &res, double r, double max_error)                                     
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    double min_err, err;                                                                                                                                      

    min_err = 1.0;                                                                                                                                            
    for (iter = vec.begin(); iter != vec.end(); ++iter) {                                                                                                     
        err = fabs(*iter - r);                                                                                                                                
        if (err < max_error) {                                                                                                                                
            res.push_back(*iter);                                                                                                                             
        }                                                                                                                                                     
        min_err = std::min(err, min_err);                                                                                                                     
    }                                                                                                                                                         
}

void find_partial_sums(const std::vector<double> &vec, std::vector<double> &res, double r)                                                                    
{                                                                                                                                                             
    std::vector<double> svec, tvec, uvec;                                                                                                                     
    std::vector<double>::const_iterator iter;                                                                                                                 
    int step = 0;                                                                                                                                             

    svec.push_back(0.);                                                                                                                                       
    for (iter = vec.begin(); iter != vec.end(); ++iter) {                                                                                                     
        step++;                                                                                                                                               
        printf("step %d, svec.size() %d\n", step, svec.size());                                                                                               
        tvec.clear();                                                                                                                                         
        std::transform(svec.begin(), svec.end(), back_inserter(tvec),                                                                                         
                       std::bind2nd(std::plus<double>(), *iter));                                                                                             
        uvec.clear();                                                                                                                                         
        uvec.insert(uvec.end(), svec.begin(), svec.end());                                                                                                    
        uvec.insert(uvec.end(), tvec.begin(), tvec.end());                                                                                                    
        sort(uvec.begin(), uvec.end());                                                                                                                       
        uvec.erase(unique(uvec.begin(), uvec.end()), uvec.end());                                                                                             

        svec.clear();                                                                                                                                         
        remove_values_with_large_error(uvec, svec, r, *iter * 4);                                                                                             
    }                                                                                                                                                         

    sort(svec.begin(), svec.end());                                                                                                                           
    svec.erase(unique(svec.begin(), svec.end()), svec.end());                                                                                                 

    res.clear();                                                                                                                                              
    res.insert(res.end(), svec.begin(), svec.end());                                                                                                          
} 

double find_closest_value(const std::vector<double> &sums, double r)                                                                                          
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    double min_err, res, err;                                                                                                                                 

    min_err = fabs(sums.front() - r);                                                                                                                         
    res = sums.front();                                                                                                                                       

    for (iter = sums.begin(); iter != sums.end(); ++iter) {                                                                                                   
        err = fabs(*iter - r);                                                                                                                                
        if (err < min_err) {                                                                                                                                  
            min_err = err;                                                                                                                                    
            res = *iter;                                                                                                                                      
        }                                                                                                                                                     
    }                                                                                                                                                         
    printf("found value %lf with err %lf\n", res, min_err);                                                                                                   
    return res;                                                                                                                                               
}                                                                                                                                                             

void print_indexes(const std::vector<double> &vec, double value)                                                                                              
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    int index = 0;                                                                                                                                            

    printf("indexes: [");                                                                                                                                     
    for (iter = vec.begin(); iter != vec.end(); ++iter, ++index) {                                                                                            
        if (value >= *iter) {                                                                                                                                  
            printf("%d, ", index);                                                                                                                            
            value -= *iter;                                                                                                                                   
        }                                                                                                                                                     
    }                                                                                                                                                         
    printf("]\n");                                                                                                                                            
}                                                                                                                                                             

int main(int argc, char **argv)                                                                                                                               
{                                                                                                                                                             
    std::vector<double> vec, sums;                                                                                                                            
    double r = .7;                                                                                                                                            
    int n = 5;                                                                                                                                                
    double value;                                                                                                                                             
    populate(vec, n);                                                                                                                                         
    find_partial_sums(vec, sums, r);                                                                                                                          
    value = find_closest_value(sums, r);                                                                                                                      
    print_indexes(vec, value);                                                                                                                                
    return 0;                                                                                                                                                 
}

Answer 7

这不是动态规划问题

输出应该是整数（索引）向量，而不是双精度向量

这可能是 0-2 的精确值，这只是概念：

A) 输出零索引，直到 r0（r - 已输出的索引值）大于 1/2

B) 检查 r0 double 的内部表示并且：

x (第一个位移) = -指数; // 指数越大，数字越小（开始时 1/2^(x) 中的 x 越大）

使用主体检查循环中浮点小数部分的位表示：（方向取决于小/大端）

{
  if (bit is 1)
    output index x;
  x++;

}

每个步骤的复杂性是恒定的，因此总体而言它是 O(n)，其中 n 是输出的大小。

Answer 8

解释这个问题，r 的二进制表示中的一位（在二进制点之后）是什么？如果您愿意，N 是“精度”。

在 Cish 伪代码中

for (int i=0; i<N; i++) {
  if (r>V[i]) {
    print(i);
    r -= V[i];
  }
}

您可以为 r == 0 添加额外的测试以提前终止循环。

请注意，这给出了最接近“r”的最小二进制数，即如果有两个同样“正确”的答案，则该二进制数更接近于零。

如果第 N 个数字是 1，您需要将“1”添加到获得的“二进制”数字中，并与原始“r”进行核对。（提示：构造向量 a[N], b[N] of 'bits'，设置 '1' 位而不是上面的 'print'。设置 b = a 并手动添加，从 ' 末尾逐位b' 直到你停止携带。转换为双倍并选择更接近的那个。

请注意，a[] <= r <= a[] + 1/2^N 并且 b[] = a[] + 1/2^N。

'最少数量的索引 [原文如此]' 是一个红鲱鱼。

Answer 9

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

例子 ：

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

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

等等

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