読者です 読者をやめる 読者になる 読者になる

kei0425tan’s blog

技術的なことを主に

POH7「プログラミングで彼女をつくる」「水着」ゲットチャレンジ!

プログラミング Scala paiza

POH8の問題を全部解いてしまったので、昔のにも挑戦してみます。

paiza.jp

問題

階乗とは数学の演算の一つで、N の階乗をN! と書きます。N が自然数であるとき、階乗は次のように計算できます。

N! = N * (N - 1) * ... * 2 * 1


N が与えられたとき、N! のすべての桁の代わりに、N! の最下位桁から続く0 をすべて除いた値の下位9桁を求めるプログラムを作成してください。
9桁ではあるが先頭が0であるような場合は先頭の0を取り除いた値を出力してください。先頭に0のついた値を出力すると誤答となります。
例えば N = 38 の時は以下のようになります。

f:id:kei0425tan:20160707141134p:plain

条件

すべてのテストケースにおいて、以下の条件をみたします。

1 ≦ N ≦ 1000000

入力例1

入力
15

出力
307674368

入力例2

入力
10

出力
36288

ちょっと見、ただ単に階乗を求めて、ちょこちょこっと条件に合うように変更するだけにみえますが、実はトラップが何個も仕掛けてありました。
2つの入力例だけの場合は、上記の通り何も考えずにトラップに引っかからずに通ってしまいます。

トラップ1

整数型では単に階乗を求めてしまうとかなり早い段階でオーバーフローを起こしてしまいます。
LL言語で動的型で解こうとしても、JavaScriptなどは内部で浮動小数点型に変換されてしまうため、正確な値がでなくなります。

トラップ2

入力範囲が1000000まで。そのため、何も考えずに再帰で書いてしまうとほぼスタックオーバーフローになります。

トラップ3

トラップ1にかからないように、巨大な値になる前に、常に下の0を削除して9桁で計算してしまおう。と思っていると引っかかります。
5の倍数をかけると実質割り算になるので、途中が9桁しかないと答えが合いません。

以上を踏まえて、scalaで解いてみました。
scalaの理由は末尾再帰最適化があるから!