15

これは古典的なプログラミングの問題であることを理解しています。したがって、解決策としてコードを探しているわけではないことを明確にしたいと思いますが、正しい方向へのプッシュに感謝します。私は C++ を学んでおり、学習プロセスの一環として、いくつかのプログラミングの問題に取り組んでいます。10 億の階乗までの数を処理するプログラムを作成しようとしています。明らかに、これらは膨大な数になり、通常の算術演算を使用するには大きすぎます。この種の問題を解決するためにどの方向に進むべきかについての指示をいただければ幸いです。

可能であれば、追加のライブラリを使用せずにこれを解決しようとします

ありがとう

PS - 問題はここにあります http://www.codechef.com/problems/FCTRL

問題を解決するために使用した方法は次のとおりです。これは、以下のコメントを読むことで達成されました。

解決策 -- 数字の 5 は、ゼロで終わる数字の素因数です。したがって、階乗数を 5 で割って再帰的に商を加算すると、階乗結果の後続ゼロの数が得られます。

EG - 126 の末尾のゼロの数! = 31

126/5 = 25 余り 1

25/5 = 5 残り 0

5/5 = 1 余り 0

25 + 5 + 1 = 31

これはどの値でも機能します。商が 5 未満になるまで除算を続けてください。

4

10 に答える 10

7

この質問をざっと読んだので、本当に正しいかどうかはわかりませんが、演繹的な推測は次のとおりです。

最初の質問 - 数字の末尾にゼロを付けるにはどうすればよいですか? 10 を掛けることによって。

どうやって10倍しますか？10または2 x 5を掛けることによって...

だから、Xのために！10 と 2x5 はいくつありますか?

(幸いなことに、2 と 5 は素数です)

編集：ここに別のヒントがあります-乗算を行う必要はないと思います。別のヒントが必要な場合はお知らせください。

于 2010-01-20T01:14:52.063 に答える
3

ヒント：Nを計算する必要はないかもしれません！Nの終わりのゼロの数を見つけるために！

于 2010-01-20T00:51:40.200 に答える
3

この問題を解決するには、Chris Johnson が言ったように、0 の数を確認する必要があります。

10 の因数は 1,2,5,10 そのものになります。これで、N の各数字をたどることができます。2^x * 5^y * 10^z で書きます。数字の他の要因を破棄します。

これで、答えは Greaterof(x,y)+z になります。

この質問から私が学んだ興味深いことの 1 つは、簡単に比較できるように、素因数の観点から数値の階乗を格納する方が常に優れているということです。

実際に x^y を求めるには、RSA アルゴリズムで使用される簡単な方法がありますが、これは覚えていません。投稿を見つけたら更新しようと思います。

于 2010-01-20T01:06:26.823 に答える
1

私が最初に読んだものから少し変更したので、これはあなたの質問に対する良い答えではありません。しかし、とにかくここに残して、主な総当たり攻撃で実際に計算を行おうとすることの非現実性を示します。

10億の階乗は、どのbignumライブラリにも届きません。このような数値を表すには、ほとんどの人がRAMに持っているよりも多くのスペースが必要になります。作業中に、ストレージから番号のページングを開始する必要があります。これを行う方法があります。最近27000億の場所でπを計算した男はそのようなライブラリを使用しました

于 2010-01-20T00:54:12.437 に答える
1

C ++やその他の言語について考える前に、擬似コードの問題を解決する方法を考え出す必要があると思います。一部の人が指摘しているように、質問の性質は、C++の問題というよりもアルゴリズムの問​​題です。プログラムを学ぶことは考え方を学ぶことであるため、あいまいなライブラリを検索することを提案する人は、滑りやすい坂の方向にあなたを向けていますよね？良いアルゴリズム分析テキストを見つけてください。そうすれば、それはあなたに役立つでしょう。私たちの部門では、CLRSのテキストから教えています。

于 2010-01-20T02:58:06.447 に答える
1

素朴な方法を使用しないでください。階乗を計算する必要がある場合は、高速アルゴリズムを使用してください: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

于 2010-01-20T01:09:20.033 に答える
0

「大きな数」のパッケージが必要です。使用するパッケージか、自分で作成するパッケージのいずれかです。

「多数のアルゴリズム」について調査することをお勧めします。JavaのBigDecimalに相当するC++を実装する必要があります。

それを見る別の方法は、ガンマ関数を使用することです。正しい答えを得るために、これらすべての値を乗算する必要はありません。

于 2010-01-20T00:50:23.210 に答える
0

まず、数値を std::vector (配列内の各位置の数字) のようなある種の配列に格納する必要があり、階乗を計算する特定のアルゴリズムを見つける必要があります (おそらく何らかの種類の専門クラス）。;)

于 2010-01-20T00:47:26.700 に答える