0

効率的かつ迅速な方法でプレフィックスを番号に追加して削除するにはどうすればよいですか? (数値には任意の桁数を指定できますが、数値に制限はありません) たとえば 122121 のような数値があり、先頭に 9 桁を追加して 9122121 にしたい場合、その後、数値の最初の桁を削除する必要があります。ベクトルに分割し、前の数字 (この場合は 9) をプッシュし、数字から数字を作成します (10 を掛けた反復)。より効率的な方法はありますか？

4

6 に答える 6

3

効率が必要な場合は、数値以外は使用しないでください。ベクトル、文字列などは使用しないでください。あなたの場合:

#include <iostream>

unsigned long long add_prefix( unsigned long long number, unsigned prefix )
{
    // if you want the example marked (X) below to print "9", add this line:
    if( number == 0 ) return prefix;

    // without the above, the result of (X) would be "90"

    unsigned long long tmp = ( number >= 100000 ) ? 1000000 : 10;
    while( number >= tmp ) tmp *= 10;
    return number + prefix * tmp;
}

int main()
{
    std::cout << add_prefix( 122121, 9 ) << std::endl; // prints 9122121
    std::cout << add_prefix( 122121, 987 ) << std::endl; // prints 987122121
    std::cout << add_prefix( 1, 9 ) << std::endl; // prints 91
    std::cout << add_prefix( 0, 9 ) << std::endl; // (X) prints 9 or 90
}

ただし、オーバーフローに注意してください。オーバーフローがなければ、上記は複数桁のプレフィックスでも機能します。プレフィックスを削除する逆アルゴリズムを理解していただければ幸いです。

編集: Andy Prowl が指摘したように、0 は「数字なし」と解釈される可能性があるため、接頭辞の後に数字 0 を付けるべきではありません。

于 2013-03-28T20:25:23.123 に答える
2

floor(log10(number)) + 1 を使用して桁数を計算できます。したがって、コードは次のようになります。

int number = 122121;
int noDigits = floor(log10(number)) + 1;
//Add 9 in front
number += 9*pow(10,noDigits);
//Now strip the 9
number %= pow(10,noDigits);

私はすべてが正しいことを願っています;）

于 2013-03-28T20:24:22.797 に答える
2

二分探索を利用した回答と、これまでに提供された回答の小さなベンチマークを提供します。

二分探索

次の関数は、二分探索を使用して目的の数値の桁数を見つけ、その前に目的の桁を追加します。

int addPrefix(int N, int digit) {
    int multiplier = 0;
    // [1, 5]
    if(N <= 100000) {
        // [1, 3]
        if(N <= 1000) {
            //[1, 2]
            if(N <= 100) {
                //[1, 1]
                if(N <= 10) {
                    multiplier = 10;
                //[2, 2]
                } else {
                    multiplier = 100;
                }
            //[3, 3]
            } else {
                multiplier = 1000;
            }
        //[4, 4]
        } else if(N <= 10000) {
            multiplier = 10000;
        //[5, 5]
        } else {
            multiplier = 100000;
        }
    //[6, 7]
    } else if(N <= 10000000) {
        //[6, 6]
        if(N <= 1000000) {
            multiplier = 1000000;
        //[7, 7]
        } else {
            multiplier = 10000000;
        }
    //[8, 9]
    } else {
        //[8, 8]
        if(N <= 100000000) {
            multiplier = 100000000;
        //[9, 9]
        } else {
            multiplier = 1000000000;
        }
    }
    return N + digit * multiplier;
}

かなり冗長です。intただし、最大 4 回の比較での範囲の数値の桁数を検出します。

基準

提供された各アルゴリズムを 4 億 5000 万回の反復に対して実行する小さなベンチマークを作成しました。決定された桁数ごとに 5000 万回の反復です。

int main(void) {
    int i, j, N = 2, k;
    for(i = 1; i < 9; ++i, N *= 10) {
        for(j = 1; j < 50000000; ++j) {
            k = addPrefix(N, 9);
        }
    }
    return 0;
}

結果：

+-----+-----------+-------------+----------+---------+
| run | Alexander | Daniel Frey | kkuryllo | W.B.    |
+-----+-----------+-------------+----------+---------+
| 1st |    2.204s |      3.983s |   5.145s | 23.216s |
+-----+-----------+-------------+----------+---------+
| 2nd |    2.189s |      4.044s |   5.081s | 23.484s |
+-----+-----------+-------------+----------+---------+
| 3rd |    2.197s |      4.232s |   5.043s | 23.378s |
+-----+-----------+-------------+----------+---------+
| AVG |    2.197s |      4.086s |   5.090s | 23.359s |
+-----+-----------+-------------+----------+---------+

この Gist で使用されているソースは、こちら にあります。

于 2013-03-28T22:03:40.150 に答える
1

数字を std::string に入れて挿入と削除を使用できますが、やり過ぎかもしれません

于 2013-03-28T20:29:32.893 に答える
1

%最初に、自分の数より大きい 10 の最大べき乗を見つけます。次に、それを加算して、あなたの番号に追加します

例えば：

int x;
int addition;
int y = 1;
while (y <= x)
{
    y *= 10;
}

x += addition * y;

私はこのコードをテストしなかったので、例として取り上げてください...他の指示もよくわかりません。明確にする必要があります。

編集OK あなたもいつか最初の桁を削除したいことを理解していると思います。これを行うには、simular アプローチを使用できます。

int x;
int y = 1;
while (y <= x*10)
{
    y *= 10;
}

x %= y;
于 2013-03-28T20:27:52.547 に答える
1

ブーストから字句キャストを使用するのはどうですか? そうすれば、反復をすべて自分で行う必要がなくなります。

http://www.boost.org/doc/libs/1_53_0/doc/html/boost_lexical_cast.html

于 2013-03-28T20:20:39.887 に答える