C++を使用してN回移動した後の三角形の数を見つける

記事では、最初に、色付きの三角形を描画する必要があります。色のない三角形を取り、三角形を4つの小さな等辺に分割する必要があります。同じ面積の三角形をn番目のステップまで続けて、図に存在する正三角形の数を見つけます。

解決策を見つけるためのアプローチ

このソリューションには2つのアプローチがあり、それらは-

ブルートフォースアプローチ

三角形の数は、ステップごとにいくらか増加し続ける（3 * previous_number + 2ずつ増加する）ことがわかります。したがって、nまでループを実行して、三角形の数を計算できます。

例

#include <iostream>
using namespace std;
int main() {
   int n = 2; // number of operations we made
   int count = 1; // at first we have only one triangle
   for(int i = 0; i < n; i++) { // looping till n
      count = 3 * count + 2; // as the triangle count is increasing by 3*prev + 2
   }
   cout <<count << "\n";
}

出力

17

上記のプログラムの時間計算量はO（N）です。ここで、Nは実行された操作の数です。これで、時間計算量をさらに改善できます。これは、より高い制約に対処するときに非常に役立ちます。

効率的なアプローチ

このアプローチでは、答えを計算する式を作成します。

例

#include <bits/stdc++.h>
using namespace std;
int main() {
   int n = 2; // number of operations we made
   int count;
   count = 2 * (pow(3, n)) - 1; // the total number of triangles after nth move
   cout << count << "\n";
}

出力

17

上記のコードの時間計算量はO（log（N））です。ここで、Nは実行した移動の数です。

上記のコードの説明

与えられたプログラムでは、与えられた手順を解くための式を作成し、式に必要な値を入れて、結果を出力するだけです。

結論

この記事では、いくつかの観測といくつかの数学を適用して、Nが移動した後の三角形の数を見つけます。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。

同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。