私はいくつかのプロジェクトオイラーの問題を行っていますが、ほとんどの場合、計算には int、float、double などを超える大きな数値が含まれます。
まず、多数の問題を回避するために、より効率的な計算方法を探す必要があることを知っています。Bignum ライブラリについて聞いたことがあります。
しかし、学者の興味のために、この問題に対する独自のソリューションをコーディングする方法を知りたいです。
専門家が私を助けてくれますか？(私の言語は C です)
17022 次
6 に答える
17
コンピューターがネイティブタイプで簡単に処理できるベースに大きな数値を格納してから、数字を可変長配列に格納する必要があります。簡単にするために、これを行う方法のコツをつかむために、基数10に数値を格納することから始めることをお勧めします。デバッグがはるかに簡単になります。
この形式で数値を格納できるクラスができたら、このクラスに加算、減算、乗算などの演算を実装するだけです。各演算は、オペランドの桁を繰り返し処理して結合する必要があります。桁がベースより大きくならないように、正しく実行するように注意してください。足し算と引き算は簡単です。単純なアルゴリズムではネストされたループが必要になるため、乗算にはもう少し作業が必要です。次に、それが機能するようになったら、効率的な方法でべき乗を実装してみることができます（たとえば、2乗を繰り返す）。
深刻なbignum実装を作成することを計画している場合、base10はそれを削減しません。それはメモリの無駄であり、遅くなります。256やワードサイズ（2 ** 32）など、コンピュータにとって自然なベースを選択する必要があります。ただし、これを行うと、単純に2桁を追加するとオーバーフローが発生するため、単純な操作がより困難になるため、慎重に処理する必要があります。
于 2010-01-02T10:38:07.617 に答える
12
C は Project Euler には適していません。C の利点は、生の速度、マシンの移植性 (標準 C とある程度)、言語の相互運用性 (ある言語が別の言語と通信する場合、C が一般的な最初の選択肢です)、特定のライブラリまたはプラットフォームの API に固執すること (C であるため) です。 OS API など)、安定した言語と stdlib が一般的です。 これらの利点はどれも、Project Euler の問題の解決には当てはまりません。 ほとんどの問題は生の計算に関するものではなく、必要なアルゴリズムを理解することであり、提出まで一日中座って待つことができるため、生の速度でさえありません。
C の経験を広げるために Project Euler の問題に挑戦しているのであれば、それはまったく問題ありませんが、この経験は、あなたが取り組む可能性のある長期にわたる実際の C プロジェクトには必ずしも当てはまらないことに注意してください。
この種の短い 1 回限りの問題については、一般に「スクリプト言語」と呼ばれる言語の方が、(開発時間で) より速く、より簡単に機能します。Python を試してみてください。C API を含む多くの点で C に近く、さまざまな一般的な「スクリプト言語」の中で、C プロジェクトと組み合わせて最もよく使用される言語はおそらく Python です。
これは不人気な答えになるかもしれませんが、それは暴言ではありません-さらに、私はCが本当に好きで、C/C++を頻繁に使用します-そして、あなたの問題に対する明確な答えがあります:「Cを使用しないでください」、あなたの最終的な大きな選択した選択肢に応じて、ソリューションを番号付けします。再び Python を取り上げると、整数には上限がありません (以下の注記)。私はこれを使用して Project Euler の問題に対する回答を自然にコーディングします。他の言語では、比較による苦痛を伴う代替数値ライブラリを使用する必要があります。
( Python 整数: 2.x には 'int' と 'long' の 2 つの整数型があります (これらは 3.x で完全に統合されています)。それらの間の変換は実質的にシームレスで、'long' は任意の大きな値を許容します。 C の long のように大きな 'int' 型になるのではなく)。
于 2010-01-02T11:10:04.450 に答える
4
C/C++ の一般的な bignum ライブラリはGNU MP Bignum Libraryです。私はいくつかの Project Euler の問題に C を使用しましたが、C は Euler の問題にあまり適した言語ではないという事実が残っています。パフォーマンスがより重要である場合、C はより多くの機能を提供できますが、今では Ruby (他にもたくさんあります) などの bignum サポートが組み込まれている言語を使用する方がはるかに優れています。
于 2010-01-02T12:14:12.213 に答える
3
簡単な方法は、数値を基数 b の文字列表現と考えることです。b=10 とすると、このような 2 つの文字列の足し算のような単純な算術演算は、ペンと紙で数を足すのと同じ方法で行うことができます。他の単純な操作についても同様です。より良い結果を得るには、より大きなベースを取ることができます。
このような単純な bignum の実装は、ほとんどのプロジェクト オイラーの問題 (おそらくすべてですが、オイラーであまり解決していないので確信が持てません) には十分なはずですが、乗算や部門/mod。
練習用に独自の bignum を作成することをお勧めしますが、本当に行き詰まっている場合は、既に実装されている bigint ライブラリのコードからアイデアを得ることができます。本格的な実装では、gmp のようなものが当然の選択です。しかし、同様の練習問題をオンラインで解くときに、他の人がコーディングした小さな bigint を見つけることもできます (例: Abednego のbigint.cpp )。
于 2010-01-02T11:04:10.560 に答える
1
これは、C用の素晴らしくシンプルなbignumモジュールです。アイデアについては、そこから学ぶことができます。Cコードは最高品質ではありませんが、アルゴリズムは適切に実装されており、非常に一般的です。
より高度なものについては、GMPを調べてください。
于 2010-01-02T10:32:23.293 に答える
0
素敵な C++ バージョンが必要な場合 (あなたは C と言いましたが、これは非常に興味深いコードです)、CGAL の内部を見てください: http://www.cgal.org/
于 2010-01-02T11:04:49.280 に答える