C++를 사용하여 N 이동 후 삼각형의 수 찾기

n 기사, 먼저 컬러 삼각형을 그려야 합니다. 색칠하지 않은 삼각형을 가져와 삼각형을 4개의 작은 정삼각형으로 나눌 필요가 있습니다. 같은 넓이의 삼각형을 n단계까지 계속해서 그림에 있는 정삼각형의 개수를 구하세요.

해결책을 찾기 위한 접근 방식

이 솔루션에는 두 가지 접근 방식이 있으며 다음과 같습니다.

무차별 대입 접근

우리는 삼각형의 수가 모든 단계 후에 일정 수만큼 계속 증가하는 것을 관찰할 수 있습니다(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++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(Normal 및 Efficiency)을 배웠습니다.

C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.