nの階乗の末尾0の数がいくつになるかを計算するプログラム (Java)

新人時代に会社のコンテストで出題された問題の回答がBitbucketに残っていたのを見つけたので、当時を思い出しながら解説してみます。
もう7年前くらいの古いものなので、あんまり面白味もないですが。。

問題

1~nの整数をすべてかけていった時の末尾の0の数を計算してください (0<n<=1000)
(例) 1~5の場合
1×2×3×4×5 = 120 だから、0は末尾に1つ

回答しか残ってなかったのですが、多分問題はこんな感じだったと思います。
要するに、整数nの階乗(n!)の末尾に0がいくつくっついているかを出力させるプログラムを書けば良いってことです。

考察

階乗の計算は、

n! = 1×2×3×…×(n-2)×(n-1)×n

になるので、1~nまでを1つずつインクリメントしてかけていけばいいじゃん!と思うのですが、nの最大が1000なので、JavaだとLongでもオーバーフローしそうな雰囲気です。
実は問題の「末尾の0の数」というのがミソで、末尾の0の数が増える条件を考えれば良かったりします。

末尾の0が増える = 桁が上がる = ×10される = ×2×5される と考えられます。
また、常に ×2の数 > ×5の数 となるので、数えるのは ×5の数だけで良さそうです。

解答

というわけで、ソースコードは以下のようになりました。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	// ゼロの個数をカウントする
	private static int cntZero = 0;
	
	// 5で割りきれるかチェック
	private static void dividedFive(int value) {
		if (value % 5 == 0) {
			cntZero++;
			dividedFive(value /= 5);
		}
		return;
	}
	
	// 入力メソッド
	private static String scanf() {
		String str = null;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			str = br.readLine();
		} catch (IOException ioe) {
			System.err.println("入出力エラー" + ioe.getMessage());
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException ioe) {
				ioe.printStackTrace();
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		return str;
	}
	
	public static void main(String[] args) {
		long inputLong = 0;
		
		System.out.println("正の整数を入力してください");

		try {
			inputLong = Integer.parseInt(scanf());
			
			if (inputLong < 0) {
				System.out.println("入力された値が無効です");
				System.out.println("理由:有効範囲外です");
				return;
			}
		} catch (NumberFormatException nfe) {
			System.out.println("入力された値が無効です");
			System.out.println("理由:数値以外が入力されました");
			return;
		} catch (Exception e) {
			e.printStackTrace();
		}
		
		// 2~inputIntまでの数をループ
		for (int cnt = 2; cnt <= inputLong; cnt++) {
			dividedFive(cnt);
		}
		
		System.out.println(inputLong + "の階乗の末尾0の数は");
		System.out.println(cntZero + "個です");
	}	
}

色々ツッコミどころがありますが、新人時代の産物なんでまあいいかって感じではあります。

タイトルとURLをコピーしました