[至急] Project Euler: #20 Factorial digit sum コード、入力、出力、解説 アルゴリズムとデータ構造 #13 - #19を教えて!gooで解答せよ。

Question

#13 - #19を教えて!gooで解答せよ。
https://oshiete.goo.ne.jp/articles/qa/2834
https://web.archive.org/web/20220923175516/https://oshiete.goo.ne.jp/articles/qa/2834

---

https://projecteuler.net/problem=20

n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

結論からお伝えすると、答えを教えてください。C,C++,javaのどれかで。
コードと入力と出力とできれば解説もお願いします。
プログラミング未経験でも簡単に理解できるように説明してほしい。

私の考え
オーバーフローが発生する。

Comments

[thkana]

> 教えて!gooで
マルチポストの理由を記載してください。(するわけないと思いながら言っているけれど)

> 解答せよ。
何様でしょう?

[episteme]

答えは 648 か。(検算にお使いください)

> オーバーフローが発生する。

オーバーフローしない(多桁の)掛け算ルーチンを書けばいいんでしょ。
そんなに難しくないでしょ。筆算でのアルゴリズムをコードに落とせばいいんだから。

[退会済みユーザー]

@thkana
これはマルチポストではない。
私は#13 - #19を教えて!gooのみに投稿した。

@episteme
Cなどはチューリング完全でありながら、そのルーチンを記述することが非常に難しい設計となっている。

[episteme]

> Cなどはチューリング完全でありながら、そのルーチンを記述することが非常に難しい設計となっている。

...だからなに?

[退会済みユーザー]

よって、そのルーチンを記述することが非常に難しい設計となっている。
故に、私はこの問題を解答できない。

[kazuma-s]

100の階乗は 10進で 158桁です。main の中は 5行で書けます。

[退会済みユーザー]

私はオーバーフローが発生する。
よって、この問題はチューリング不完全なコンピュータでは解けない。

[kazuma-s]

そのオーバーフローが発生するコードを質問に追記してください。

[退会済みユーザー]

long long n = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29*30*31*32*33*34*35*36*37*38*39*40*41*42*43*44*45*46*47*48*49*50*51*52*53*54*55*56*57*58*59*60*61*62*63*64*65*66*67*68*69*70*71*72*73*74*75*76*77*78*79*80*81*82*83*84*85*86*87*88*89*90*91*92*93*94*95*96*97*98*99*100;

[退会済みユーザー]

返信が遅すぎる。

[kazuma-s]

int a[160] = { 1 }, c = 0, n, i;
for (n = 2; n <= 100; n++)
　　for (i = 0; i < 160; i++)
　　　　a[i] = a[i] * n + c, c = a[i] / 10, a[i] %= 10;

Answer 1

残念ながら、ここではコードの作成依頼は受け付けていません

まずはあなたなりにコードを書いてみましょう。その上でわからないことを聞いていただければお答えできるかと思います。

Answer 2

退会済みになっているから、解答を書いてももう見ないでしょう。
Java で BigInteger を使えば、100 の階乗でもオーバーフローしません。

import java.math.BigInteger;

class Main {
	public static void main(String[] args) {
		BigInteger ONE = BigInteger.ONE, f = ONE, n;
		for (n = new BigInteger("100"); !n.equals(ONE); n = n.subtract(ONE))
			f = f.multiply(n);
		String s = f.toString();
		int a = 0;
		for (int i = s.length(); --i >= 0; ) a += s.charAt(i) - '0';
		System.out.println(a);
	}
}

Answer 3

https://oshiete.goo.ne.jp/articles/qa/2834 解答してくれるならば、私は喜ぶ。

---

なお、このコメントは私が私の友達に質問し手に入れたコメントである。