0

私は C++ が初めてで、「BigInt」クラスを作成しようとしています。私は、数値をベクトルに読み込むことに基づいてほとんどの実装を行うことにしました。

ここまでは、入力文字列のコピー コンストラクターのみを記述しました。

Largenum::Largenum(std::string input)
{
 for (std::string::const_iterator it = input.begin(); it!=input.end(); ++it)
    {
      number.push_back(*it- '0');
    }
}

私が抱えている問題は、追加機能にあります。数回テストした後、機能するように見える関数を作成しましたが、ご覧のとおり、非常に非効率的です。次のような2つの異なるベクトルがあります。

std::vector<int> x = {1,3,4,5,9,1};
std::vector<int> y = {2,4,5,6};

この問題を解決するために私が考えた方法は、短い方の前に 0 を追加することでした。この場合は y ベクトルを使用して、両方のベクトルを次のように同じサイズにします。

x = {1,3,4,5,9,1};
y = {0,0,2,4,5,6};

次に、基本スタイルの追加を使用してそれらを追加します。

ベクトル Y の前に 0 を追加したくないのは、数が多いと遅くなるためです。私の現在の解決策は、ベクトルを逆にしてから、適切な量の 0 を push_back してから元に戻すことです。これは、単に前面に挿入するよりも遅くなる可能性があります。まだテストしていません。

問題は、ベクトルにすべての加算を行った後、結果を push_back することです。逆方向ベクトルが残っているので、もう一度逆方向を使用する必要があります! 私の方法よりもはるかに優れた方法が必要ですが、私はそれを見つけることに行き詰まっています。理想的には、Aもconstにします。関数のコードは次のとおりです。

Largenum Largenum::operator+(Largenum &A)
{
    bool carry = 0; 
    Largenum sum;                

    std::vector<int>::size_type max = std::max(A.number.size(), this->number.size());
    std::vector<int>::size_type diff = std::abs (A.number.size()-this->number.size());

    if (A.number.size()>this->number.size())
    {
        std::reverse(this->number.begin(), this->number.end());
        for (std::vector<int>::size_type i = 0; i<(max-diff); ++i) this->number.push_back(0);
        std::reverse(this->number.begin(), this->number.end());
    }
    else if (this->number.size() > A.number.size())
    {
        std::reverse(A.number.begin(), A.number.end());
        for (std::vector<int>::size_type i = 0; i<(max-diff); ++i) A.number.push_back(0);
        std::reverse(A.number.begin(), A.number.end());
    }
    for (std::vector<int>::size_type i = max; i!=0; --i)
    {
        int num = (A.number[i-1] + this->number[i-1] + carry)%10;
        sum.number.push_back(num);
        (A.number[i-1] + this->number[i-1] + carry >= 10) ? carry = 1 : carry = 0;
    }
    if (carry) sum.number.push_back(1);

   reverse(sum.number.begin(), sum.number.end());

   return sum;
}

誰かが素晴らしい意見を持っているとしたら、これは C++ でクラスを使用する私の最初のプログラムであり、かなり圧倒されます。

4

2 に答える 2

1

あなたの機能は、私が見た中で最も最適なものにかなり近いと思います。それでも、それを改善するためのいくつかの提案があります：

  • 10 進数の数値システムは非常に非効率的です。大きな数には多くの桁があります。追加する必要がある桁数を減らすために、より高い基数を使用することをお勧めします。このような数値を人間が読める形式で読み書きするのは少し難しくなりますが、桁数が少なくなるため、操作を数回最適化します。
  • 大きな整数を実装するときは、それらを逆の順序で表すため、インデックス 0 の位置に最下位桁があり、配列の最後に最上位桁があります。push_backこのようにして、キャリーによって新しい桁を追加する必要がある場合、完全な逆ではなく、のみを実行します。
于 2013-06-19T14:04:47.367 に答える
0

1 つの問題: 整数モジュラスは、分岐予測ミスと比較しても、最新のプロセッサではかなり遅いです。明示的な %10 を実行する代わりに、3 番目の for ループでこれを試してください。

int num = A.number[i-1] + this->number[i-1] + carry;
if(num >= 10)
{
    carry = 1;
    num -= 10;
}
else
{
    carry = 0;
}
sum.number.push_back(num);
于 2013-06-20T12:28:00.770 に答える