0

ここで noob を完了します。これを C++ で試してみます。任意の基数の数値の配列を作成しようとしています。つまり、新しいベースを定義し、この配列を新しいベースで「カウント」したいと考えています。例: 基数 78。最初の「桁」に追加すると、78 に達したときに 2 番目の桁にオーバーフローするような方法で、3 つの 78 基数の配列を作成したいと考えています。[1] [ 1] [77] + 1 = [1] [2] [0]...

これは効率的な方法で可能ですか?ベース10000の20の長い配列としましょう。それとも、計算時間が私を殺しますか?

ありがとう。

4

2 に答える 2

0

の線に沿って何かを試してください

class counter_array {
  public:
    static const int LEN = 20;
    static const int base = 5;

    counter_array operator+=(int inc) {
      arr[0] += inc;
      for (int i = 1; i < LEN; ++i) {
        int old = arr[i];
        arr[i] += arr[i-1] / base;
        arr[i-1] %= base;
        if (arr[i] == old) {
          break;
        }
      }
    }

  private:
    int arr[len];
};

私はデバッグを行いませんでしたが、ドリフトを取得する必要があります。

于 2013-10-22T08:54:56.157 に答える
0

内部的に (少なくとも最新のすべてのマシン、および C または C++ をサポートするすべてのマシンでは)、整数値はバイナリです。他のベースは、入力と出力にのみ使用されます。カウントなどの内部操作は、値とその表現方法に依存するという意味で、「ベース独立」です。

問題は、long long(少なくとも 64 ビット) が十分に大きいかどうかです。その場合、変換ルーチンを提供するだけで済みます。(strtollは 36 までの基数をサポートしますが、対応する出力ルーチンはありません。) そうでない場合は、4 つの基本演算子に Knuth のアルゴリズムを使用して、より大きな整数型を実装する必要があります。また、入力と出力の変換ルーチンを提供する必要があります (4 つの基本操作があれば簡単です)。

もちろん、より長い整数型の実装には任意のベースを使用できます。伝統的に、基数 2^n (n は利用可能な機械語サイズ) が効率上の理由から使用されてきましたが、基数 10000 や、機械語の 1 つに収まる基数の使用を止めるものは何もありません。あなたの数値は、より多くのメモリを必要とするだけです(したがって、より多くの時間が必要になります)。アルゴリズムは同じです (Knuth のもの)。

于 2013-10-22T09:05:52.573 に答える