🧩

【Java】階乗

に公開
Java
アルゴリズムとデータ構造
factorial
再帰的アルゴリズム
purmutation
tech

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

この記事は再帰的アルゴリズムについてまとめました。

基本用語確認

アルゴリズム

問題を解くためのものであって、明確に定義され、順序付けられた有限個の規則からなる集合。
（「JIS X0001」より。JISとは日本産業規格のこと。）

再帰的

『ある定義の中で、自分自身の定義を使うことを再帰的(recursive)という。』
(増原英彦氏の「計算機プログラミングⅠ(11) 再帰」より引用(2025.5.10時点))

再帰的なメソッド定義

『あるメソッド定義の中で、そのメソッド自信を呼び出しているようなものを再帰的(recursive)メソッド定義という。』
(増原英彦氏の「計算機プログラミングⅠ(11) 再帰」より引用(2025.5.10時点))

帰納的なメソッド呼出

『あるメソッド定義の中で、そのメソッド自身を呼び出すこと』
(増原英彦氏の「計算機プログラミングⅠ(11) 再帰」より引用(2025.5.10時点))

階乗

正の整数nに対して以下の式をnの階乗(factorial)といい、n!と表す。

n! = n \times (n - 1) \times \cdots \times 3 \times 2 \times 1

順列

正の整数n, kに対して、異なるn個のものから重複せずに異なるk個のものを取り出して1列に並べることを、「n個のものからk個とる順列(permutation)」といい、{}_n P_kと表す。{}_n P_kは以下のように定める。

{}_n P_k = n \times (n - 1) \times (n - 2) \times \cdots \times (n - (k - 1))

階乗

階乗の実装

再帰的なメソッド定義による階乗の実装は次の通り。

//--- 非負の整数値nの階乗値を返却 ---//
static int factorial(int n) {
  if (n > 0)                      // ①
    return n * factorial(n - 1);  // ②
  else
    return 1;                     // ③
}

アルゴリズムのイメージ図

n=3のとき

つまり

階乗の利用例

import java.util.Scanner;

public class Factorial {
	
  //--- 非負の整数値nの階乗値を返却 ---//
  static int factorial(int n) {
    if (n > 0)                      // ①
      return n * factorial(n - 1);  // ②
    else
      return 1;                     // ③
  }
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);

    System.out.println("【階乗値を求める】");
    System.out.print("整数を入力せよ：");
    int x = stdIn.nextInt();
    
    System.out.println(x + "の階乗は" + factorial(x) + "です。");
  }
}

実行結果

【階乗値を求める】
整数を入力せよ：3
3の階乗は6です。

おまけ

順列の実装と利用例

順列(permutation){}_n P_kを求めるメソッドを作ってみます。メソッド定義は上記の階乗のものを少し改修したものです。

import java.util.Scanner;

public class Permutation {

  //--- 非負の整数値nの順列値を返却 ---//
  static int permutation(int n, int k) {
    if (n > k)                          // ①
      return n * permutation(n - 1, k); // ②
    else
      return k;                         // ③
  }
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    
    System.out.println("【順列P(n, k)を求める】");
    System.out.print("整数nを入力せよ：");
    int x = stdIn.nextInt();
    System.out.print("整数kを入力せよ：");
    int y = stdIn.nextInt();
    
    System.out.println(x + "の順序は" + permutation(x, y) + "です。");
  }
}

実行結果

※実行文に表示されているP(n, k)は{}_n P_kのことを表す。

【順列P(n, k)を求める】
整数nを入力せよ：5
整数kを入力せよ：3
5の順序は60です。

\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}
ご協力のほどよろしくお願いします。

Discussion