Bài 9.3: Số thuận nghịch và phân tích trong C++

Chào mừng các bạn đã quay trở lại với chuỗi bài viết về C++! Hôm nay, chúng ta sẽ cùng khám phá một khái niệm khá thú vị trong toán học ứng dụng vào lập trình: Số thuận nghịch, hay còn gọi là Palindrome Number. Đồng thời, chúng ta sẽ tìm hiểu các kỹ thuật để phân tích một số, tức là trích xuất và xử lý các chữ số tạo nên nó – một kỹ năng nền tảng khi làm việc với các bài toán số học.

Số Thuận Nghịch (Palindrome Number) là gì?

Một số thuận nghịch là một số nguyên mà khi đọc từ trái sang phải cũng cho kết quả giống như khi đọc từ phải sang trái. Nói cách khác, thứ tự các chữ số của nó không thay đổi khi bị đảo ngược.

Ví dụ về số thuận nghịch:

  • 121
  • 3443
  • 9
  • 1001
  • 567765

Ví dụ về số không thuận nghịch:

  • 123 (đảo ngược là 321)
  • 4567 (đảo ngược là 7654)
  • 10 (đảo ngược là 01 hay 1)

Kiểm tra một số có phải là số thuận nghịch hay không là một bài toán cổ điển, thường dùng để rèn luyện kỹ năng thao tác với các chữ số của một số.

Phân Tích Một Số - Trọng Tâm Để Nhận Biết Số Thuận Nghịch

Để biết một số có phải là thuận nghịch hay không, chúng ta cần phải "nhìn" vào các chữ số tạo nên nó. Quá trình "nhìn" này chính là phân tích số đó thành các chữ số thành phần.

Trong C++ và hầu hết các ngôn ngữ lập trình, hai toán tử đóng vai trò cốt lõi trong việc trích xuất chữ số từ một số nguyên là:

  1. Toán tử chia lấy phần dư (%): Khi chia một số nguyên cho 10, phần dư chính là chữ số cuối cùng (chữ số hàng đơn vị) của số đó.

    • Ví dụ: 123 % 10 cho kết quả 3.
    • Ví dụ: 4567 % 10 cho kết quả 7.

  2. Toán tử chia lấy phần nguyên (/): Khi chia một số nguyên cho 10 và lấy phần nguyên, chúng ta sẽ loại bỏ chữ số cuối cùng của số đó.

    • Ví dụ: 123 / 10 cho kết quả 12.
    • Ví dụ: 4567 / 10 cho kết quả 456.

Bằng cách lặp lại hai thao tác này, chúng ta có thể "bóc tách" từng chữ số của một số nguyên từ hàng đơn vị trở đi.

Ví dụ: Trích xuất và in các chữ số

Hãy xem một ví dụ đơn giản về cách dùng % 10 và / 10 để trích xuất và in ra từng chữ số của một số:

#include <iostream>

int main() {
    int number = 54321;
    int temp = number; // Dùng biến tạm để không làm thay đổi số gốc

    cout << "Cac chu so cua so " << number << " (tu cuoi len):" << endl;

    // Vòng lặp chạy cho đến khi số tạm bằng 0
    while (temp > 0) {
        int digit = temp % 10; // Trich xuat chu so cuoi
        cout << digit << " "; // In chu so

        temp /= 10; // Loai bo chu so cuoi
    }

    cout << endl; // Xuong dong

    return 0;
}

Giải thích code:

  • Chúng ta sử dụng một biến temp để sao chép giá trị của number. Điều này quan trọng vì vòng lặp sẽ làm giảm temp cho đến khi nó về 0, chúng ta cần giữ giá trị gốc của number để sau này so sánh hoặc xử lý khác.
  • Vòng lặp while (temp > 0) tiếp tục chừng nào temp còn lớn hơn 0, tức là nó còn ít nhất một chữ số.
  • Trong mỗi lần lặp:
    • temp % 10 lấy chữ số hàng đơn vị hiện tại của temp.
    • cout << digit << " "; in chữ số vừa trích xuất.
    • temp /= 10 loại bỏ chữ số hàng đơn vị khỏi temp, chuẩn bị cho lần lặp kế tiếp (lúc này chữ số hàng chục cũ sẽ trở thành hàng đơn vị mới).
  • Quá trình lặp lại cho đến khi temp trở thành 0, tức là tất cả các chữ số đã được xử lý.

Kết quả chạy code trên sẽ là: 1 2 3 4 5. Như bạn thấy, các chữ số được trích xuất từ phải sang trái (hàng đơn vị, hàng chục, ...).

Kiểm Tra Số Thuận Nghịch Bằng Cách Đảo Ngược Số

Cách phổ biến nhất để kiểm tra một số có phải là số thuận nghịch là tạo ra số đảo ngược của nó và so sánh với số gốc.

Quy trình đảo ngược một số tương tự như quy trình trích xuất chữ số, nhưng chúng ta sẽ "xây dựng" một số mới từ các chữ số đã trích xuất, theo thứ tự ngược lại.

Ví dụ: Đảo ngược một số
#include <iostream>

int main() {
    int originalNumber = 12345;
    int temp = originalNumber; // Bien tam cho qua trinh dao nguoc
    int reversedNumber = 0;    // Bien luu so dao nguoc, khoi tao bang 0

    // Vong lap de dao nguoc so
    while (temp > 0) {
        int digit = temp % 10;         // Lay chu so cuoi
        reversedNumber = reversedNumber * 10 + digit; // Them chu so vao so dao nguoc
        temp /= 10;                    // Loai bo chu so cuoi khoi so tam
    }

    cout << "So goc: " << originalNumber << endl;
    cout << "So dao nguoc: " << reversedNumber << endl;

    // Kiem tra neu so goc la thuan nghich (can so sanh voi so goc, KHONG phai temp)
    // Chu y: Vi du nay chi hien thi dao nguoc, kiem tra thuan nghich lam o vi du sau
    // cout << originalNumber << (originalNumber == reversedNumber ? " la" : " khong la") << " so thuan nghich." << endl;

    return 0;
}

Giải thích code:

  • Biến originalNumber lưu trữ số ban đầu.
  • temp là bản sao dùng trong quá trình đảo ngược.
  • reversedNumber khởi tạo bằng 0. Đây là nơi chúng ta sẽ xây dựng số đảo ngược.
  • Trong vòng lặp while (temp > 0):
    • int digit = temp % 10; lấy chữ số cuối cùng của temp.
    • reversedNumber = reversedNumber * 10 + digit; là bước mấu chốt.
      • reversedNumber * 10 dịch tất cả các chữ số hiện có của reversedNumber sang trái một vị trí (nhân 10).
      • + digit thêm chữ số mới (vừa trích xuất) vào vị trí hàng đơn vị mới.
    • temp /= 10; loại bỏ chữ số đã xử lý khỏi temp.
  • Sau vòng lặp, reversedNumber chứa số đảo ngược của originalNumber.

Kết quả chạy code trên với originalNumber = 12345 sẽ là: So goc: 12345 So dao nguoc: 54321

Ví dụ: Hàm kiểm tra số thuận nghịch sử dụng phương pháp đảo ngược

Bây giờ, kết hợp kỹ thuật đảo ngược số, chúng ta có thể xây dựng một hàm kiểm tra xem một số có phải là thuận nghịch hay không.

#include <iostream>

// Ham kiem tra so thuan nghich
bool isPalindrome(int n) {
    // So am thuong khong duoc coi la thuan nghich trong dinh nghia pho bien
    if (n < 0) {
        return false;
    }
    // So co mot chu so (0-9) la thuan nghich
    if (n >= 0 && n < 10) {
        return true;
    }

    int originalN = n; // Luu lai so goc
    int reversedN = 0; // Bien luu so dao nguoc

    // Tien hanh dao nguoc so
    while (n > 0) {
        int digit = n % 10;
        // Kiem tra tran so khi dao nguoc (chi quan trong voi so rat lon)
        // Doi voi int thong thuong, tran so dao nguoc it xay ra trong bai toan co ban
        // Nhung neu so goc qua lon, reversedN * 10 + digit co the vuot qua int MAX
        // De don gian, trong vi du co ban nay ta bo qua check tran so chi tiet
        reversedN = reversedN * 10 + digit;
        n /= 10;
    }

    // So sanh so goc voi so dao nguoc
    return originalN == reversedN;
}

int main() {
    int num1 = 121;
    int num2 = 123;
    int num3 = 4554;
    int num4 = 10;
    int num5 = 7;

    cout << num1 << (isPalindrome(num1) ? " la" : " khong la") << " so thuan nghich." << endl;
    cout << num2 << (isPalindrome(num2) ? " la" : " khong la") << " so thuan nghich." << endl;
    cout << num3 << (isPalindrome(num3) ? " la" : " khong la") << " so thuan nghich." << endl;
    cout << num4 << (isPalindrome(num4) ? " la" : " khong la") << " so thuan nghich." << endl;
    cout << num5 << (isPalindrome(num5) ? " la" : " khong la") << " so thuan nghich." << endl;
    cout << "-121" << (isPalindrome(-121) ? " la" : " khong la") << " so thuan nghich." << endl;


    return 0;
}

Giải thích code:

  • Hàm isPalindrome(int n) nhận vào một số nguyên n.
  • Hàm xử lý các trường hợp đặc biệt: số âm không thuận nghịch, các số từ 0 đến 9 luôn thuận nghịch.
  • Lưu lại giá trị gốc của n vào originalN trước khi thực hiện quá trình đảo ngược (vì n sẽ bị thay đổi trong vòng lặp).
  • Sử dụng vòng lặp while và các toán tử % 10, /= 10 để xây dựng reversedN giống như ví dụ trước.
  • Cuối cùng, hàm trả về kết quả của phép so sánh originalN == reversedN. Nếu bằng nhau, số đó là thuận nghịch (true); ngược lại, không phải (false).
  • Trong main, chúng ta gọi hàm isPalindrome với nhiều số khác nhau và in kết quả ra màn hình sử dụng toán tử ba ngôi ?: để cho output ngắn gọn.

Kết quả chạy code trên sẽ là: 121 la so thuan nghich. 123 khong la so thuan nghich. 4554 la so thuan nghich. 10 khong la so thuan nghich. 7 la so thuan nghich. -121 khong la so thuan nghich.

Kiểm Tra Số Thuận Nghịch Bằng Cách Chuyển Thành Chuỗi Ký Tự

Một cách tiếp cận khác để kiểm tra số thuận nghịch là chuyển số nguyên sang dạng chuỗi ký tự (string). Khi ở dạng chuỗi, việc kiểm tra thuận nghịch trở nên đơn giản hơn, tương tự như kiểm tra một từ có phải là palindrome (ví dụ: "madam", "level").

Để kiểm tra một chuỗi có phải palindrome không, chúng ta có thể dùng hai con trỏ (hoặc chỉ số), một bắt đầu từ đầu chuỗi và một bắt đầu từ cuối chuỗi. Di chuyển hai con trỏ vào trong, so sánh các ký tự tại vị trí hiện tại của chúng. Nếu tìm thấy cặp ký tự nào khác nhau, chuỗi đó không phải palindrome. Nếu hai con trỏ gặp nhau hoặc vượt qua nhau mà không tìm thấy sự khác biệt nào, thì chuỗi đó là palindrome.

Ví dụ: Hàm kiểm tra số thuận nghịch bằng cách chuyển chuỗi
#include <iostream>
#include <string> // Can include <string> de su dung string va to_string
#include <algorithm> // Can include <algorithm> cho cac thu vien xu ly chuoi (khong bat buoc cho cach nay nhung thuong dung)

// Ham kiem tra so thuan nghich bang cach chuyen thanh chuoi
bool isPalindromeString(int n) {
    // Xu ly so am neu can thiet. Thong thuong so am khong thuan nghich
    if (n < 0) {
        return false;
    }

    // Chuyen so nguyen thanh chuoi
    string s = to_string(n);

    // Su dung hai con tro (chi so) de kiem tra
    int left = 0; // Chi so bat dau tu dau chuoi
    int right = s.length() - 1; // Chi so bat dau tu cuoi chuoi

    // Duyet tu hai dau vao giua
    while (left < right) {
        // Neu cap ky tu khac nhau, khong phai thuan nghich
        if (s[left] != s[right]) {
            return false;
        }
        // Di chuyen con tro vao trong
        left++;
        right--;
    }

    // Neu vong lap ket thuc ma khong tim thay cap khac nhau, chuoi la thuan nghich
    return true;
}

int main() {
    int num1 = 121;
    int num2 = 987;
    int num3 = 5005;
    int num4 = 0;
    int num5 = -5;

    cout << num1 << (isPalindromeString(num1) ? " la" : " khong la") << " so thuan nghich (string). " << endl;
    cout << num2 << (isPalindromeString(num2) ? " la" : " khong la") << " so thuan nghich (string). " << endl;
    cout << num3 << (isPalindromeString(num3) ? " la" : " khong la") << " so thuan nghich (string). " << endl;
    cout << num4 << (isPalindromeString(num4) ? " la" : " khong la") << " so thuan nghich (string). " << endl;
    cout << num5 << (isPalindromeString(num5) ? " la" : " khong la") << " so thuan nghich (string). " << endl;


    return 0;
}

Giải thích code:

  • Hàm isPalindromeString(int n) nhận một số nguyên n.
  • to_string(n) chuyển số nguyên n thành một đối tượng string.
  • Chúng ta dùng hai biến left và right làm chỉ số truy cập các ký tự trong chuỗi s. left bắt đầu từ 0 (ký tự đầu tiên), right bắt đầu từ chỉ số cuối cùng (s.length() - 1).
  • Vòng lặp while (left < right) tiếp tục chừng nào hai chỉ số chưa gặp hoặc vượt qua nhau.
  • Trong mỗi lần lặp, chúng ta so sánh ký tự tại s[left] và s[right].
  • Nếu chúng khác nhau (s[left] != s[right]), số đó không phải thuận nghịch, hàm trả về false ngay lập tức.
  • Nếu chúng bằng nhau, chúng ta di chuyển left tiến lên (left++) và right lùi lại (right--) để so sánh cặp ký tự tiếp theo.
  • Nếu vòng lặp kết thúc (tức là left không còn nhỏ hơn right nữa) mà không tìm thấy cặp khác nhau nào, điều đó có nghĩa là tất cả các cặp đối xứng đều giống nhau, và số đó là thuận nghịch, hàm trả về true.

Kết quả chạy code trên sẽ là: 121 la so thuan nghich (string). 987 khong la so thuan nghich (string). 5005 la so thuan nghich (string). 0 la so thuan nghich (string). -5 khong la so thuan nghich (string).

Phương pháp chuyển sang chuỗi thường dễ code và dễ hiểu hơn so với phương pháp đảo ngược số bằng toán học thuần túy, đặc biệt với người mới bắt đầu. Tuy nhiên, nó có thể tốn kém tài nguyên hơn một chút vì phải tạo ra một đối tượng chuỗi mới.

Phân Tích Số Mở Rộng: Tính Tổng Chữ Số, Đếm Chữ Số

Kỹ thuật trích xuất chữ số bằng % 10 và /= 10 không chỉ dùng để kiểm tra số thuận nghịch. Nó là nền tảng cho rất nhiều bài toán liên quan đến các chữ số của một số nguyên. Dưới đây là hai ví dụ đơn giản khác về "phân tích" số: tính tổng các chữ số và đếm số lượng chữ số.

Ví dụ: Tính tổng và đếm số lượng chữ số
#include <iostream>

// Ham phan tich so: tinh tong va dem chu so
void analyzeNumber(int n) {
    if (n < 0) {
        cout << "Xin vui long nhap so nguyen khong am." << endl;
        return;
    }
    if (n == 0) {
        cout << "So 0 co 1 chu so, tong cac chu so la 0." << endl;
        return;
    }

    int temp = n; // Bien tam de phan tich
    int sumOfDigits = 0;
    int countOfDigits = 0;

    cout << "Phan tich so: " << n << endl;
    cout << "Cac chu so (tu cuoi len): ";

    // Vong lap phan tich
    while (temp > 0) {
        int digit = temp % 10; // Lay chu so cuoi
        cout << digit << " ";

        sumOfDigits += digit; // Cong vao tong
        countOfDigits++;      // Tang bien dem

        temp /= 10;           // Loai bo chu so cuoi
    }

    cout << endl; // Xuong dong sau khi in chu so
    cout << "Tong cac chu so: " << sumOfDigits << endl;
    cout << "So luong chu so: " << countOfDigits << endl;
}

int main() {
    analyzeNumber(12345);
    cout << "---" << endl;
    analyzeNumber(909);
    cout << "---" << endl;
    analyzeNumber(7);
    cout << "---" << endl;
    analyzeNumber(0);
    cout << "---" << endl;
    analyzeNumber(-100); // Test truong hop am

    return 0;
}

Giải thích code:

  • Hàm analyzeNumber(int n) nhận một số nguyên không âm.
  • Xử lý các trường hợp đặc biệt cho số âm và số 0.
  • Sử dụng biến temp để lặp.
  • sumOfDigits và countOfDigits được khởi tạo bằng 0 để lưu kết quả.
  • Vòng lặp while (temp > 0) thực hiện quá trình trích xuất chữ số quen thuộc.
  • Trong mỗi lần lặp:
    • digit = temp % 10; trích xuất chữ số.
    • sumOfDigits += digit; cộng chữ số vào tổng.
    • countOfDigits++; tăng biến đếm lên 1.
    • temp /= 10; loại bỏ chữ số.
  • Sau vòng lặp, sumOfDigits chứa tổng các chữ số, và countOfDigits chứa số lượng chữ số của số gốc (trừ trường hợp số 0 được xử lý riêng).
  • In ra kết quả thu được.

Kết quả chạy code trên sẽ là:

Phan tich so: 12345
Cac chu so (tu cuoi len): 5 4 3 2 1 
Tong cac chu so: 15
So luong chu so: 5
---
Phan tich so: 909
Cac chu so (tu cuoi len): 9 0 9 
Tong cac chu so: 18
So luong chu so: 3
---
Phan tich so: 7
Cac chu so (tu cuoi len): 7 
Tong cac chu so: 7
So luong chu so: 1
---
So 0 co 1 chu so, tong cac chu so la 0.
---
Xin vui long nhap so nguyen khong am.

Bài tập ví dụ: C++ Bài 4.B2: Số đặc biệt

Một số nguyên dương \(n\) được gọi là số đặc biệt nếu \(n\) chia hết cho tổng các chữ số của chính nó. Ví dụ, số \(27\) là số đặc biệt, còn hai số \(11\) và \(2013\) thì không phải là số đặc biệt.

Cho số nguyên dương \(n\). Hãy kiểm tra xem số \(n\) có phải là số đặc biệt hay không?

INPUT FORMAT

Dòng đầu tiên chứa số nguyên dương \(n(1\leq n \leq 10^{18})\).

OUTPUT FORMAT

Nếu \(n\) là số đặc biệt in ra 1, nếu không phải in ra 0. .

Ví dụ 1:

Input
27
Ouput
1

Giải thích ví dụ mẫu:

  • Ví dụ 1:
    • Input: 27
    • Giải thích: 27 chia hết cho tổng các chữ số của nó (2 + 7 = 9). <br>

Ý tưởng chính:

Một số n là số đặc biệt nếu n chia hết cho tổng các chữ số của nó. Do đó, chúng ta cần thực hiện hai bước chính:

  1. Tính tổng các chữ số của số n.
  2. Kiểm tra xem n có chia hết cho tổng đó hay không.

Các bước thực hiện:

  1. Đọc đầu vào:

    • Sử dụng cin để đọc số nguyên dương n.
    • Vì n có thể lên tới 10^18, kiểu dữ liệu int thông thường sẽ không đủ. Bạn cần sử dụng kiểu dữ liệu có kích thước lớn hơn, đó là long long trong C++.

  2. Tính tổng các chữ số:

    • Để tính tổng các chữ số của một số, bạn có thể lặp qua các chữ số của nó.
    • Một cách phổ biến để làm điều này là sử dụng vòng lặp while.
    • Trong mỗi bước lặp:
      • Lấy chữ số cuối cùng của số bằng toán tử modulo (%). Ví dụ, so % 10 sẽ cho chữ số hàng đơn vị.
      • Cộng chữ số này vào một biến lưu tổng (khởi tạo bằng 0).
      • Loại bỏ chữ số cuối cùng bằng cách chia số cho 10 bằng phép chia nguyên (/). Ví dụ, so / 10 sẽ bỏ đi chữ số hàng đơn vị.
    • Lặp lại cho đến khi số ban đầu trở thành 0.
    • Quan trọng: Bạn cần giữ lại giá trị gốc của n để kiểm tra tính chia hết ở bước sau. Vì vậy, hãy sử dụng một biến tạm thời (ví dụ: temp_n) để thực hiện việc tính tổng chữ số, trong khi biến n vẫn giữ giá trị gốc.

  3. Kiểm tra tính chia hết:

    • Sau khi tính được tổng các chữ số (gọi là sum_digits), hãy kiểm tra xem số gốc n có chia hết cho sum_digits hay không.
    • Sử dụng toán tử modulo (%). Nếu n % sum_digits == 0, tức là n chia hết cho tổng các chữ số của nó.

  4. Xuất kết quả:

    • Sử dụng cout để in ra 1 nếu n là số đặc biệt (điều kiện chia hết đúng).
    • In ra 0 nếu n không phải là số đặc biệt (điều kiện chia hết sai).

Gợi ý về cấu trúc code (không phải code hoàn chỉnh):

  • Bao gồm thư viện iostream (#include <iostream>).
  • Sử dụng cin và cout.
  • Khai báo biến n kiểu long long.
  • Đọc n.
  • Khai báo biến sum_digits (có thể là int vì tổng chữ số của 10^18 tối đa là 9 * 19 = 171, vẫn nằm trong phạm vi int), khởi tạo bằng 0.
  • Khai báo biến tạm temp_n kiểu long long, gán temp_n = n.
  • Sử dụng vòng lặp while (temp_n > 0) để tính tổng chữ số.
  • Bên trong vòng lặp: lấy chữ số (temp_n % 10), cộng vào sum_digits, cập nhật temp_n = temp_n / 10.
  • Sau vòng lặp, kiểm tra điều kiện n % sum_digits == 0.
  • Dùng câu lệnh điều kiện (if/else) để in ra 1 hoặc 0.
  • Có thể thêm ios_base::sync_with_stdio(false); cin.tie(NULL); ở đầu hàm main để tăng tốc độ nhập/xuất, dù với một số lượng input ít như thế này có thể không quá cần thiết.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.