7

問題は、与えられた 10 進数が与えられた基数で持つことができる桁数を決定するための式を導出することです。

例: 10 進数 100006 は、基数 2、3、4、5、6、7、8 のそれぞれ 17、11、9、8、7、6、8 桁で表すことができます。

これまでに導き出した式は次のようになります: (log10(num) /log10(base)) + 1.

C/C++ では、この式を使用して上記の結果を計算しました。

long long int size = ((double)log10(num) / (double)log10(base)) + 1.0;

しかし、悲しいことに、式が正しい答えを与えていないのは、次のような場合です。

Number 8 in  base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 64 in  base 2 : 1,0,0,0,0,0,0
Number of digits: 7
Formula returned: 6

Number 64 in  base 4 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 125 in  base 5 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 128 in  base 2 : 1,0,0,0,0,0,0,0
Number of digits: 8
Formula returned: 7

Number 216 in  base 6 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 243 in  base 3 : 1,0,0,0,0,0
Number of digits: 6
Formula returned: 5

Number 343 in  base 7 : 1,0,0,0
Number of digits: 4
Formula returned: 3

したがって、エラーは1桁です。考えられるすべてのケースで機能するように、式を修正するのを誰かに手伝ってもらいたいだけです.

編集：入力仕様に従って、10000000000、つまり10 ^ 10のようなケースに対処する必要があります.C / C ++のlog10（）がそのようなケースを処理できるとは思いませんか？したがって、この問題の他の手順/式は高く評価されます。

4

13 に答える 13

8

コンパイラ設定に高速フローティング操作があります。正確な浮き操作が必要です。問題は、log10(8)/log10(2) は数学では常に 3 です。しかし、例えば、あなたの結果は 2.99999 か​​もしれません。悪いです。少量の添加剤を追加する必要がありますが、0.5 は追加しないでください。約 .00001 程度である必要があります。

ほぼ真の公式：

int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);

本当に本当の解決策

数式の結果を確認する必要があります。複雑さはO(log log n)またはO(log result)！

int fast_power(int base, int s)
{
    int res = 1;
    while (s) {
        if (s%2) {
            res*=base;
            s--;
        } else {
            s/=2;
            base*=base;
        }
    }
    return res;
}

int digits_size(int n, int base)
{
    int s = int(log10(1.0*n)/log10(1.0*base)) + 1;
    return fast_power(base, s) > n ? s : s+1;
}

baseこのチェックは、乗算によるブルート フォース テストよりも優れています。

于 2009-12-04T14:19:01.610 に答える
7

次のいずれかが機能します。

>>> from math import *
>>> def digits(n, b=10):
...     return int(1 + floor(log(n, b))) if n else 1
...
>>> def digits(n, b=10):
...     return int(ceil(log(n + 1, b))) if n else 1
...

最初のバージョンはmathpath.orgで説明されています。2 番目のバージョンでは、底bがd桁の最小の数である任意の数n+ 1に対して正しい答えを得るために が必要です。つまり、基数bで10...0と書かれている数字です。入力は特殊なケースとして扱われなければならないことに注意してください。0

10 進数の例:

>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3

バイナリ：

>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11

編集：OPは、logソリューションが大きな入力に対して機能しない可能性があると述べています。それについてはわかりませんが、もしそうなら、次のコードは壊れないはずです。これは整数演算のみを使用するためです (今回は C で)。

unsigned int 
digits(unsigned long long n, unsigned long long b)
{
  unsigned int d = 0;
  while (d++, n /= b);
  return d;
}

このコードはおそらく効率が悪いでしょう。はい、それは最大のあいまいさのポイントのために書かれました。それは単に、すべての数には少なくとも 1 つの数字があり、それによって割らbないすべての除算0は追加の数字の存在を意味するという観測を使用しています。より読みやすいバージョンは次のとおりです。

unsigned int 
digits(unsigned long long n, unsigned long long b)
{
  unsigned int d = 1;
  while (n /= b) {
    d++;
  }
  return d;
}
于 2009-12-04T14:11:19.863 に答える
5

指定された基数の数字の桁数

于 2009-12-04T14:08:05.080 に答える
3

あなたの式は正しいので（試してみました）、除算の丸め誤差であり、数値が本来あるべき整数値よりわずかに小さくなると思います。そのため、整数に切り捨てると、1 を失います。最終的な値に 0.5 を追加してみてください (切り捨てが実際には丸め演算になるようにします)。

于 2009-12-04T14:08:42.503 に答える
2

あなたが望むのは、現在計算しているものである floor(1+log b (n))ではなく、 ceiling (= 以下を超えない最小の整数) log b (n+1) です。

あなたは試すことができます：

int digits = (int) ceil( log((double)(n+1)) / log((double)base) );
于 2009-12-04T14:12:01.023 に答える
1

あなたの式を使って、

log(8)/log(2) + 1 = 4

問題は対数計算の精度にあります。使用する

ceil(log(n+1)/log(b))

その問題を解決するはずです。これはまったく同じではありません

ceil(log(n)/log(b))

これは、n=8 b=2 に対して答え 3 を与えるため、次の式と同じではありません。

log(n+1)/log(b) + 1

これは、n=7 b=2 に対して答え 4 を与えるためです (完全な精度で計算した場合)。

実際、g++ を使用して最初のフォームを実装およびコンパイルすると、興味深い結果が得られます。

double n = double(atoi(argv[1]));
double b = double(atoi(argv[2]));
int i = int(std::log(n)/std::log(b) + 1.0);

失敗します（IEは答え3を返します）、一方で、

double v = std::log(n)/std::log(b) + 1.0;
int i = int(v);

成功します (答えは 4 になります)。もう少し見ると第三形態かな

ceil(log(n+0.5)/log(b))

n (または 2 番目の形式では n+1) が b の整数乗 (n の整数値) である場合の「重大な」ケースを回避するため、より安定します。

于 2009-12-04T14:18:17.913 に答える
0 
static int numInBase(int num, int theBase)
{
   if(num == 0) return 0;
   if (num == theBase) return 1;
   return 1 + numInBase(num/theBase,theBase);
}
于 2009-12-04T16:23:16.660 に答える
0

浮動小数点の丸めの問題。

log10(216) / log10(6) =  2.9999999999999996

ただし、次の場合は機能しないため、提案されているように 0.5 を追加することはできません。

log10(1295) = log10(6) = 3.9995691928566091   //    5, 5, 5, 5
log10(1296) = log10(6) = 4.0                  // 1, 0, 0, 0, 0

log(value, base) 関数を使用すると、これらの丸め誤差を回避できる可能性があります。

于 2009-12-04T14:18:29.473 に答える
0

丸め関数 (例: + 0.5) をコードのどこかにラップすることは有益かもしれません: 割り算が (例) 2.99989787 を生成している可能性が非常に高く、これに 1.0 が追加され、3.99989787 が与えられ、それが int に変換されると、次のようになります。 3.

于 2009-12-04T14:09:21.947 に答える
0

式は私にとって正しいようです：

Number 8 in  base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3

log10(8) = 0.903089
log10(2) = 0.301029

Division => 3

+1 => 4

したがって、それは間違いなく単なる丸め誤差です。

于 2009-12-04T14:11:26.383 に答える
0

他のエラーを生成せずに丸めエラーを排除する唯一の方法は、整数対数を使用または実装することだと思います。

于 2009-12-04T15:01:37.620 に答える