1

Consider the problem:

It can be shown that for some powers of two in decimal format like:
2^9 = 512
2^89 = 618,970,019,642,690,137,449,562,112

The results end in a string consisting of 1s and 2s. In fact, it can be proven that for every integer R, there exists a power of 2 such that 2K where K > 0 has a string of only 1s and 2s in its last R digits.

It can be shown clearly in the table below:

R Smallest K 2^K
1 1 2
2 9 512
3 89 ...112
4 89 ...2112

Using this technique, what then is the sum of all the smallest K values for 1 <= R <= 10? Proposed sol: Now this problem ain't that difficult to solve. You can simply do int temp = power(2, int) and then if you can get the length of the temp then multiply it with

(100^len)-i or (10^len)-i

// where i would determine how many last digits you want.

Now this temp = power(2,int) gets much higher with increasing int that you can't even store it in the int type or even in long int.... So what would be done. And is there any other solution based on bit strings. I guess that might make this problem easy. Thanks in advance.

4

4 に答える 4

2

いいえ、「ビット列」に基づく解決策はないと思います。それはかなり非効率的です。しかし、int 型よりもはるかに大きな固定サイズの変数型、またはメモリ容量によってのみ制限される任意のサイズの変数型を特徴とするGMPのような Bignum ライブラリがあり、それに加えて、ソフトウェア FPU エミュレーションと同様に機能する数学演算のセットが一致します。

マイナーな言い換えによる参照後の引用。

 #include <gmpxx.h>

 int
 main (void)
 {
   mpz_class a, b, c;

   a = 1234;
   b = "-5676739826856836954375492356569366529629568926519085610160816539856926459237598";
   c = a+b;
   cout << "sum is " << c << "\n";
   cout << "absolute value is " << abs(c) << "\n";

   return 0;
 }

C++ 演算子のオーバーロードのおかげで、ANSI C バージョンよりもはるかに使いやすくなっています。

于 2012-12-17T10:21:17.397 に答える
2

n結果の最下位桁のみに関心があるため、それらのみを計算するアルゴリズムを考案することができます。書かれた乗算の標準アルゴリズムに基づいてn、積の最下位桁が被乗数の最下位桁によって完全に決定されることがわかりますn。これに基づいて、 の桁数をR^Kに収まるように計算するアルゴリズムを作成できるはずlong intです。

long int遭遇する可能性のある唯一の問題は、が保持できるよりも長い一致するシーケンスで終わる数字が存在する可能性があることです。その場合でも、独自のアルゴリズムまたはライブラリを使用して追加の数字を計算することに頼ることができます。

これは基本的に、多数のライブラリが行うことと同じであることに注意してください。必要になる可能性が低い桁数を計算しているため、アプローチのみがより効率的である可能性があります。

于 2012-12-17T10:34:58.753 に答える
1

GMP を試してみてください。http: //gmplib.org/
メモリに収まるサイズであれば、任意のサイズの数値を格納できます。
ただし、力ずくのアプローチが少ない方が良いかもしれません。

于 2012-12-17T10:18:42.913 に答える
1

バイナリ文字列を std::bitset または std::vector www.cplusplus.com/reference/bitset/bitset/に格納できます

ビットセットはあなたの選択だと思います。

2 の累乗の演算に大きな算術演算を使用することはできませんが、

于 2012-12-17T10:19:59.607 に答える