2

さて、私はフィボナッチ ジェネレーターで使用するスケーラブルなデータ型を構築するという課題を受け取りました。数列の 1000 番目の数値までテストしに行ったとき、その課題はほぼ完了していました。

配列がずれていることに気付き、問題はシーケンスの 262 番目にあると判断しました。少しデバッグした後、これがリンクされたリストが7つの整数から8つの整数に移動する場所であることを発見しましたが、それが問題に関連していることはわかりません.

私が探している番号は次のとおりです。

2 542 592 393 026 885 507 715 496 646 813 780 220 945 054 040 571 721 231

私が得ている数は次のとおりです。

1 154 259 239 326 885 507 715 496 646 813 780 220 945 054 040 571 721 231

お気づきかもしれませんが、最後のチャンク (左端) までは非常によく似ています。

私のソースはSOには少し長いので、要旨を作成しました:

https://gist.github.com/anonymous/5802620

1,000,000,000 を超えるものを運ぶという魔法は、378 行目の関数で発生し ます。

更新として、私はまだ「近いが、葉巻はありません」という出力を得ています。犯人である可能性が高いコードは次のとおりです（投稿された回答を含む）：

Giant Giant::operator + (const Giant & rightSide)
{
   Giant returned;
   int extra = 0;

   for(int i = 0;
      i < chunks.getNumItems() && i < rightSide.chunks.getNumItems(); i++)
   {
      int num = chunks.getData(i) + rightSide.chunks.getData(i);
      returned.chunks.insert((num + extra) % chunkSize,
         returned.chunks.getNumItems());
      extra = (num + extra) / chunkSize;
   }

   if(chunks.getNumItems() > rightSide.chunks.getNumItems())
   {
      for(int i = rightSide.chunks.getNumItems();
          i < chunks.getNumItems(); ++i)
      {
         returned.chunks.insert(extra + chunks.getData(i),
            returned.chunks.getNumItems());
         extra = 0;
      }
   }
   else if(chunks.getNumItems() < rightSide.chunks.getNumItems())
   {
      for(int i = chunks.getNumItems();
          i < rightSide.chunks.getNumItems(); ++i)
      {
         returned.chunks.insert(extra + rightSide.chunks.getData(i),
            returned.chunks.getNumItems());
         extra = 0;
      }
   }

   if (extra != 0)
   {
       returned.chunks.insert(extra, returned.chunks.getNumItems());
   }

   return returned;
}

更新 クラスのメンバーがやって来て、コードを調べました。ここに問題がありました：

ostream & operator << (ostream & out, const Giant & giant)
{
   for(int i = giant.chunks.getNumItems() - 1;
      i >= 0; i -= 1)
   {
      if (i != giant.chunks.getNumItems()-1)
         out << setw(9) << setfill('0');
      out << giant.chunks.getData(i);
   }
   return out;
}

問題の原因となった先行ゼロを強制的に表示するのを忘れていました。解決策が見つかりました。

4

3 に答える 3

2

あなたの問題は 387 行目と 389 行目にあるようです。あなたはextraすぐに方程式を説明していません。これらの行にはそれぞれ((num + extra) % chunkSize)とが必要extra = (num + extra )/ chunkSize;です。現在の実装では、セグメントの 1 つは、キャリー付きの 0 ではなく、キャリーなしの 1000000000 である可能性があります (あなたが望んでいた場合、私があなたの意図を読んでいる場合)。

于 2013-06-18T04:29:28.377 に答える
0

更新 クラスのメンバーがやって来て、コードを調べました。ここに問題がありました：

ostream & operator << (ostream & out, const Giant & giant)
{
   for(int i = giant.chunks.getNumItems() - 1;
      i >= 0; i -= 1)
   {
      if (i != giant.chunks.getNumItems()-1)
         out << setw(9) << setfill('0');
      out << giant.chunks.getData(i);
   }
   return out;
}

問題の原因となった先行ゼロを強制的に表示するのを忘れていました。解決策が見つかりました。

于 2013-06-18T16:00:04.917 に答える