一个将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}
我不知道从哪里开始,并会欣赏一些建议.请记住,这些数字是分数,而不是整数,算法必须在线性时间内完成.
解决方法
以下方法将十进制数字中的数字转换为基数中提到的数字：
/** * 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更好,因为它提高了准确性.
