0

次のように数値をループする次のコードがあるとします。

 int p;
 cin>>p;
 for(unsigned long long int i=3*pow(10,p);i<6*pow(10,p);i++){

              //some code goes here
 }

ここで、特定の条件チェックに基づいてi、範囲の間にa を出力する必要があります。3*pow(10,p)<= i <6*pow(10,p)

コードは正常に動作しますupto p=8が、その後かなり遅くなり、コンパイラが行き詰まるようですp=9,10,11。問題は正しいデータ型を使用することにあると思います。ここで使用する正しいデータ型は何ですか?

このループの目的は、範囲内の適切な数値を見つけることです。適切な数字の条件は次のとおりです。1) 数字として 3、5、またはその両方。他の数字は使用できません。2) 3 の出現回数は 5 で割り切れる。 3) 5 の出現回数は 3 で割り切れる。

注:unsigned long long intここで使用しました(0 to 18,446,744,073,709,551,615)。私は32 ビット マシンで実行しています。

4

1 に答える 1

2

<cstdint> およびそのint64_t(64 ビットであることが保証されている) を使用でき、ループの外で電力を計算する必要があります。最近の C または C++ 標準では少なくとも 64ビットlong longです。

しかし、1201ProgramAlarmのコメントで述べたように、3e11 (つまり 3000 億) ループは、私たちの高速マシンでも大量です。数分または数時間かかる場合があります。基本的な操作にはナノ秒 (またはその半分) が必要です。3e9 操作には数秒かかります。3e11 操作には数分かかります。ループ本体は、数千 (またはそれ以上) の基本操作 (機械語命令など) を実行できます。

行き詰まっているのはコンパイラではありません: コードのコンパイルは簡単かつ迅速です (プログラムのサイズが合理的である限り、たとえばコードが 1 万行未満で、異常なプリプロセッサやテンプレート展開のトリックによって異常に展開されない限り)。コンパイルされた実行可能ファイルを実行しているコンピューターです。

コードをベンチマークする場合は、コンパイラで最適化を有効にすることを忘れないでください (たとえば、 GCCg++ -Wall -O2 -arch=nativeを使用している場合はコンパイルします ...)

問題についてもっとよく考えて、検索スペースが小さくなるように再定式化する必要があります。

実際、まともな数字は、それらを表す数字の文字列として考えられるかもしれません。結局のところ、数字には数字がなく (特に、2 進数または 3 進数表記で表された数字は3数字として持つことができません)、数字の一部の表現のみが数字を持ちます。

3次に、12 文字よりも短いorの文字列のみを考慮する必要が5あり、その数ははるかに少なくなります (10000 未満、おそらく 2 13未満、つまり 8192 未満)。1万回繰り返すのは速いはずです。したがって、たとえば 15 文字よりも小さいすべての文字列を生成し、その中に と のみ3を5含めて、適切かどうかをテストします。

于 2015-11-06T05:23:32.010 に答える