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

最近，我遇到了以下采访问题，我想知道动态编程方法是否行得通，或者/或者是否存在某种数学见解可以使解决方案变得更容易……它与ieee754 double的构造非常相似。

问题:
有N个 double 值的 vector V。其中 vector 的第i个索引处的值等于1/2 ^(i + 1)。例如:1/2、1/4、1/8、1/16等...

您要编写一个函数，该函数以一个双“r”作为输入，其中0
此外，索引的数量应最少，并且在有两个解决方案的情况下，应首选最接近零的解决方案。

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's不想完全阅读问题。因此，让所有人注意以下几点:

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

有r的示例，其中有2个解，即| r-s0 |。 == | r-s1 |且s0

如果您认为这个问题很简单，那么您很可能还不了解。因此，再次阅读该问题将是一个好主意。

编辑(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}

最佳答案

算法

考虑目标数字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中最小的数字。

由于分数P = 1/(2^N)都是P的2的整数倍，因此F的任何整数倍都可以表示为round(r/P)中的分数的总和。要获取应使用的分数列表，请以二进制形式对整数1进行编码，并在kth二进制位置中读取kth，作为“在解决方案中包括r分数”。

例子:

将整个问题乘以32。

将10舍入到最接近的整数。

将2**N编码为二进制整数(五个位)

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

将每个二进制位与一个小数相关联。

   = 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之后):



选择总和等于给定数(误差最小)的2的幂就是简单的整数二进制编码。因此，该问题简化为整数的二进制编码。

解决方案的存在:任何正浮点数0 < r < 2**N，±0.5都可以转换为整数并以二进制形式表示。

最佳性:整数解决方案中的最大误差是±0.5 * 1/2**N的舍入误差。 (在原始问题中，最大错误是0.5。)

唯一性:对于任何正数(浮点数)，都有一个唯一的整数表示形式，因此也有一个唯一的二进制表示形式。 (r的可能异常(exception)=参见下文。)

实现(Python)

此函数将问题转换为等效的整数，将r舍入为整数，然后读取0.5的二进制表示形式为整数以获取所需的分数。

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

附录:r * 2**N问题

如果0.5以1结尾，则可以四舍五入。即，存在两种可能的分数总和表示。

如果像在原始问题陈述中那样想要使用最少分数的表示形式(即二进制表示形式中的ojit_code位最少数量)，则只需尝试两个舍入选项，然后选择哪一种更经济。

关于c++ - 构建分数面试挑战，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10477945/