Tìm Số Đảo Ngược (VL18)

Nguồn: LuyenCode (VL18) Độ khó: Dễ Xâu Xử lý xâu Số lớn Cờ hiệu

Đề bài

Viết chương trình tìm số đảo ngược của 1 số nguyên dương $n$ nhập từ bàn phím.

Giới hạn: $0 \lt n \le 10^{1000}$ (tức là $n$ có thể dài tới 1001 chữ số).

Dữ liệu vào: Số nguyên dương $n$.

Dữ liệu ra: Số nguyên dương đảo ngược của số $n$.

Ví dụ 1 – input

1234

Ví dụ 1 – output

4321

Ví dụ 2 – input

1320

Ví dụ 2 – output

231

Lời mở đầu

Hôm nay mình chia sẻ một bài rất cơ bản, nhưng qua cách mình góp ý bài làm và hướng dẫn một em học viên thì mình nghĩ sẽ có nhiều điều đáng học hỏi 🤗. Em ấy nhắn: "anh ơi giúp em bài này với ạ, em thử trong Visual mọi trường hợp em thấy ổn hết nhưng khi nộp chỉ đúng có một test". Thế là hai anh em cùng "bắt bệnh" từng chút một, từ cái code ban đầu cho đến lời giải gọn gàng, rồi còn thêm một thử thách nhỏ: làm sao chỉ dùng đúng 1 vòng lặp.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ: với $n = 1234$ thì viết ngược lại các chữ số là 4321. Với $n = 1320$ thì viết ngược lại sẽ được 0231, nhưng một số nguyên dương thì không có chữ số 0 ở đầu, nên đáp án là 231. Tức là các chữ số 0 ở cuối của $n$ sẽ biến mất khi đảo ngược, còn các chữ số 0 nằm giữa thì vẫn giữ nguyên (ví dụ $1020300 \to 30201$).

Chú ý giới hạn

$n \le 10^{1000}$ nên $n$ có thể dài tới 1001 chữ số, không có kiểu số nguyên nào chứa nổi (kể cả long long chỉ khoảng 19 chữ số). Vì vậy ta phải đọc $n$ vào dưới dạng chuỗi và xử lý từng ký tự chữ số.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bắt bệnhCode ban đầu sai ở đâu?Cách 12 vòng lặp · nên dùngCách 21 vòng lặp + cờ hiệu

Bắt bệnh code ban đầu của em học viên

Đây là code em học viên gửi mình (chỉ đúng 1 test khi nộp):

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    fflush(stdin);
    getline(cin, s);
    int len = s.length();
    if(s[len-1] == '0')
    {
        s.erase(s.begin() + (len-1));
    }
    if(s[0] == '0')
    {
        s.erase(s.begin());
    }
    if(s[0] == '-')
    {
        s.erase(s.begin());
        s[len-1] = '-';
        s[len] = '\0';
    }
    if(len == 1 && s[len -1] == 0)
    {
        cout << 0;
    }
    for(int i = len -1; i >= 0; i--)
    {
        cout << s[i];
    }
    return 0;
}

Chuyện nhỏ: câu lệnh fflush(stdin) trước getline

Mình hỏi em: sao em lại có câu lệnh fflush(stdin); trước getline vậy, tại sao lại cần nó? Em trả lời là em tưởng nhập chuỗi thì cần xoá bộ nhớ đệm. Thật ra nó tuỳ trường hợp:

• Nếu trước câu lệnh nhập chuỗi mà có 1 câu lệnh nhập số (số nguyên hay số thực), thì sau khi nhập số xong mình nhấn Enter, cái Enter đó sẽ nằm lại trong bộ đệm. Đến khi nhập chuỗi thì nó tưởng cái Enter đó là nhập cho chuỗi ⇒ bỏ qua không cho nhập. Thế nên mới cần một lệnh "dọn" cái Enter đó ở sau bước nhập số và trước bước nhập chuỗi.
• Còn nếu chỉ toàn là nhập chuỗi thì không cần dòng đó.

fflush(stdin) không chuẩn

fflush(stdin) cũng không chuẩn đâu nha, trên một số IDE / hệ thống chấm nó sẽ không hoạt động. Nếu code theo kiểu C thì nên thay bằng rewind(stdin);, còn nếu code theo C++ dùng string + getline thì dùng cin.ignore(); nhé.

Tự đưa ra test để tìm chỗ sai

Khi làm bài trên các trang chấm bài, các bạn hãy hiểu test mẫu cho là 1 chuyện thôi, mình phải tự đưa ra nhiều trường hợp khác nữa để test, chứ không phải đúng 1, 2 test mẫu rồi khi chấm bị sai lại không biết vì sao sai. Những hệ thống này không hiện test sai cho mình, mình phải tự nghiệm lấy.

Ví dụ bài của em, mình chạy thử với test đơn giản 123000:

123000 00321

Nó ra kết quả sai rành rành ra đây, lẽ ra đáp án chỉ là 321 thôi. Em giải thích là em chỉ nghĩ có 1 số 0 nên chưa tính đến, nhưng 123000 vẫn là 1 số input hợp lệ trong điều kiện cho phép mà 😀. Code chỉ xoá đúng một ký tự '0' ở cuối, nên các số 0 còn lại vẫn bị in ra.

Còn một lỗi "ẩn" nữa

Sau khi erase, độ dài chuỗi đã giảm đi 1 nhưng biến len vẫn giữ giá trị cũ, nên vòng lặp cuối bắt đầu in từ s[len - 1] – vị trí ngay sau ký tự cuối của chuỗi mới (một ký tự '\0'). Mình chạy lại code này thì thấy: với 1320 nó in ra '\0' rồi mới tới 231, với 123000 nó in '\0' + 00321 (chính là cái "khoảng trắng" lạ ở đầu dòng kết quả phía trên). Nhìn trên màn hình thì tưởng gần đúng, nhưng hệ thống chấm so từng ký tự nên vẫn bị sai.

Tránh thêm / xoá trên mảng khi không cần thiết

Vốn dĩ ngay từ đầu em chọn theo hướng làm này là đã thấy không ổn rồi: tự làm khó mình và không tối ưu chút nào. Các bạn nhớ giùm mình 1 điều này nha:

Một câu cần nhớ kỹ

Khi đụng đến mảng / chuỗi (bản chất chuỗi là mảng ký tự), nếu có thể giải quyết vấn đề không cần thêm hay xoá thì tốt nhất nên tránh thêm hay xoá. Vì thêm hay xoá nó sẽ dẫn đến code phức tạp là 1 chuyện, mà hiệu suất lại kém, bởi nó sẽ phải liên tục di dời toàn bộ phần tử sau vị trí thêm hay xoá nhích lên hay nhích xuống. Ví dụ 1 mảng có 1000 phần tử, em xoá thằng đầu tiên thì 999 thằng sau phải nhích lên 1.

Chừng nào đề nói rõ phải áp dụng cách thêm hay xoá để ra kết quả thì lúc đó mới phải làm đúng như vậy. Còn bài này hãy nhìn kỹ: ví dụ chuỗi là "123", ta làm sao không cần biết, miễn ta in ra được "321" 😀. Em làm cách nào cũng được miễn sau cùng ra đáp án output giống như đề bài cần thôi mà.

Cách 1Bỏ qua các số 0 ở cuối rồi in ngược – O(N)

Để gợi ý, mình nói qua 1 vấn đề khác: giờ input là mảng số nguyên, ví dụ [1, 2, 3, 4, 5], mình muốn xuất ra mảng bị đảo ngược lại, tức là in ra 5, 4, 3, 2, 1. Vậy em sẽ làm sao? ⇒ Cho vòng lặp chạy ngược lại! Quá thô thiển và rõ ràng rồi nha 😀. Vậy vấn đề bài kia cũng như vậy thôi á: chạy ngược in từng ký tự từ cuối về đầu, nhưng với ký tự '0' thì cẩn thận nhé.

Ví dụ "1020300" thì chỉ in ra "30201": 2 số 0 cuối cùng thì không in ra, còn những số 0 khác thì in ra bình thường. Vậy mấu chốt ở đâu? Rõ ràng mình không có xoá gì cả, mình chỉ cần chọn lọc in ra hay không in thôi 🙂. Nếu không in thì bỏ qua nó. Em sẽ nhìn thấy quy luật là:

Quy luật

Duyệt từ cuối về đầu: nếu đầu tiên là những ký tự '0' thì mình bỏ qua không in nó ra, cho đến khi nào gặp ký tự khác '0' đầu tiên thì từ đó về đầu là in ra hết tất cả.

• Input "1020300": duyệt từ cuối về, gặp '0' ⇒ bỏ qua, gặp '0' ⇒ bỏ qua, gặp '3' ⇒ bắt đầu từ đây đến đầu chuỗi là cứ in ra hết ⇒ in ra "30201".
• Input "123": duyệt từ cuối về, gặp '3' thoả mãn khác '0' ⇒ từ đây về đầu in ra hết ⇒ in ra "321".

Thành ra code gồm 2 vòng lặp: vòng lặp thứ nhất cho biến ketthuc lùi từ cuối chuỗi qua hết các ký tự '0', vòng lặp thứ hai in các ký tự từ ketthuc về 0.

Không cần lo số 0 ở đầu

Em học viên lúc đầu còn viết thêm một vòng lặp tìm vị trí batdau là chữ số khác '0' đầu tiên tính từ đầu chuỗi. Đoạn đó dư thừa nha: dữ liệu vào là số nguyên dương hợp lệ (đề ghi rõ "số nguyên dương $n$" chứ không phải "chuỗi số nguyên dương"), mà số thì không bao giờ có số 0 ở đầu. Nếu là "chuỗi số" thì còn có thể sợ có số 0 ở đầu, nhưng đã là số thì không có chuyện đó, nên bỏ bớt vòng lặp đó đi, cứ thế duyệt về 0 thôi ⇒ cả thảy 2 vòng lặp. Cũng vì $n \gt 0$ nên chắc chắn có ít nhất một chữ số khác '0', vòng while không bao giờ chạy lố ra ngoài chuỗi.

Minh hoạ

Em nhập số $n$ rồi bấm Tiếp. Ô đỏ gạch ngang là số 0 ở cuối bị bỏ qua, ô xanh là chữ số đã in ra màn hình:

n

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này (đọc $n$ bằng cin >> s vì $n$ là một "từ" liền, không chứa khoảng trắng):

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int ketthuc = s.length() - 1;
    while(s[ketthuc] == '0')
        ketthuc--;
    for(int i = ketthuc; i >= 0; i--)
        cout << s[i];
    return 0;
}

s = input().strip()
ketthuc = len(s) - 1
while s[ketthuc] == '0':
    ketthuc -= 1
kq = []
for i in range(ketthuc, -1, -1):
    kq.append(s[i])
print(''.join(kq))

Về dòng #include <bits/stdc++.h>

Với những hệ thống chấm bài dùng trình biên dịch GNU C++ (và các IDE như Dev-C++, Code::Blocks), chỉ 1 thư viện này là nó như bao trọn tất cả các thư viện khác rồi, cần sử dụng toán học hay bất kỳ cái gì không cần include gì thêm hết. Còn Visual Studio không dùng trình biên dịch GNU C++ mà dùng trình biên dịch riêng của nó, nên Visual Studio không dùng thư viện đó được nha. Ngoài ra, các bạn cũng tránh đặt trùng tên biến (ví dụ đã có biến i ở ngoài mà vòng lặp lại khai báo thêm 1 biến i nữa) – tuy có thể không sai nhưng sẽ dễ bị lỗi lắm đó.

C++▶ Chạy tay từng dòng codeCách 1: vòng while lùi ketthuc qua các số 0 ở cuối, rồi vòng for in từ ketthuc về 0.

Dữ liệu vào (stdin) – sửa thoải mái1320

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main()

5{

6 string s;

7 cin >> s;

8 int ketthuc = s.length() - 1;

9 while(s[ketthuc] == '0')

10 ketthuc--;

11 for(int i = ketthuc; i >= 0; i--)

12 cout << s[i];

13 return 0;

14}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ cần chuỗi chứa $n$ ⇒ $O(N)$ với $N$ là số chữ số của $n$.
• Thời gian: vòng while đi qua các số 0 ở cuối, vòng for đi qua phần còn lại, mỗi ký tự được xét đúng 1 lần ⇒ $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Cách 2Chỉ 1 vòng lặp với biến cờ hiệu – O(N)

Nếu em đã hiểu đoạn code ở trên rồi thì lẽ ra bài này đã xong rồi, tuy nhiên mình đố em vui 1 câu để giúp em có thêm thử thách, cũng như trải qua nó sẽ giúp em có thêm kiến thức hen ^^.

Như em đã thấy, code cách 1 phải dùng đến 2 vòng lặp. Vậy mình đố em có thể code sao cho chỉ dùng 1 vòng lặp thôi không? Tất nhiên cũng vẫn là theo tư tưởng xử lý như đã nói: duyệt từ cuối về đầu, nếu khởi đầu gặp toàn ký tự '0' thì bỏ qua không in nó ra, còn tại 1 chỗ nào gặp ký tự đầu tiên khác '0' thì từ đó về đầu là cứ thế in ra hết.

Em ấy thử rất nhiều lần vẫn chưa được, nên mình đưa giải pháp của mình. Cơ bản ta có biến check để biết khi nào sẽ in các ký tự ra:

• Nếu check = true thì kể từ lúc đó là nó cứ in ra.
• Còn nếu check = false thì chưa in ra, nhưng sẽ cứ kiểm tra xem khi nào có thể in ra được thì cập nhật lại check = true.

Kỹ thuật xử lý cờ hiệu

Ban đầu biến check khởi tạo là false. Tìm ra được ký tự đầu tiên khác '0' (tính từ cuối) thì kể từ lúc đó cập nhật lại check = true và đồng thời in ra ngay ký tự đó, để rồi từ các lần lặp ký tự tiếp theo thấy check = true thì cứ thế in ký tự ra thôi 😀. Đúng 1 vòng lặp hen ^^.

Minh hoạ cờ hiệu

Bấm Tiếp để xem biến check "bật" lên ở đâu:

n

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    bool check = false;
    for(int i = s.length() - 1; i >= 0; i--)
    {
        if(check == false && s[i] != '0')
            check = true;
        if(check == true)
            cout << s[i];
    }
    return 0;
}

s = input().strip()
check = False
kq = []
for i in range(len(s) - 1, -1, -1):
    if check == False and s[i] != '0':
        check = True
    if check == True:
        kq.append(s[i])
print(''.join(kq))

C++▶ Chạy tay từng dòng codeCách 2: 1 vòng lặp từ cuối về đầu, biến cờ check bật lên ở chữ số khác 0 đầu tiên.

Dữ liệu vào (stdin) – sửa thoải mái123000

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main()

5{

6 string s;

7 cin >> s;

8 bool check = false;

9 for(int i = s.length() - 1; i >= 0; i--)

10 {

11 if(check == false && s[i] != '0')

12 check = true;

13 if(check == true)

14 cout << s[i];

15 }

16 return 0;

17}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp: vẫn là duyệt mỗi ký tự đúng 1 lần ⇒ thời gian $O(N)$, bộ nhớ $O(N)$ cho chuỗi.

Không gian$O(N)$

Thời gian$O(N)$

Vậy nên dùng cách nào?

Mình hỏi tiếp em học viên: giữa cách dùng 2 vòng lặp như ban đầu với cách dùng 1 vòng lặp này thì theo em cách nào sẽ mang đến hiệu suất chương trình tốt hơn? Và nếu làm thì mình nên áp dụng theo cách nào? Em trả lời cách 1 có hiệu suất tốt hơn vì nó sẽ kiểm tra ít điều kiện hơn – chính xác 😊.

• Cách 2 cứ mỗi ký tự lại phải đi kiểm tra điều kiện biến check là true hay false (tới 2 câu if).
• Trong khi nếu làm theo cách 1 thì không cần như thế: vòng while chỉ so sánh với '0', vòng for thì chỉ việc in.

Kết luận

Thành ra chịu khó tách ra 2 vòng lặp, kệ code có dài hơn 1 chút (thực ra không cách biệt mấy), nhưng nó rõ ràng code cho người xem (những người làm chung với mình chẳng hạn) và hiệu suất tốt hơn cho chương trình ⇒ nên theo cách 1 nhé 😀. Cách 2 vẫn rất đáng học vì kỹ thuật cờ hiệu sẽ còn gặp lại ở rất nhiều bài khác.

Qua bài này em đã học được nhiều điều hen: tự nghĩ test để tìm lỗi, tránh thêm / xoá trên mảng khi không cần thiết, đọc kỹ đề (số khác chuỗi số), và kỹ thuật cờ hiệu. Mỗi bài mình đụng phải là 1 kinh nghiệm học được, gom tất cả làm hành trang kinh nghiệm cho những bài sau nha 😊.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên (độ dài 1 đến 1000 chữ số, nhiều test có một dãy số 0 ở cuối, có cả test $n = 10^{1000}$), so với kết quả đảo chuỗi rồi bỏ số 0 ở đầu – khớp hết; với $n$ dài 1001 chữ số chương trình chạy tức thì. Code ban đầu của em học viên mình cũng chạy lại: sai với cả 1320 lẫn 123000 đúng như phân tích ở trên.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇