Hướng dẫn giải của Cây thông Noel
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Xây dựng hình cây thông Noel 3 tầng theo quy tắc:
- Tầng 1: Cao n dòng, mỗi dòng i (từ 0) có 2*i+1 ký tự, gồm lá 'x' ở giữa và 2 đèn LED '#' ở 2 đầu. Cạnh hình tam giác.
- Tầng 2: Cao n+1 dòng, tương tự.
- Tầng 3: Cao n+2 dòng, tương tự.
- Toàn bộ cây được đặt trong một khung hình chữ nhật. Các vị trí còn lại (xung quanh cây) được lấp đầy bằng dấu '.'.
- Chiều rộng của khung hình được xác định bởi dòng cuối cùng của tầng 3 (dòng thứ n+1 của tầng đó): độ rộng là 2*(n+2)-1 = 2n+3.
Các cách tiếp cận
Cách Dựa vào hàng và cột (Math & Logic)
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
// Chiều cao của mỗi tầng
int h1 = n;
int h2 = n + 1;
int h3 = n + 2;
// Chiều rộng tối đa (từ dòng cuối cùng của tầng 3)
int width = 2 * (n + 2) - 1;
int mid = width / 2;
int current_row = 0;
int total_rows = h1 + h2 + h3;
for (int i = 0; i < total_rows; ++i) {
// Xác định xem dòng i thuộc tầng nào
int h = 0;
int start_h = 0;
if (i < h1) {
h = i; // Dòng thứ h của tầng 1 (từ 0)
start_h = 0;
} else if (i < h1 + h2) {
h = i - h1; // Dòng thứ h của tầng 2
start_h = 0;
} else {
h = i - h1 - h2; // Dòng thứ h của tầng 3
start_h = 0;
}
// Khoảng cách lề
int space = mid - h;
// Chiều dài phần bên trong (x và #)
int inner_len = 2 * h + 1;
// In ra các dấu chấm (lề)
for (int j = 0; j < space; ++j) cout << ".";
// In ra các ký tự của cây
for (int j = 0; j < inner_len; ++j) {
if (j == 0 || j == inner_len - 1) cout << "#";
else cout << "x";
}
// In ra các dấu chấm (lề)
for (int j = 0; j < space; ++j) cout << ".";
cout << endl;
}
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(1)
Phương pháp này phân tích từng dòng của cây thông. Biến i là chỉ số dòng toàn cục. Ta xác định dòng i thuộc về tầng nào và là dòng thứ bao nhiêu trong tầng đó (biến h). Dựa vào h, ta tính được số lượng dấu '.' ở lề (space = mid - h) và số lượng ký tự bên trong (inner_len = 2*h + 1). Vòng lặp in ra các ký tự tương ứng: 2 đầu là '#' và phần còn lại là 'x'. Cách này xử lý tuần tự từng dòng một cách trực quan và không cần lưu trữ ma trận.
Cách Hàm tái sử dụng (Refactoring)
#include <iostream>
using namespace std;
// Hàm in ra một tầng của cây thông
// lines: số dòng của tầng đó
// width: chiều rộng khung hình
void printTier(int lines, int width) {
int mid = width / 2;
for (int i = 0; i < lines; ++i) {
int space = mid - i;
int inner_len = 2 * i + 1;
// In lề trái
for (int j = 0; j < space; ++j) cout << ".";
// In bên trong
if (inner_len == 1) {
cout << "#";
} else {
cout << "#";
for (int k = 0; k < inner_len - 2; ++k) cout << "x";
cout << "#";
}
// In lề phải
for (int j = 0; j < space; ++j) cout << ".";
cout << endl;
}
}
int main() {
int n;
cin >> n;
int width = 2 * (n + 2) - 1;
printTier(n, width); // Tầng 1
printTier(n + 1, width); // Tầng 2
printTier(n + 2, width); // Tầng 3
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(1)
Cách tiếp cận này nhận thấy rằng cả 3 tầng đều tuân theo cùng một quy tắc hình học (hình tam giác). Điểm khác biệt duy nhất là số lượng dòng. Do đó, ta tách logic in một tầng ra thành một hàm printTier riêng. Hàm này nhận vào số dòng và chiều rộng cố định của khung. main chỉ cần gọi hàm này 3 lần với số dòng tương ứng (n, n+1, n+2).
Cách Ma trận ký tự (Matrix/Grid)
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
int h = 2 * (n + 2) - 2; // Chiều cao (số dòng - 1)
int w = 2 * (n + 2) - 1; // Chiều rộng
int mid = w / 2;
// Khởi tạo ma trận rỗng
vector<string> grid(h + 1, string(w, '.'));
// Vẽ 3 tam giác
int current_row = 0;
for (int t = 0; t < 3; t++) {
int height = n + t;
for (int i = 0; i < height; i++) {
int left = mid - i;
int right = mid + i;
grid[current_row][left] = '#';
grid[current_row][right] = '#';
for (int j = left + 1; j < right; j++) {
grid[current_row][j] = 'x';
}
current_row++;
}
}
// In ma trận
for (int i = 0; i <= h; i++) {
cout << grid[i] << endl;
}
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Phương pháp này tạo một ma trận ký tự (vector of strings) có kích thước cố định và lấp đầy bằng '.' trước. Sau đó, ta duyệt qua từng dòng của từng tầng, tính toán vị trí của '#' và 'x' trong ma trận và ghi vào. Cuối cùng, in ra ma trận. Cách này rõ ràng về mặt cấu trúc dữ liệu nhưng tốn bộ nhớ hơn so với các cách in trực tiếp.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2) | O(1) | Dựa vào hàng và cột (Math & Logic) |
| 2 | O(n^2) | O(1) | Hàm tái sử dụng (Refactoring) |
| 3 | O(n^2) | O(n^2) | Ma trận ký tự (Matrix/Grid) |
Bài học kinh nghiệm
- Chiều rộng khung hình được quyết định bởi dòng dưới cùng của tầng 3, có công thức: 2*(n+2)-1.
- Mỗi dòng trong một tầng có dạng hình tam giác cân. Nếu dùng chỉ số dòng
i(từ 0), số lượng ký tự 'x' là2*i - 1(với i>0), và vị trí 2 đầu '#' nằm ở khoảng cáchitừ lề (hoặc từ trục). - Tất cả các dòng đều có cùng độ dài (bằng chiều rộng khung hình), các khoảng trống được lấp bằng dấu '.'.
Lỗi thường gặp
- Lầm tưởng về độ rộng của các tầng: Tầng 1 chỉ rộng tối đa 2*n-1, nhưng khi in ra phải đặt trong khung to hơn (2n+3). Nếu in từng tầng riêng lẻ mà không canh lề, cây sẽ bị lệch.
- Sai sót khi tính toán vị trí in 'x': Cần đảm bảo in đúng số lượng 'x' ở giữa 2 dấu '#'. Ví dụ dòng đầu tiên (i=0) chỉ có 1 ký tự '#' và không có 'x'.
- Quên in các ký tự '.' ở lề phải.
Bình luận