n bài báo, đầu tiên, chúng ta phải vẽ một tam giác màu. Chúng ta cần lấy một tam giác không có màu và chia tam giác thành bốn cạnh nhỏ bằng nhau. Các tam giác có cùng diện tích và tiếp tục làm đến bước thứ n và tìm số tam giác đều có trong hình.
Phương pháp tiếp cận để tìm ra giải pháp
Có hai Cách tiếp cận cho Giải pháp này và chúng -
Phương pháp tiếp cận vũ phu
Chúng ta có thể quan sát thấy rằng số lượng tam giác tiếp tục tăng lên một số nào đó (tăng 3 * số_trước + 2) sau mỗi bước. Vì vậy, chúng ta có thể chạy một vòng cho đến n và tính số hình tam giác.
Ví dụ
#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";
} Đầu ra
17
Độ phức tạp về thời gian của chương trình trên là O (N), trong đó N là số hoạt động được thực hiện. Giờ đây, chúng tôi có thể cải thiện hơn nữa độ phức tạp về thời gian của nó, điều này sẽ rất hữu ích khi chúng tôi xử lý các ràng buộc cao hơn.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ đưa ra một công thức tính toán câu trả lời cho chúng tôi.
Ví dụ
#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";
} Đầu ra
17
Đoạn mã trên có độ phức tạp về thời gian là O (log (N)), trong đó N là số lần di chuyển chúng tôi đã thực hiện.
Giải thích về đoạn mã trên
Trong chương trình đã cho, chúng tôi chỉ đơn giản là tạo ra một công thức để giải quyết thủ tục đã cho của chúng tôi và đưa các giá trị cần thiết vào công thức và in ra kết quả.
Kết luận
Bài này tìm số tam giác sau khi N di chuyển bằng cách áp dụng một số quan sát và một số phép toán. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này.
Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. chúng tôi hy vọng bạn thấy bài viết này hữu ích.