Editorial for ptit055: Bảng cửu chương

Hiểu bài toán

Bài toán yêu cầu in ra bảng cửu chương cho một số n cho trước, bao gồm 31 dòng tương ứng với các phép nhân từ n x 0 đến n x 30. Dữ liệu đầu vào là một số nguyên n (0 ≤ n ≤ 10^8). Đầu ra cần định dạng đúng theo mẫu 'n x i = kết quả' cho mỗi dòng.

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

Cách Vòng lặp cơ bản với kiểu dữ liệu long long

#include<stdio.h>
#define ll long long

int main(){
    ll n;
    scanf("%lld",&n);
    for (ll i = 0; i <= 30; i++){
        printf("%lld x %lld = %lld\n",n,i,n*i);
    }
    return 0;
}

• Time Complexity: O(1) (vì số lần lặp cố định là 31)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Sử dụng kiểu dữ liệu long long để đảm bảo không bị tràn số khi n nhân với 30 (n ≤ 10^8, nên n30 ≤ 310^9, nằm trong giới hạn của long long). Vòng lặp for chạy từ 0 đến 30 để in ra tất cả các phép nhân.

Cách Vòng lặp với kiểu dữ liệu int

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

#define ll long long

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<=30;i++){
        printf("%d x %d = %lld\n",n,i,n*i);
    }
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng kiểu int cho n. Tuy nhiên, khi in kết quả ni, nó được ép kiểu ngầm sang long long (do printf với format %lld). Điều này có thể gây lỗi nếu n rất lớn (gần 10^8) vì ni có thể vượt quá giới hạn của int nếu tính toán trên kiểu int.

Cách Vòng lặp với biến toàn cục

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

• Time Complexity: O(1)
• Space Complexity: O(1)

Sử dụng biến toàn cục i cho vòng lặp. Kiểu dữ liệu long long cho n để đảm bảo an toàn số. Đây chỉ là biến thể về cách khai báo biến, logic tính toán tương tự như cách 1.

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

Bài học kinh nghiệm

• Kiểu dữ liệu long long là cần thiết để tránh tràn số khi tính toán n * 30 với n lên tới 10^8.
• Số lần lặp là cố định (31 lần), do đó độ phức tạp thời gian là hằng số O(1).

Lỗi thường gặp

• Sử dụng kiểu int cho biến kết quả n*i có thể gây lỗi tràn số nếu n lớn.
• Quên xuống dòng '\n' ở cuối mỗi dòng in sẽ gây sai định dạng đầu ra.