Editorial for ptit001: Vẽ hình chữ nhật đặc

Hiểu bài toán

Bài toán yêu cầu in ra một hình vuông đặc có độ dài cạnh là n. Hình vuông này được tạo thành từ các ký tự dấu sao (''). Nói cách khác, với đầu vào là một số nguyên dương n (2 ≤ n ≤ 100), người dùng cần xuất ra n dòng, mỗi dòng chứa n ký tự '', để tạo thành một khối hình vuông đặc.

Các cách tiếp cận

Cách Vòng lặp lồng (Nested Loops)

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)  {
            printf("*");
        }
        printf("\n");
    }
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Ta sử dụng hai vòng lặp lồng nhau. Vòng lặp ngoài (biến i) chạy từ 0 đến n-1 để duyệt qua từng hàng của hình vuông. Trong mỗi lần chạy của vòng lặp ngoài, vòng lặp trong (biến j) chạy từ 0 đến n-1 để in ra n ký tự '*' trên một hàng. Sau khi in xong một hàng (hoàn thành vòng lặp trong), ta in một ký tự xuống dòng ('\n') để chuyển sang hàng tiếp theo. Quá trình này lặp lại n lần, tạo ra n hàng, mỗi hàng n ký tự.

Cách Tạo chuỗi kí tự

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);

    // Tạo một hàng mẫu gồm n dấu sao
    char row[101]; // Đủ để chứa 100 dấu sao và ký tự kết thúc
    for(int i = 0; i < n; i++) {
        row[i] = '*';
    }
    row[n] = '\0';

    // In hàng mẫu đó n lần
    for(int i = 0; i < n; i++) {
        printf("%s\n", row);
    }

    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Phương pháp này tạo ra một chuỗi đại diện cho một hàng của hình vuông trước. Ta cấp phát một mảng ký tự, gán '*' cho n phần tử đầu tiên và thêm ký tự kết thúc chuỗi '\0'. Sau đó, ta chỉ cần in chuỗi này ra màn hình kèm theo ký tự xuống dòng, và lặp lại thao tác này n lần. Cách này về mặt lý thuyết vẫn có độ phức tạp thời gian O(n^2) do phải in n ký tự cho mỗi dòng trong n dòng, nhưng nó tách biệt việc tạo nội dung hàng với việc lặp hàng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề có thể được chia thành hai phần: tạo nội dung của một hàng (n dấu sao) và lặp lại thao tác in hàng đó n lần.
• Sử dụng vòng lặp lồng là cách hiệu quả và phổ biến nhất để giải quyết các bài toán in hình dạng học trên ma trận.

Lỗi thường gặp

• Quên ký tự xuống dòng '\n' ở cuối mỗi hàng sẽ khiến toàn bộ输出 nằm trên một dòng duy nhất.
• Lỗi off-by-one: vòng lặp phải chạy đúng n lần (từ 0 đến n-1 hoặc 1 đến n) để đảm bảo số hàng và số cột chính xác.