2

数値 n を指定して、10 進数表現に 3 桁を含まない 1 から n までの数値のカウントを返す関数を作成します。

この問題を解決する最も最適な方法は何ですか。

私がナイーブで使用しているアプローチ、つまりnlogn（複雑さを見てアプローチを推測するのは簡単です:)）

4

1 に答える 1

4

次のアルゴリズムは、0 から (n-1) までの整数の数を、10 進数表現の「3」を除いて非常に効率的に計算します。(間隔を 1 .. n から 0 .. n-1 に変更したのは、次の計算を少し単純化するためだけです。)

(私は複雑さの計算の専門家ではありませんが、このアルゴリズムの複雑さは だと思います。これはO(log n)、 の各桁に対して固定数のステップを実行するためですn。)

最初の観測は、最大 d 桁の整数 (つまり、間隔 0 .. 10 d -1 の数値) で、10 進数表現に数字 3 がない整数の数は、正確に 9 dであるということです。可能な選択肢 0、1、2、4、5、6、7、8、9。

ここで、5 桁の数値 n = a 4 a 3 a 2 a 1 a 0を使用してアルゴリズムのデモを行います。

間隔の 10 進数表現に「3」を含まない整数の数を個別に計算します

  • I 0 : a 4 a 3 a 2 a 1 0 <= i < a 4 a 3 a 2 a 1 a 0
  • 私1 : a 4 a 3 a 2 0 0 <= i < a 4 a 3 a 2 a 1 0
  • 私2 : a 4 a 3 0 0 0 <= i < a 4 a 3 a 2 0 0
  • 私3 : a 4 0 0 0 0 <= i < a 4 a 3 0 0 0
  • 私4 : 0 0 0 0 0 <= 私 < a 4 0 0 0 0

10 進数表現で「3」を持たない区間 I jの整数の数は次のとおりです。

  • より高い値の数字 a j+1、 a j+2、...のいずれかが 3 に等しい場合は 0、それ以外の場合:
  • a j * 9 j、0 <= a j <= 3 の場合 ( j番目の桁の a jの選択肢、下位のすべての数字の 9 つの選択肢)、
  • (a j - 1) * 9 j 、 aj > 3 の場合 (3 は j番目の数字として有効な選択肢ではないため) .

したがって、次の関数があります。

/*
 * Compute number of integers x with 0 <= x < n that do not
 * have a 3 in their decimal representation.
 */
int f(int n)
{
    int count = 0;
    int a;      // The current digit a_j
    int p = 1;  // The current value of 9^j

    while (n > 0) {
        a = n % 10;
        if (a == 3) {
            count = 0;
        }
        if (a <= 3) {
            count += a * p;
        } else {
            count += (a-1) * p;
        }
        n /= 10;
        p *= 9;
    }

    return count;
}
于 2013-01-14T09:01:21.070 に答える