私はSPOJの次の問題に取り組んでいます、
http://www.spoj.com/problems/ARITH/
数値には最大500桁が含まれている必要があると言われていますが、最大500桁の数値の適切なデータ型は何ですか。
1868 次
5 に答える
2
500桁の整数を保持する組み込みのデータ型はありません。したがって、それらをバイトの配列に格納する方法を考え出す必要があります。
http://gmplib.org/の機能からインスピレーションを得てください。つまり、最初に数字をどこかに保存する必要があります。
struct Digit {
size_t len;
char sign;
char* digits;
};
そして、あなたはそのようなもので働くために必要なすべての機能を実装しなければなりませんDigit：
void digit_init(struct Digit* d);
void digit_set(struct Digit* d, const char* digits);
void digit_add(struct Digit* a, struct Digit* b, struct Digit* result);
void digit_mult(struct Digit* a, struct Digit* b, struct Digit* result);
于 2013-03-06T06:19:06.317 に答える
1
多倍長演算にGMPライブラリを使用すると、ソートされます。
于 2013-03-06T06:25:37.997 に答える
0
cにその数の桁を数値として格納するための構築された方法はありません。この質問は、他の方法で算術演算を実行できるように設計されています（数値を常に文字列として残し、少数の実際の数値を一度に処理します）。BigIntegerがあるため、（たとえば）Javaでの質問ははるかに簡単です。しかし、cでそれを実行したい場合は、BigNumの実装が一般的にどのように機能するかを見ていきます。これは参照として役立つかもしれません：
于 2013-03-06T06:26:07.130 に答える
0
乗算ごとに、最初の数値に2番目の数値の各桁を乗算します。2番目の数値の最後の桁の積から始めて、部分的な結果を上下に並べます。各部分的な結果は、対応する数字に揃える必要があります。」
この制約のため、
char bignum[MAX_DIGITS+1];に代わる実用的な方法はありません。
編集 -これは私の最初の応答でした。中間結果を印刷する必要がない場合でも、それは役に立ちます。
基数10に数値を書き留めることに重点が置かれ、入力が基数10にあるため、基数10の微分配列を使用することをお勧めします。Charsは長い乗算を研究するのに適した候補ですが、基数を100、1e4、 1e6または1e9は理にかなっています。
ベース100はuint8_tまたはcharに適合し、ベース10000はuint16_tに適合します（16x16 ==> 32の乗算は、ほとんどの組み込みプロセッサでも使用できます）。Doublesは、最大2 ^ 53-1の正確な値を保持できます。これにより、各被乗数は実質的に1e6に制限されます。
たとえば、base 1e8を使用すると、（uint32_t）に8桁を格納でき、乗算の結果を（uint64_t）に論理的に格納できます。また、基数2のbignumを10進表現に変換するために必要な長い除算なしで、数値を簡単に印刷できます。
struct big_int {
uint32_t digits[MAX_DIGITS/8];
unsigned int length; //
int sign; // or possibly use int length and negative lengths
};
于 2013-03-06T06:37:28.930 に答える
0
私の知る限り、このような精度で算術演算を実行するための組み込み関数/型はありません。CでもC++でもありません。STLでもありません。C++のブーストもありません。SPOJに提出するため、カスタムライブラリをリンクすることはできません。私の知る限り、Cの使用を主張し、SPOJで問題が発生している場合は、独自のルーチンを作成するか、コピーして貼り付けることしかできません。
または、Big-Integerサポートが組み込まれているJava/Pythonを試してください。
簡単に言えば、SPOJに提出するという事実を考えると、これを達成するためのエレガントな方法はありません。
于 2013-03-06T08:44:40.510 に答える