Hiểu bài toán

Bài toán yêu cầu đếm số lượng số đối xứng có đúng n chữ số (1 ≤ n ≤ 15). Số đối xứng là số mà khi đọc ngược lại vẫn bằng chính nó. Ví dụ: 121 là số đối xứng 3 chữ số. Với n=1, các số đối xứng là 1,2,...,9 (9 số). Với n=2, các số đối xứng là 11,22,...,99 (9 số).

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

Cách Công thức lặp (Recursive)

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

long long palin(int n)
{
    if(n == 1 || n == 2)
        return 9;
    else
        return 10*palin(n-2);
}

int main()
{
    int x;
    while(scanf("%d", &x) != -1)
    {
        printf("%lld\n", palin(x));
    }
    return 0;
}

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

Phương pháp này dựa trên nhận thấy rằng số lượng số đối xứng có n chữ số gấp 10 lần số lượng số đối xứng có n-2 chữ số. Với n=1 (9 số) và n=2 (9 số), ta có thể tính đệ quy cho các n lớn hơn: F(n) = 10 * F(n-2). Ví dụ: F(3) = 10 * F(1) = 90, F(4) = 10 * F(2) = 90. Tuy nhiên, đệ quy có thể gây tràn stack nếu n rất lớn (trong bài này n ≤ 15 nên an toàn).

Cách Công thức toán học trực tiếp

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
long long solve(int n){
    if (n%2 == 0) return 9 * (long long)pow(10,n/2-1);
    else return 9 * (long long)pow(10,(n-1)/2);
}
int main() {
    int n;
    while (scanf("%d", &n) != EOF){
        printf("%lld\n", solve(n));
    }
    return 0;
}

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

Đây là phương pháp tối ưu nhất. Số đối xứng có n chữ số được xác định bởi nửa đầu của nó (nếu n chẵn) hoặc nửa đầu bao gồm chữ số ở giữa (nếu n lẻ). Chữ số đầu tiên không được là 0. Do đó:

• Nếu n chẵn: Ta có 9 cách chọn chữ số đầu tiên (1-9) và 10^(n/2 - 1) cách chọn các chữ số còn lại trong nửa đầu. Tổng = 9 * 10^(n/2 - 1).
• Nếu n lẻ: Ta có 9 cách chọn chữ số đầu tiên và 10^((n-1)/2) cách chọn các chữ số còn lại trong nửa đầu (bao gồm chữ số ở giữa). Tổng = 9 * 10^((n-1)/2). Công thức này có thể viết gọn là 9 * 10^(floor((n-1)/2)).

Cách Công thức toán học với hàm pow

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int k=(n+1)/2;
        int sum=9*pow(10,k-1);
        printf("%d\n",sum);
    }
}

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

Cách tiếp cận này cũng dựa trên công thức toán học nhưng được viết dưới dạng khác. k=(n+1)/2 chính là ceil(n/2) - độ dài của nửa đầu số đối xứng. Số đối xứng có n chữ số được tạo thành bằng cách chọn nửa đầu (k chữ số) với chữ số đầu tiên khác 0. Do đó có 9 * 10^(k-1) cách. Ví dụ: n=3, k=2, số cách = 9 * 10^1 = 90.

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

Bài học kinh nghiệm

• Một số đối xứng có n chữ số được xác định hoàn toàn bởi nửa đầu của nó (khoảng ceil(n/2) chữ số).
• Chữ số đầu tiên của số đối xứng không được bằng 0, nên có 9 lựa chọn (1-9). Các chữ số còn lại trong nửa đầu có thể là 0-9.
• Số lượng số đối xứng có n chữ số là 9 * 10^(ceil(n/2) - 1) = 9 * 10^(floor((n-1)/2)).

Lỗi thường gặp

• Làm tròn số khi tính toán số mũ lớn, cần sử dụng kiểu dữ liệu phù hợp (long long) và chú ý đến giới hạn của kiểu int.
• Quên trường hợp chữ số đầu tiên không được là 0, dẫn đến việc tính cả các số bắt đầu bằng 0 (không phải số n chữ số chuẩn).
• Tràn số khi tính 10^(n/2) với n lớn, trong bài này n ≤ 15 nên 10^7 (với n=15) nằm trong giới hạn của long long nhưng cần cẩn thận với các bài toán lớn hơn.