第12回【Python】階乗の計算、階乗の末尾に 0 はいくつ付く？

2023年1月14日

現在取り組んでいるのは、paiza ラーニング問題集「ループメニュー 2」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 12 回目です。

自分の誕生日が 12 月 12 日なので、12 という数字が好きです。鈴木尚、その前だと村田善ですかね。しかし、なぜか、呂明賜の記憶が強い。クロマティの代わりに出てきて打ちまくっていた印象。外国人選手枠が今と同じ 4 人だったら・・・あぁ、野球の話は尽きない。

それでは、今日も頑張ってみようと思います。

階乗の計算

N の階乗、要は、N×(N-1)×(N-2)×・・・×1 なので、5 の階乗であれば、5×4×3×2×1=120 を求めろ、ということですか。

Python

N = int(input())
def factorial(n):
    if n > 0:
        return n * factorial(n-1)
    return 1
print(factorial(N))

当然の如く、再帰関数で求めたわけですが、別に for 文でもよかったですよね。

Python

N = int(input())
factorial = 1
for n in range(1,N+1):
    factorial *= n
print(factorial)

もちろん、while 文でも書けるはず。

Python

N = int(input())
factorial = 1
while N > 0:
    factorial *= N
    N -= 1
print(factorial)

再帰関数の思い込みが強くて、for 文や while 文がすぐに出てこなかった。

では、VBA にするとどうなるか。

VBA

Sub main()
    N = Cells(1, 1)
    Debug.Print factorial(N)
End Sub
Function factorial(N) As Long

    If N > 0 Then
        factorial = N * factorial(N - 1)
    Else
        factorial = 1
    End If
End Function

もちろん、for 文でも書けるはず。

VBA

N = Cells(1, 1)
factorial = 1
For i = 1 To N
    factorial = factorial * i
Next
Debug.Print factorial

while 文（Do Loop 文）でも挑戦しておこう。

VBA

N = Cells(1, 1)
factorial = 1
Do While N > 0
    factorial = factorial * N
    N = N - 1
Loop
Debug.Print factorial

VBA を学習し始めた頃の再帰関数に関するテーマとして、階乗計算が用いられやすかったからだろうか。階乗計算は再帰関数にする、って思ってたなぁ。思い込みは捨てるべし。

階乗の末尾に 0 はいくつ付く？

いちいち N の階乗を求めてゼロを数える、ってことはナンセンスでしょうねぇ。数が大きくなりすぎて、メモリがいっぱいいっぱいになっちゃいそう。

ただし、Python が扱うことができる整数の桁数は無制限（システムメモリに依る）だそうですよ。

中学生の頃に解き方を習った気がします。素因数分解の授業で。記憶があやふやなので、ネットで調べました。5 で割った解を足し算していけばいい、らしい。

Python

N = int(input())
cnt = 0
while N > 0:
    cnt += N // 5
    N //= 5
print(cnt)

先ほど作った階乗のプログラムと合わせて演算してみましたが、間違いないようです。

VBA でもやってみます。エクセルで利用可能な桁数は 15 桁。階乗の計算をしてからゼロの数を数えるのは難しそう。

VBA

N = Cells(1, 1)
cnt = 0
Do While N > 0
    cnt = cnt + Int(N / 5)
    N = Int(N / 5)
Loop
Debug.Print cnt

「50」で階乗の計算をしてみたら「3.04140932017134E+64」の結果が返ってきます。こういう工夫は必要ですね。

最後に

確認のために素因数分解をします。紙と鉛筆を用意して。

いやー、久しぶりにやりました。

「50」の階乗を Python で求めた後に、5 で割って、5 で割って、5 で割って、5 で割って、・・・素因数分解のプログラムを作成するのと、手計算するのとどっちが早いだろうと悩みながら。多分、手計算の方が早いんでしょうけど。

知らないと解くことができない問題って好きだなぁ。こういう知識が増えれば、次の新しい問題に応用することができるようになるし。

引き続き、お付き合いよろしくお願いいたします！