java – 在O(N)时间内改变小数部分的基数

前端之家收集整理的这篇文章主要介绍了java – 在O(N)时间内改变小数部分的基数前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我道歉.这个问题是编程任务的一部分.我们被要求实施
一个将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,7};

转换为小数分数的二进制分数为0.25,转换函数的测试如下所示:

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

@Test
    assertArrayEquals(to,baseChanger(from,2,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.
 */

所以用“从”和“到”如上所述,这意味着要做以下事情:

>创建一个可以保存P数位的数组:

int [] output = new int [P]; // output = {0,0}
>取最右边的数字“from”:

{0,1 <==}
>将该数字乘以B(在此处为10)并添加进位(零,当前),并分配给x:

x <1×10 0 = 10
>用x mod A替换最右边的数字(当前为1)(2)

{0,0 <==}
>计算进位,这是x / A:

携带< -10 / 2 = 5
>将进位分配到输出中的第0个插槽:

输出[0]< - 携带 输出:{5 <==,0}
此过程重复一次,现在输出

output: {2,5}

但请注意,数字的顺序不正确,从最不重要到最重要!

另外,(更重要的是),从小数如0.3到二进制的转换将会怎么做?假设你想要的是12位精度.当然,没有确切的二进制表示,所以你在这里做什么,特别是因为最低有效数字首先出现?

from = {3}

我不知道从哪里开始,并会欣赏一些建议.请记住,这些数字是分数,而不是整数,算法必须在线性时间内完成.

解决方法

免责声明:我认为在O(N)时间结束.我已经加入了算法的多功能性.此外,负基数是IMPRACTICAL

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

/**
 * 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;
}

将基数中的数字转换为十进制的方法返回一个浮点数.

/**
 * 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 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;
}

我已经获得了所需的泛化水平.结果:

>实际(正确)输出

>上面写的代码输出

所以,我想这样解决了!顺便说一句,这里有一些提示

>使用数组而不是String可以导致几个并发症.对于初学者来说,浮动的组成部分进入难处理.这个方法没关系因为我们知道循环应该在哪里停止.>使用字符串排除了复制的需要.>但是你的方法有一个上限:基数的上限是Integer.MAX_VALUE,而String方法只有36(0到9和a toz)(尽管这不是一个很大的优点,因为它没有实际应用).>更改数字基础的最实际的方法是首先转换为十进制,然后将其转换为另一个基数.>使用double将比使用float更好,因为它提高了准确性.

原文链接:https://www.f2er.com/java/124716.html

猜你在找的Java相关文章