C++ Tìm số tam giác sau N bước chia

Bắt đầu với một tam giác đều. Mỗi bước, chia mỗi tam giác thành 4 tam giác đều nhỏ hơn cùng diện tích. Lặp lại n bước. Tìm tổng số tam giác đều trong hình cuối cùng.

Các phương pháp giải

Phương pháp vét cạn

Quan sát số tam giác tăng theo quy tắc: count = 3 × count_trước + 2. Chạy vòng lặp n lần.

Ví dụ

#include <iostream>
using namespace std;

int main() {
    int n = 2;
    int count = 1;
    for (int i = 0; i < n; i++)
        count = 3 * count + 2;
    cout << count << "\n";
}

Kết quả

17

Độ phức tạp: O(N).

Phương pháp hiệu quả (Công thức đóng)

Suy ra công thức: số tam giác = 2 × 3ⁿ - 1.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 2;
    int count = 2 * pow(3, n) - 1;
    cout << count << "\n";
}

Kết quả

17

Độ phức tạp: O(log N) do hàm pow.

Kết luận

Đã tìm số tam giác sau N bước chia bằng quan sát quy luật và suy ra công thức toán học. Chương trình C++ có thể chuyển sang các ngôn ngữ khác. Hy vọng hữu ích.