AtCoder が提供しているABC（AtCoder Beginner Contest）273 のA問題をC++とPythonで解いてみました。ABC273は、2022年10月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
A問題 A Recursive Function（Difficulty : 11）
問題はリンク先をご覧ください。
ABC273 A問題 A Recursive Function
漸化式から関数を値を求める問題です。AtCoder Problems による Difficulty は、11 でした。
解答案
問題を解く方針を書きだします。
- 整数を読み、再帰によって関数の値を求める。
もしくは、
- 整数を読み、一般項から関数の値を求める。
C++ プログラム例（ABC273A）
問題で与えられた漸化式を関数として実装します。問題と同じ f という名前の関数を定義して、関数内で再帰呼び出しをしています。
#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
if (n == 0) {
return 1;
} else {
return n * f(n - 1);
}
}
int main()
{
int n;
cin >> n;
cout << f(n) << endl;
return 0;
}再帰呼び出しする関数は工夫しないと、計算時間やメモリ使用量が爆発的に大きくなる場合があります。今回は、制約で $0 \leqq N \leqq 10$ と指定されていたため、そのまま実装しました。
次に一般項から関数の値を求めてみましょう。こちらの方が自然かもしれません。
問題に与えられた漸化式から、$f(n) = n \times (n – 1) \times \cdots \times 2 \times 1 = n!$ と分かります。この一般項から値を求めるプログラムは以下となります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int result = 1;
for (int i = 1; i <= n; ++i) {
result *= i;
}
cout << result << endl;
return 0;
}どちらも、AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC273A）
Python でも、2種類のプログラムを紹介します。まずは、漸化式を再帰呼び出しする関数として実装します。
Python の代表的なコーディングガイドライン PEP 8（日本語版）で、関数の前後は空白行を2行空けるべきという記述があるため、関数 f の前後は2行の空行を入れています。
"""AtCoder Beginner Contest 273 A"""
def f(n):
return 1 if n == 0 else n * f(n - 1)
n = int(input())
print(f(n))次に、一般項は階乗です。こちらはライブラリ関数を呼び出すことにします。
"""AtCoder Beginner Contest 273 A"""
import math
n = int(input())
print(math.factorial(n))どちらも「AC」と判定されました。
最後に
問題に示された漸化式から計算する場合と一般項を求めて計算する場合を紹介しました。一般項が分かっているなら、一般項を使う方が、ほとんどの場合で計算量が少なくなります。
引き続き ABC の問題を紹介していきます。
