3

私は2^（n-1）を解く単純な組み合わせ問題を解いている最中です。

唯一の問題は、1 <= n <= 2 ^ 31 -1（符号付き32ビット整数の最大値）です。

JavaのBigIntegerクラスを使用してみましたが、2 ^ 31/10 ^ 4以上の数値でタイムアウトになるため、明らかに機能しません。

さらに、JavaまたはC++の組み込みクラスのみを使用するように制限されています。

速度が必要であることを知って、文字列の算術演算を行うC++でクラスを作成することにしました。

さて、私が掛け算をするとき、私のプログラムは、効率のために（文字列を繰り返し追加するのではなく）紙の上で掛け算するのと同じように掛け算します。

しかし、それでも、2を単独で2 ^ 31-1倍することはできません。それは、十分に効率的ではありません。

それで私は問題についてのテキストを読み始めました、そして私は解決に至りました...

2^n = 2^(n/2) * 2^(n/2) * 2^(n%2)（ここで、/は整数除算を示し、％は係数を示します）

これは、対数の乗算でべき乗を解くことができることを意味します。しかし、私には、このメソッドをコードに適用する方法を回避できませんか？下限を選択するにはどうすればよいですか。また、最終的な乗算に必要なさまざまな数値を追跡するための最も効率的な方法は何ですか。

この問題を解決する方法について誰かが知っている場合は、詳しく説明してください（サンプルコードをいただければ幸いです）。

アップデート

皆様のご協力に感謝します！java.math.BigInteger明らかに、この問題は現実的な方法で解決されることを意図していますが、ceil（log2（n））の反復のみを実行するべき関数でなんとかアウトパフォームしました。

誰かが私が作成したコードに興味があるなら、ここにあります...

using namespace std;

bool m_greater_or_equal (string & a, string & b){ //is a greater than or equal to b?
    if (a.length()!=b.length()){
        return a.length()>b.length();
    }
    for (int i = 0;i<a.length();i++){
        if (a[i]!=b[i]){
            return a[i]>b[i];
        }
    }
    return true;
}

string add (string& a, string& b){
    if (!m_greater_or_equal(a,b)) return add(b,a);
    string x = string(a.rbegin(),a.rend());
    string y = string(b.rbegin(),b.rend());
    string result = "";
for (int i = 0;i<x.length()-y.length()+1;i++){
    y.push_back('0');
}

int carry = 0;
for (int i =0;i<x.length();i++){
    char c = x[i]+y[i]+carry-'0'-'0';
    carry = c/10;
    c%=10;
    result.push_back(c+'0');
}
if (carry==1) result.push_back('1');
return string(result.rbegin(),result.rend());

}

string multiply (string&a, string&b){
    string row = b, tmp;
    string result = "0";

    for (int i = a.length()-1;i>=0;i--){

        for (int j= 0;j<(a[i]-'0');j++){
            tmp = add(result,row);
            result = tmp;
        }
        row.push_back('0');
    }
    return result;
}

int counter = 0;

string m_pow (string&a, int exp){
    counter++;
    if(exp==1){
        return a;
    }
    if (exp==0){
        return "1";
    }
    string p = m_pow(a,exp/2);
    string res;
    if (exp%2==0){
        res = "1";  //a^exp%2 is a^0 = 1
    } else {
        res = a;   //a^exp%2 is a^1 = a
    }
    string x = multiply(p,p);
    return multiply(x,res);
    //return multiply(multiply(p,p),res); Doesn't work because multiply(p,p) is not const

}

int main(){


    string x ="2";

    cout<<m_pow(x,5000)<<endl<<endl;
    cout<<counter<<endl;

    return 0;
}
4

3 に答える 3

6

@Oliの回答で述べたように、これはコンピューティングの問題ではありません。これは、2進数でsが後に続くのは2^n簡単なことです。10

しかし、それらを10進数で出力したいので、これは非常に大きな数の2進数から10進数に変換する方法の問題になります。

それに対する私の答えは、それは現実的ではないということです。（この質問が好奇心から生じていることを願っています。）

あなたはそれを10進数で計算2^(2^31 - 1)して印刷しようとしていると言います。その数は646,456,993桁の長さです。

  • JavaBigIntegerはそれを行うことができません。これは少数を対象としており、O(n^2)アルゴリズムを使用しています。
  • コメントで述べたように、C++には組み込みのBigNumライブラリはありません。
  • Mathematicaでさえそれを処理することはできません： General::ovfl : Overflow occurred in computation.
  • 最善の策は、GMPライブラリを使用することです。

答えの一部を見たいだけの場合：

2^(2^31 - 1) = 2^2147483647 = 

880806525841981676603746574895920 ... 7925005662562914027527972323328

(total: 646,456,993 digits)

これは、クローズソースのライブラリを使用して行われ、Core i7 2600K @ 4.4GHzで約37秒と3.2GBのメモリを使用しました。これには、6億4600万桁すべてを大規模なテキストファイルに書き込むために必要な時間が含まれます。
（メモ帳でファイルを開くのに、計算に必要な時間よりも時間がかかりました。）

ここで、一般的なケースでそのようなパワーを実際に計算する方法についての質問に答えるために、@dasblinkenlightはSquaringによるExponentiationの変形であるものに対する答えを持っています。

大きな数の場合、2進数から10進数に変換するのは、はるかに難しい作業です。ここでの標準アルゴリズムは分割統治法です。

後者を実装しようとすることはお勧めしません-プログラマーを始める範囲をはるかに超えているからです。（そしてまた、いくぶん数学を多用します）

于 2012-01-07T18:52:57.640 に答える
4

掛け算をする必要はまったくありません。2 ^（n-1）はちょうど1 << (n-1)、つまり1の後に(n-1)ゼロが続きます（2進数）。

于 2012-01-07T17:48:51.187 に答える
3

このメソッドをコードに適用する最も簡単な方法は、最も直接的な方法である再帰的に適用することです。aだけでなく、任意の数で機能するので、より面白くするためにパラメーターとして2受け取るコードを作成しました。a

MyBigInt pow(MyBigInt a, int p) {
    if (!p) return MyBigInt.One;
    MyBigInt halfPower = pow(a, p/2);
    MyBigInt res = (p%2 == 0) ? MyBigInt.One : a;
    return res * halfPower * halfPower;
}
于 2012-01-07T17:50:16.367 に答える