AOJ 0019 Factorial

問題概要

n!を求めよ。

制約

• 1 ≤ n ≤ 20

解法

n! = n × n-1 × ... × 2 × 1
であるので、それを計算すれば良い。

計算方法には、ループで書く方法と再帰関数で書く方法がある。

• ループ

fact = 1;
for (int i = 1; i <= n; i++) {
    fact *= i;  // fact = fact * i; と同じ
}

• 再帰関数

fact(i)をiの階乗と定義すると以下のような漸化式が導ける。

1. fact(i) = 1 (i ≤ 1)
2. fact(i) = i × fact(i-1) (i > 1)

よって、以下のように再帰関数を書くことができる。

int fact(x)
{
    if (x <= 1) return x;
    return x * fact(x - 1);
}

注意点として、この問題では、最大n = 20であり、20!はint型の範囲を超えてしまうので、long long型などを使用する必要がある。

コード

#include <iostream>

using namespace std;

int main()
{
    int n;
    long long result = 1;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

using namespace std;

long long fact(long long n)
{
    if (n <= 1) return 1;
    return fact(n - 1) * n;
}

int main()
{
    int n;
    cin >> n;
    cout << fact(n) << endl;
    return 0;
}