Một vài lỗi sai khi code C++ trong các kì thi HSG Tin học (phần 1)

Đỗ Thị Hồng Ngát 23/09/2023
Một vài lỗi sai khi code C++ trong các kì thi HSG Tin học (phần 1)
23
Th9

Một vài lỗi sai khi code C++ trong các kì thi HSG Tin học (phần 1)

Trong các kì thi HSG Tin học, C++ là ngôn ngữ vô cùng phổ biến bởi tốc độ xử lí nhanh và sự hỗ trợ của các thư viện có sẵn. Tuy nhiên, đây cũng là một ngôn ngữ đòi hỏi sự tinh tế và kiến thức vững vàng để tránh những lỗi sai không đáng có. Đó có thể là những lỗi cú pháp đơn giản, hoặc thậm chí là những sai sót logic đáng tiếc. Để giúp các bạn chuẩn bị tốt hơn cho những kì thi quan trọng này, bài viết dưới đây sẽ điểm qua một số lỗi thường gặp khi code C++ trong các kì thi HSG Tin học, cùng những gợi ý và phương pháp để tránh những sai lầm không đáng có. Hãy cùng tìm hiểu và rèn luyện kỹ năng lập trình thật tốt để đạt kết quả cao trong cuộc thi!

1. String append

Hãy cùng phân tích độ phức tạp của dòng code dưới đây:

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

int main(){
    string s = "";
    for (int i = 1; i <= 1000000; i++){
        s = s + 'a';
    }
    cout << s << endl;
}

Thoạt nhìn qua thì có vẻ đoạn code trên chạy trong \(O(n)\), vì mỗi lần ta sẽ thêm một kí tự vào cuối xâu. Tuy nhiên đoạn code này có độ phức tạp là \(O(n^2)\) và sẽ chạy quá thời gian.

Hãy để ý đến dòng code s = s + 'a', với mỗi lần chạy đoạn code này, ta sẽ thực hiện copy string \(s\) rồi mới thêm kí tự \(‘a’\) vào cuối. Mỗi lần copy như vậy sẽ có độ phức tạo \(O(n)\), khiến tổng độ phức tạp sẽ là \(O(n^2)\).

Ta có thể sửa lại như sau:

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

int main(){
    string s = "";
    for (int i = 1; i <= 1000000; i++){
        s += 'a';
    }
    cout << s << endl;
}

Đoạn code s += 'a' sẽ trực tiếp thêm kí tự \(‘a’\) vào cuối với độ phức tạp \(O(1)\).

2. endl và ‘\n’

Hãy tìm ra điểm khác biệt trong hai đoạn code sau

Đúng vậy, hai code chỉ khác nhau ở chỗ, một code dùng endl còn một code dùng '\n'. Tuy nhiên sử dụng endl lại khiến TLE, tại sao lại như vậy?

Lý do là bởi endl là một manipulator (trình điều khiển), không phải là một kí tự đơn giản. Khi sử dụng endl, nó thực hiện hai thao tác. Đầu tiên, nó thêm kí tự xuống dòng '\n' vào đầu ra, sau đó nó đẩy các dữ liệu đang đợi xuống thiết bị đầu ra. Điều này đảm bảo rằng dữ liệu được đưa ra ngay lập tức, nhưng cũng làm cho endl chậm hơn.

Trong đa số trường hợp, hai cách này không có sự khác biệt lớn. Tuy nhiên ở những bài cần in ra ở nhiều dòng, endl có thể sẽ khiến code của bạn chậm đi đáng kể. Để khác phục điều này đối với những bạn đã quen sử dụng endl, ta có thể thêm một dòng code define endl '\n'

3. Tham chiếu và tham trị

Phân tích độ phức tạp đoạn code dưới đây

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

void do_something(vector<int> a){
    cout << "Hello world";
}

int main(){
    vector<int> a(1000000, 0);
    for (int i = 1; i <= 1000000; i++){
        do_something(a);
    }
}

Cũng giống như trường hợp đầu, nhìn qua code có vẻ sẽ chạy trong \(O(n)\). Nhưng hãy để ý, đoạn code thực chất chạy trong \(O(n^2)\), bởi ta đang truyền vector vào hàm do_something theo tham trị, tức là một bản sao của vector a sẽ được tạo ra và sử dụng trong hàm mỗi lần gọi do_something. Việc tạo bản sao sẽ tốn \(O(n)\), khiến tổng độ phức tạp của đoạn code là \(O(n^2)\).

Ta có thể giải quyết bằng việc sử dụng tham chiếu thay vì tham trị. Khi truyền tham số vào hàm theo tham chiếu, địa chỉ của biến số sẽ được truyền vào hàm. Do đó, thay đổi giá trị của tham số trong hàm sẽ ảnh hưởng trực tiếp đến biến gốc ngoài hàm. Tham chiếu thường được sử dụng khi muốn thay đổi giá trị của biến gốc trong hàm hoặc khi tham số có kích thước lớn và muốn tránh sao chép dữ liệu không cần thiết.

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

void do_something(vector<int> &a){ // tham chiếu
    cout << "Hello world";
}

int main(){
    vector<int> a(1000000, 0);
    for (int i = 1; i <= 1000000; i++){
        do_something(a);
    }
}


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

void do_something(vector<int> a){
    cout << "Hello world";
}

int main(){
    int a = 1000000000;
    long long x = a * a;
    cout << x << endl;
}

Bạn nghĩ kết quả sẽ là \(10^{18}\)? Hãy thử chạy trên máy của mình.

Có phải kết quả của bạn ra một con số âm nào đấy chẳng liên quan đến kết quả thực của \(x\)? Đúng vậy, \(x\) đã bị tràn số.

Bạn có thể đang tự thắc mắc: rõ ràng ta đã khai báo \(x\) là long long cơ mà? Nếu đúng như vậy, bạn đang chưa hiểu cách đoạn code x = a * a hoạt động như nào. Đầu tiên, compiler sẽ lấy giá trị của \(a\) nhân với giá trị của \(a\), rồi gán kết quả đó cho \(x\). Tuy nhiên, \(a\) mang kiểu dữ liệu int, nên kết quả sẽ phải trả về int, tuy nhiên \(10^{18}\) là quá lớn so với kiểu dữ liệu này.

Để khắc phục, ta sẽ ép kiểu dữ liệu của a

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

void do_something(vector<int> a){
    cout << "Hello world";
}

int main(){
    int a = 1000000000;
    long long x = (long long)a * a; // long long * int sẽ trả về long long
    cout << x << endl;
}

5. Mod overflow

Hãy tiếp tục thử chạy đoạn code dưới đây trên máy của bạn

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

void do_something(vector<int> a){
    cout << "Hello world";
}

int main(){
    int a = 1e9, b = 1e9, c = 1e9;
    const int MOD = 1e9 + 7;
    
    cout << (a + b + c) % MOD;
}

Một lần nữa, kết quả lại trả về một số âm nào đấy không liên quan? Đúng vậy, một lần nữa ta gặp phải vấn đề tràn số.

Hãy để ý đến thứ tự thực hiện tính toán trong C++. Với phép tính (a + b + c) % MOD, nó sẽ lần lượt thực hiện a + b rồi mới cộng đến c, đến lúc này, như trường hợp \(4\) đã nêu ở trên, giá trị sẽ vượt quá kiểu int. Để khắc phục, ta sửa lại thành ((a + b) % MOD + c) % MOD

Một vài trường hợp tiêu biểu khác liên quan đến tràn số khi \(MOD\):

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

void do_something(vector<int> a){
    cout << "Hello world";
}

int main(){
    int a = 1e9, b = 1e9, c = 1e9;
    const int MOD = 1e9 + 7;

    long long prod = ((a * b) % MOD * c) % MOD;
    // a * b sẽ vượt qua kiểu giá trị int. ta khắc phục như sau:
    prod = ((1ll * a * b) % MOD * c) % MOD;

    cout << prod << endl;

    long long sub = ((a - b) % MOD - c) % MOD;
    // lưu ý việc mod số âm sẽ khiến giá trị có thể bị âm. Ta sửa như sau:

    sub = ((a - b + MOD) % MOD - c + MOD) % MOD;
    cout << sub << endl;

}

Nên lưu ý rằng chỉ sử dụng phép toán mod khi cần thiết, bởi sử dụng nhiều phép toán này sẽ khiến chương trình chạy chậm đi.

Lời kết

Chúng ta có thể thấy rằng một vài lỗi nhìn có vẻ “ngớ ngẩn” nhưng lại rất dễ gặp phải nếu ở trong phòng thi dưới áp lực thời gian làm bài. Hi vọng các bạn sẽ ít gặp những lỗi sai như trên hơn và hãy tiếp tục đón chờ phần 2 của bài viết nhé.

Xem thêm tại: https://www.facebook.com/codedreamedu và https://codedream.edu.vn/hoc-thuat-toan/

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *