Изменение базы для дробных чисел в O (N) времени

Ответ 1

Отказ от ответственности: Я думаю, что он заканчивается в O (N) времени. Я добавил к универсальности алгоритма. Более того, Отрицательные радики IMPRACTICAL

Следующий метод преобразует число в десятичной базе в значение, указанное в 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 в десятичный - возвращает a 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);
}

И метод copy:

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 может привести к нескольким осложнения. Для начала интегральная часть float введенный трудно справиться. Этот метод в порядке для дробной части, потому что мы знаем, где предполагается цикл для остановки.

• Использование String исключает необходимость копирования.

• Но ваш метод имеет верх: верхний предел для radix - это Integer.MAX_VALUE, тогда как подход String составляет всего 36 (от 0 до 9 и от a до z) (хотя это не является довольно серьезным преимуществом, поскольку оно не имеет практического применения).

• Самый практичный подход к изменению базы чисел - сначала преобразовать в десятичной и затем преобразовать ее в другую базу.

• Использование double было бы лучше, чем использование float, поскольку оно повышает точность.

Ответ 2

Это решение работает. Он работает в O (NP) времени и не имеет переполнений (поскольку перенос имеет максимум B-1 = 2 ^ 31 - 1 - 1). Пожалуйста, дайте мне знать, сможете ли вы его сломать; см. ниже для тестовых случаев.

public class BaseTranslator {

    public static int[] convertBase(int[] f, int A, int B, int P)
    {
        if(A < 2) return null;
        if(B < 2) return null;
        if(P < 1) return null;
        if (f==null) return null;

        int[] converted = new int[P];
        int N = f.length;

        for (int i=0; i<N; i++) if (f[i]<0 || f[i]>=A) return null;

        int[] copy = new int[N];

        for (int i=0;i<N;i++) {copy[i]=f[i];}

        int i = 0;

        for (i=0; i<P;i++) {
            int carry=0;

            for(int idx=N-1; idx>=0; idx--) {

                int x = copy[idx]*B + carry;
                int next = x % A;
                carry = x / A;

                copy[idx] = next;
            }

            converted[i]=carry;
        }


        return converted;  
    }
}

Следующие @Тесты прошли:

import static org.junit.Assert.*;

import org.junit.Test;
public class BaseTranslatorTest {
    @Test
    public void basicBaseTranslatorTest() {
        // Expect that .01 in base-2 is .25 in base-10
        // (0 * 1/2^1 + 1 * 1/2^2 = .25)

        // corners

        /*  
         * If digits[i] < 0 or digits[i] >= baseA for any i, return null
         * If baseA < 2, baseB < 2, or precisionB < 1, return null 
         */

        int[] input = {1};

        assertArrayEquals(new int[]{1}, BaseTranslator.convertBase(input, 2, 2, 1));

        // bad base and/or precision

        assertArrayEquals(null, BaseTranslator.convertBase(input, 2, 2, 0));
        assertArrayEquals(null, BaseTranslator.convertBase(input, 2, 1, 1));
        assertArrayEquals(null, BaseTranslator.convertBase(input, 2, 1, 0));
        assertArrayEquals(null, BaseTranslator.convertBase(input, 1, 2, 1));
        assertArrayEquals(null, BaseTranslator.convertBase(input, 1, 2, 0));
        assertArrayEquals(null, BaseTranslator.convertBase(input, 1, 1, 1));
        assertArrayEquals(null, BaseTranslator.convertBase(input, 1, 1, 0));

        // bad input

        assertArrayEquals(null, BaseTranslator.convertBase(new int[]{9,3,5,-2}, 10, 10, 1)); 
        assertArrayEquals(null, BaseTranslator.convertBase(new int[]{9,3,5, 2}, 9, 9, 1));         

        // null input

        assertArrayEquals(null, BaseTranslator.convertBase(null, 1000000007, 1000000007, 1));  

        input = new int[]{0, 1};
        int[] expectedOutput = {2, 5};
        assertArrayEquals(expectedOutput, BaseTranslator.convertBase(input, 2, 10, 2));

        assertArrayEquals(new int[]{0,1}, BaseTranslator.convertBase(new int[]{0,1}, 2, 2, 2));
        assertArrayEquals(new int[]{0,1,0,0,0}, BaseTranslator.convertBase(new int[]{0,1}, 2, 2, 5));
        assertArrayEquals(new int[]{0}, BaseTranslator.convertBase(new int[]{0,1}, 2, 2, 1));
        assertArrayEquals(new int[]{2,5}, BaseTranslator.convertBase(new int[]{0,1}, 2, 10, 2));
        assertArrayEquals(new int[]{2,5,0,0,0}, BaseTranslator.convertBase(new int[]{0,1}, 2, 10, 5));
        assertArrayEquals(new int[]{2}, BaseTranslator.convertBase(new int[]{0,1}, 2, 10, 1));
        assertArrayEquals(new int[]{0,1}, BaseTranslator.convertBase(new int[]{2,5}, 10, 2, 2));
        assertArrayEquals(new int[]{0,1,0,0,0}, BaseTranslator.convertBase(new int[]{2,5}, 10, 2, 5));
        assertArrayEquals(new int[]{0}, BaseTranslator.convertBase(new int[]{2,5}, 10, 2, 1));

        assertArrayEquals(new int[]{0,0,0,0,0}, BaseTranslator.convertBase(new int[]{0}, 1000000007, 314159, 5));

        assertArrayEquals(new int[]{1,1}, BaseTranslator.convertBase(new int[]{3,1,2,5}, 10, 4, 2));


        assertArrayEquals(new int[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
                BaseTranslator.convertBase(new int[]{0,0,0,0,3,0,5,1,7,5,7,8,1,2,5}, 10, 2, 15));



        assertArrayEquals(new int[]{4,8,1,4,8,1,4,8,1,4,8,1,4,8,1,4,8}, 
                          BaseTranslator.convertBase(new int[]{1,1,1}, 3, 10, 17));

        assertArrayEquals(new int[]{12}, 
                          BaseTranslator.convertBase(new int[]{12}, 16, 16, 1));        

    }

}