1

引用符で囲まれたテキストは、私の問題を理解するために必要な場合に備えて、プログラムの背景を少し示しています。読みたくない場合は、最後に引用されていないもので完全に理解できるかもしれません。

私は C++ でのソートの共通プロジェクトに取り組んでおり、現在基数ソートを行っています。私はそれを関数として持っており、文字列のベクトル、最大桁数を保持する整数、および数値の基数/基数を持つ整数: (numbers, maxDigits, radix)

プログラムは基数が異なる数値を文字列として受け取るため、stoi を使用してそれらを基数 10 の整数に変換し、プロセスを一般化しやすくしています。アルゴリズムの簡単な要約は次のとおりです。

  • 値 0 から 9 を保持する 10 個のキューを作成します
  • 各桁を反復します (maxDigit 回)
    • ベクトル内の各数値を反復処理します (ここでは基数 10 に変換されます)
    • 見ている現在の数字に基づいてそれらをキューに入れます
    • キューから番号を最初から最後まで引き出してベクトルに戻します

私が頭を抱えようとしている問題については、maxDigit 値 (ユーザーが入力した基数に関係なく) を base 10 に変換した後に maxDigit 値に変更したいと考えています。つまり、ユーザーが使用したとしますコード

radixSort(myVector, 8, 2)

最大桁数8と基数2の数値のベクトルをソートします。数値の基数を10に変換するので、それが理にかなっていれば、maxDigitsも変更するアルゴリズムを見つけようとしています。

試行錯誤しながら簡単な方法を見つけようとして、これについてたくさん考えてみました。ヒントや正しい方向への助けを得ることができれば、それは大きな助けになるでしょう.

4

1 に答える 1

1

何かが基数 2 で最大桁数が 8 の場合、その最大値はすべて 1 です。= 255 、11111111つまり (2^8 - 1) です。

基数 10 の最大桁数は、その最大値を表すために必要なものになります。これは、255 (2.406540​​18043) の 10 を底とする対数で、3 に切り上げられます。

log10 (radix^maxdigits - 1)したがって、基本的には最も近い整数に切り上げます。

于 2014-10-27T00:09:29.373 に答える