小数位数组的基地转换

Question

我想实现一个算法来将一个整数数组，代表一个数字的小数部分的数字，从一个基地到另一个。换句话说：

int[] input = {0, 0, 1, 0, 1}; // 0.00101 in base 2 
int[] output = convertBase(input, 2, 10, 5); // convertBase(input, fromBase, toBase, precision) 
output == {1, 5, 6, 2, 5}; // .15625 in base 10 

有一个建议的算法，其被表述为这样：

为（ⅰ< precisionB）：

1. 保持进位，初始化为0.
2. 从右到左

   a。 x =将第i个数字乘以baseB，并加上进位
   b。新的ith数字是x％baseA
   c。携带= X/baseA

3. 输出[I] =携带

但是，当我实现这一点，第二位数字始终是关闭由位为长度超过3个数字阵列。对于上面的例子，它将返回{1, 3, 6, 2, 5}。输入{0, 1}在基地2将正确地返回{2, 5}在基地10.

我不认为我正确理解2b。看起来你已经完成了输入数组中的第i位数字，替换它应该没有关系？

这里是我的代码：

public static int[] convertBase(int[] digits, int baseA, 
           int baseB, int precisionB) { 
    if (baseA < 2 | baseB < 2 | precisionB < 1) { 
     return null; 
    } 
    int[] input = digits.clone(); 
    int[] output = new int[precisionB]; 
    int carry = 0; 
    int j; 
    int x; 

    for (int i = 1; i <= precisionB; i++) { 
     j = precisionB - i; 
     if (input[j] >= baseA | input[j] < 0) { 
      return null; 
     } 
     x = (input[j] * baseB) + carry; 
     input[j] = x % baseA; 
     carry = x/baseA; 
     output[j] = carry; 
    } 

    return output; 
} 

这是MIT's 6.005当然，问题设置1

Answer 1

我终于想通了。解决方法是，您必须遍历输入数组的每个数字的所有数字。以下是Java中的代码：

public static int[] convertBase(int[] digits, int baseA, 
           int baseB, int precisionB) { 
    if (baseA < 2 | baseB < 2 | precisionB < 1) { 
     return null; 
    } 
    int[] input = digits.clone(); 
    int[] output = new int[precisionB]; 
    int carry; 
    int j; 
    int x; 

    for (int i = 1; i <= precisionB; i++) { 
     carry = 0; 
     for (int k = 0; k < input.length; k++) { 
      j = input.length - 1 - k; 
      if (input[j] >= baseA | input[j] < 0) { 
       return null; 
      } 
      x = (input[j] * baseB) + carry; 
      input[j] = x % baseA; 
      carry = x/baseA; 
     } 
     output[i-1] = carry; 
    } 
    return output; 
}