C++でN回の操作後に存在する正三角形の数を求める方法

この記事では、色付きの三角形を描き、その中に存在する正三角形の数を求める方法を解説します。まず無色の三角形を用意し、それを4つの同じ面積を持つ小さな正三角形に分割します。この操作をn回繰り返し、最終的な図形の中にいくつの正三角形が存在するかを求めます。

解決策へのアプローチ

この問題を解くには、主に2つのアプローチがあります。

総当たり（ブルートフォース）アプローチ

観察すると、各ステップごとに三角形の数は「3 × 前回の数 + 2」という規則で増加していくことがわかります。したがって、n回ループを回すことで三角形の数を順次計算できます。

コード例

#include <iostream>
using namespace std;
int main() {
    int n = 2; // 実行した操作の回数
    int count = 1; // 最初は三角形が1つだけ
    for(int i = 0; i < n; i++) { // n回ループ
        count = 3 * count + 2; // 三角形の数は 3*prev + 2 ずつ増加
    }
    cout << count << "\n";
}

出力

17

上記プログラムの時間計算量はO(N)です。ここでNは実行された操作の回数を表します。より大きな制約値を扱う場合に備えて、時間計算量をさらに改善することが可能です。

効率的なアプローチ

このアプローチでは、答えを直接計算できる公式を作成します。漸化式「a(n) = 3 × a(n−1) + 2」（初項 a(0) = 1）を数学的に解くことで、n回の操作後の三角形の総数は「2 × 3ⁿ − 1」で表されることが導けます。

コード例

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 2; // 実行した操作の回数
    int count;
    count = 2 * (pow(3, n)) - 1; // n回目の操作後の三角形の総数
    cout << count << "\n";
}

出力

17

上記のコードの時間計算量はO(log(N))です。ここでNは実行した操作の回数です。累乗計算にlog(N)の計算量がかかるため、総当たり法よりも高速に動作します。

コードの解説

このプログラムでは、与えられた手順を解くための公式を作成し、必要な値を公式に代入して結果を出力しています。ループ処理が不要になるため、Nが非常に大きい場合でも効率的に答えを求められます。

まとめ

この記事では、観察と数学を応用して、N回の操作後の三角形の数を求めました。また、この問題に対するC++プログラムと、通常のアプローチ（O(N)）および効率的なアプローチ（O(log(N))）という2つの解法についても学びました。

同じプログラムは、C、Java、Pythonなどの他の言語でも記述できます。この記事が皆さんのお役に立てば幸いです。