1

ウィキペディアの小数の繰り返しに関する情報を読んだ後、小数の繰り返し部分の桁数を見つける方法を見つけました。

例えば、

1/3 = 0.33333333333333333333333333333... したがって、結果は 1 桁です。

1/7 = 0.142857142857142857142857142857... したがって、結果は 6 桁になります。

ただし、(Java での) 私の方法は 1/6 では機能しませんでした。

1/6 = 0.1666... したがって、小数の非反復部分にもかかわらず、結果は 1 桁になります。

うまくいく解決策を見つけました（Nayuki Minaseの功績による）。

private static int getCycleLength(int n)
{
    Map<Integer,Integer> stateToIter = new HashMap<Integer,Integer>();
    int state = 1;
    int iter = 0;
    while (!stateToIter.containsKey(state))
    {
        stateToIter.put(state, iter);
        state = state * 10 % n;
        iter++;
    }
    System.out.println(iter + " - " + stateToIter.get(state));
    return iter - stateToIter.get(state);
}

このアルゴリズムがどのように機能するかを誰かに説明してもらえますか? ありがとうございました。

4

3 に答える 3

1

したがって、このアルゴリズムでは、この行が重要です。

while(!stateToIter.containsKey(state))

繰り返し状態が見つかった場合、プログラムが壊れています。繰り返し状態を見つけるということは、繰り返しサイクルを検出していることを意味します。問題を見てみましょう。たとえば、6 を求めなければならないとします。1/6 を行う方法は次のとおりです。

Problem :6 | 1 | Result = ?  
 Step 1: 
 Add 0. in the result and multiply 1 with 10
 6 | 10 | 0.

 Iteration 

 Step 2: 
 Do the division
 6 | 10 | 0.1
      6
    -----
      4 [Mod]

 Iteration = 0

 Step 3: 
 Multiply mod with 10 and carry on
 6 | 10 | 0.16
      6
    -----
      40 
      36
    -----
      04 [Mod]


 Iteration = 1

 Now we find a repeating mod so now matter how far we go we always get 4 as mod and our result will be 0.166666.. and so on so our repeating cycle will be 1 which is our iteration.
于 2013-06-07T05:36:18.803 に答える
0

10 進数に変換するときは、0 になる (書き込む必要がなくなる) かあきらめる (精度の限界に達する) まで、持っている値に徐々に 10 を掛けます。

もう一度作業している同じ値を取得したら、その時点から同じ数字を繰り返します。メソッドが行うことは、繰り返し値を取得したときに検出し、最初にそれを見てからの経過時間 (繰り返しサイクルの長さ) を計算することです。

ところで、マップの使用を回避するこの問題の別の解決策。繰り返しシーケンスは、1/9 または 1/99 または 1/999 または 1/9999 などの倍数でなければなりません。これが繰り返されるポイントです。

public static void main(String... args) throws IOException {
    for (int i = 3; i < 100; i++) {
        System.out.println("i: " + i + " f: " + 1.0 / i + " repeat: " + getRepeatingCount(i));
    }
}

public static final BigInteger TEN_TO_19 = BigInteger.TEN.pow(19);

public static int getRepeatingCount(int divisor) {
    if (divisor <= 0) throw new IllegalArgumentException();
    while (divisor % 2 == 0) divisor /= 2;
    while (divisor % 5 == 0) divisor /= 5;
    int count = 1;
    if (divisor == 1) return 0;
    for (long l = 10; l > 0; l *= 10) {
        long nines = l - 1;
        if (nines % divisor == 0)
            return count;
        count++;
    }
    for(BigInteger bi = TEN_TO_19; ; bi = bi.multiply(BigInteger.TEN)) {
        BigInteger nines = bi.subtract(BigInteger.ONE);
        if (nines.mod(BigInteger.valueOf(divisor)).equals(BigInteger.ZERO))
            return count;
        count++;
    }
}
于 2013-06-07T06:40:20.087 に答える