4

10 進数を受け取り、その数値の 2 進数表現を返す 2 つの関数を作成しました。簡単な計算の後で、1 と 0 を文字列に連結するという簡単な方法を選択しました。これを行うための反復的かつ再帰的な方法を作成しました。次に、先生がくれたタイマー クラスで 2 つの方法の時間を計りました。私の再帰的方法は、反復的方法と比較して約 2 倍高速であることが判明しました。なぜこれが当てはまるのでしょうか？

string CConversion::decimalToBinaryIterative(int num)
{
   string ss;
   while(num > 0)
   {
        if  (num%2 != 0)
        {
            ss = '1' + ss;
        }
        else
        {
            ss = '0' + ss;
        }
        num=num/2;
    }
    return ss;
}
string CConversion::decimalToBinaryRecursive(int num)
{
    if(num <= 0)
    { 
        return "";
    } 
    else 
    {
       if  (num%2 != 0)
       {
            return decimalToBinaryRecursive(num/2) + '1';
       }
        else
        {
            return  decimalToBinaryRecursive(num/2) + '0';
        }
    }

}
4

2 に答える 2

5

std::string文字列の容量が許せば、文字列をコピーせずに追加できるため、文字を a に追加する方が、事前に保留中の文字を追加するよりもコストがかかりません。

ただし、先頭に追加するには、常に文字列全体のコピーが必要です。

反復コードをこれに変更すると

string ss;
while(num > 0)
{
    if  (num%2 != 0)
    {
        ss = ss + '1';
    }
    else
    {
        ss = ss + '0';
    }
    num=num/2;
 }
 return string(ss.rbegin(), ss.rend());

タイミングはほぼ同じになるか、反復がわずかに速くなるはずです。

于 2013-11-11T15:31:37.337 に答える
3

唯一の疑わしい部分は、文字列を連結する方法です。

ss = ss + '1';  // 1

ss = '1' + ss;  // 2

最初のものは (再帰的な方法のように) すべての文字をシフトせず、文字列の末尾に文字を追加する可能性があります。

しかし、2 つ目は、すべての文字を右にシフトする (または新しい文字列を作成する) 必要があります。

この問題を解決するにはss += 'x'、関数の最後ですべての文字列を連結して反転させるために使用します。

于 2013-11-11T15:28:05.820 に答える