0

数値の小数部の桁を表す整数の配列をある基数から別の基数に変換するアルゴリズムを実装しようとしています。言い換えると：

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

提案されたアルゴリズムがあり、次のように表現されています。

(i < 精度 B) の場合:

  1. キャリーを保持し、0 に初期化します。
  2. 右から左へ

    を。x = i 桁目を baseB で乗算し、キャリー
    b を加算します。新しい i 桁は x % baseA
    c. キャリー = x / baseA

  3. 出力[i] =キャリー

しかし、これを実装すると、3 桁を超える配列の場合、2 桁目が常に少しずれます。上記の例では、 が返されます{1, 3, 6, 2, 5}。基数 2の入力は基数 10 で {0, 1}正しく返されます。{2, 5}

私は 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 の 6.005コース、問題セット 1 からのものです。

4

1 に答える 1

0

私は最終的にそれを理解しました。解決策は、出力の各桁に対して入力配列のすべての桁をループする必要があることです。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;
}
于 2012-09-23T13:34:34.720 に答える