java - 在 O(N) 时间内更改小数的基数

Question

我道歉。这个问题是编程作业的一部分。我们被要求实现 一种以 P 位精度将 分数 f 从基数 A 更改为基数 B 的方法。 函数有签名

baseChanger(int[] f, int A, int B, int P)。

例如，小数 3.14159 的小数为 0.14159，表示为数组:

int[] frac = {1,4,1,5,9};

16 进制的分数 -- 0.3BA07 -- 会被写成

int[] frac = {3,11,10,0,7};

二进制小数 0.01 转换为十进制小数是 0.25，测试转换函数如下所示:

int[] from = {0,1};
int[] to = {2,5};

@Test
    assertArrayEquals(to, baseChanger(from, 2, 10, 2));

这是我们被要求实现的算法:

/*      
 * for (i < P) {
 *   1. Keep a carry, initialize to 0.
 *   2. From right to left:
 *      a. x = multiply the ith digit by B and add the carry
 *      b. the new ith digit is x % A
 *      c. carry = x / A
 *   3. output[i] = carry 
 * 
 * @param f The input array to translate. This array is not mutated.
 * @param A The base that the input array is expressed in.
 * @param B The base to translate into.
 * @param P The number of digits of precision the output should
 *                   have.
 * @return An array of size P expressing digits in B.
 */

所以对于上面的“from”和“to”，这意味着执行以下操作:

1. 创建一个可以容纳 P 个数字的数组:

   int[] output = new int[P];//输出 = {0, 0}

2. 取“from”最右边的数字:

   {0, 1 <== }

3. 将该数字乘以 B(此处为 10)并加上进位(当前为零)，然后分配给 x:

   x <-- 1 x 10 + 0 = 10

4. 将最右边的数字(当前为 1)替换为 x mod A(此处为 2):

   {0, 0 <== }

5. 计算进位，即 x/A:

   携带 <-- 10/2 = 5

6. 将进位分配给输出中的第 0 个槽:

   输出[0] <--进位

   输出:{5 <==, 0}

这个过程再重复一次，现在输出

output: {2,5}

但是请注意，数字的顺序是错误的，并且是从least significant 到most significant 输出的!

此外，(更重要的是)将小数(如 0.3)转换为二进制会怎样做？假设您想要 12 位精度。当然，没有精确的二进制表示法，所以您会在这里做什么，特别是因为最低有效数字先出现？

from = {3}

我不确定从哪里开始，希望得到一些建议。请记住，这些数字是分数，而不是整数，并且算法必须在线性 时间内完成。

Answer 1

免责声明:我认为它在O(N) 时间内完成。我已经增加了算法的多功能性。此外，负基数是不切实际的

以下方法将十进制数转换为 radix 中提到的数:

/**
 * This method returns an array with <code>precs</code> elements conating the
 * required fractional part in the base <code>radix</code>
 *
 * @param frac A <code>float</code> that contains the fractional part 
 * (and fractional part only!!) in decimal number system.
 * @param radix The base to which it has to be converted (must be (+) ve).
 * @param precs The number of digits required i.e. precision.
 * 
 * @return A <code>int[]</code> that contains the digits(eqivalent).
 */
public static int[] toRadix(float frac, int radix, int precs)
{
    if(radix < 2) return null;
    //Only fractional part is accepted here.
    frac = frac - (long)frac;  //Precautionary measure :-)
    int i, j;
    int[] res = new int[precs]; //For storing result.
    for(i = 0; i < precs && frac != 0; i++)
    {
        frac *= radix;
        res[i] = (int)frac;
        if((long)frac >= 1)
            frac = frac - (long)frac;
    }
    if(flag)
        return copy(res, i);
    return res;
}

将基数 radix 中的数字转换为十进制的方法 -- 返回 float。

/**
 * This method returns a <code>float</code> that contains the equivalent of the
 * fraction in the other base in the parameter array, in decimal.
 * 
 * @param frac An <code>int[]</code> conatining only the fractional part.
 * @param radix The base of the fraction entered (must be (+) ve).
 * 
 * @return The equivalent decimal fraction as a <code>float</code>.
 */
public static float toDecimal(int[] frac, int radix)
{
    if(radix < 2) return null;
    float res = 0, fac = 1.0f/radix;
    int i, p = frac.length;
    for(i = 0; i < p; i++)
    {
        res += frac[i] * fac;        //or (float)Math.pow(radix, -i);
        fac/=radix;                  //would be fine as well.
    }
    return res;
}

终于! `baseChanger()` 方法

public static int[] baseChanger(int[] f, int A, int B, int P)
{
    if(A < 2) return null;
    if(B < 2) return null;
    return toRadix(toDecimal(f, A), B, P);
}

和复制方法:

private static int[] copy(int[] a, int index)
{
    index = index < a.length ? index : a.length;
    int b[] = new int[index];
    for(int i = 0; i < index; i++)
        b[i] = a[i];
    return b;
}

---

我已获得所需的泛化水平。结果:

1. 实际(正确)输出:

   

2. 以上编写代码的输出:

   

所以，我想这就解决了!顺便说一句，这里有一些提示:

1. 使用数组而不是 String 会导致几个 并发症。对于初学者来说，float 的组成部分 进去很难对付。这个方法ok 对于小数部分，因为我们知道循环应该在哪里 停止。

2. 使用 String 排除了复制的需要。

3. 但是您的方法有一个优势:radix 的上限是
   Integer.MAX_VALUE 而 String 方法只有 36(0 到 9 和一个到 z)(虽然这不是一个非常重要的优势，因为它没有实际应用)。

4. 更改数字基数的最实用方法是首先转换为 十进制和然后，将其转换为其他基数。

5. 使用 double 会比使用 float 更好，因为它可以提高准确性。