読者です 読者をやめる 読者になる 読者になる

やるしかなっちゃん

やるしかない!

逆数を求めるプログラム

Java アルゴリズム

逆数と言っても小数で表した形のやつ
以下のように出力したいとする(#は循環小数を表すための記号)

1 / 8 = 0.125
1 / 7 = 0.#142857
1 / 23 = 0.#0434782608695652173913
1 / 28 = 0.03#571428
1 / 29 = 0.#0344827586206896551724137931
1 / 34 = 0.0#2941176470588235
1 / 36 = 0.02#7

まずは普段の筆算で求めるのをコードにしてみる

public static void invertNumber(int n) {
    int[] q = new int[100]; // 商
    int[] r = new int[100]; // 余り
    q[0] = 0; // 1の位は必ず0
    r[0] = 1; // 最初の余りは1(分子)

    int i = 0, j;
    while(true) {
        i++; j = 0;
        q[i] = (r[i - 1] * 10) / n;
        r[i] = (r[i - 1] * 10) % n;

        // 余りの中に一つでも同じ値が存在すれば循環小数になる
        // 同じ値が存在する位置でループ終了
        while (j < i && r[i] != r[j]) {
            j++;
        }
        if (r[i] == 0 || i != j) {
            break;
        }
    }

    System.out.print("1 / " + n + " = " + q[0] + ".");
    for (int k = 1; k <= j; k++) {
        System.out.print(q[k]);
    }
    if (r[i] != 0) {
        System.out.print("#");
    }
    for (int k = j + 1; k <= i; k++) {
        System.out.print(q[k]);
    }
    System.out.println();
}

もう一目瞭然だけど計算量はO(N^2)

ここで、余りが0からn-1までの値をとるのでc[n-1]分の配列を用意して、i回目の繰り返しで余りrが求められた時c[r] = iとする処理を行っておけば、循環部分のループは配列cをチェックするだけで済むようになる

また、c[r]に対して値iが既に代入されているか確認するときに初期値0との比較を行うと、0番目の余りである1を表せないので配列は0以外で初期化することがポイント(ここに気が付かなくて果てしなく時間を無駄にした)
それを踏まえて改善版のコードは以下のようになる

public static void invertNumber(int n) {
    int[] q = new int[100]; // 商
    int[] c = new int[n];  // 循環チェック用, 余りは0以上n未満の整数
    q[0] = 0; // 1の位は必ず0
    Arrays.fill(c, -1); 

    int i = 0, r = 1; // 最初の余りは必ず1
    c[1] = i;
    while(true) {
        i++;
        q[i] = r * 10 / n;
        r = r * 10 % n;

        if (r == 0) {
            c[r] = i;
            break;
        }

        if (c[r] == -1) {
            c[r] = i;
        } else {
            break;
        }
    }

    // 循環部分は小数第j位から第i位
    int j = c[r];
    System.out.print("1 / " + n + " = " + q[0] + ".");
    for (int k = 1; k <= j; k++) {
        System.out.print(q[k]);
    }
    if (r != 0) {
        System.out.print("#");
    }
    for (int k = j + 1; k <= i; k++) {
        System.out.print(q[k]);
    }
    System.out.println();
}

ループを1つ減らせたので計算量はO(N)