C++ là một ngôn ngữ lập trình vô cùng phổ biến trong cộng đồng lập trình thi đấu hiện nay bởi là một trong những ngôn ngữ có tốc độ xử lí nhanh nhất. Ngoài ra, nó còn được sử dụng nhiều bởi có những thư viện hỗ trợ vô cùng tiện lợi, ví dụ như STL (Standard Template Library). Tuy nhiên, vẫn còn rất nhiều điều để khai thác từ ngôn ngữ này trong lập trình thuật toán, hãy cùng Codedream khám phá những tips và tricks có thể bạn chưa biết để tiết kiệm được thời gian, cũng như code trở nên ngắn gọn hơn nhé.
Tips sử dụng ternary operator
Ternary opeator được sử dụng để tạo ra các biểu thức có điều kiện. Nó cho phép chúng ta đưa ra một quyết định dựa trên một điều kiện và trả về giá trị tùy thuộc vào kết quả của điều kiện đó. Cú pháp của ternary operator như sau:
condition ? value_if_true : value_if_false;
Xét đoạn code sau:
int a = 2, b = 1; bool larger; if (a > b) larger = true; else larger = false;
Ta có thể rút ngắn đoạn code trên sử dụng ternary operator:
int a = 2, b = 1; bool larger = (a > b) ? true : false;
Trong ví dụ trên, ta có 2 số nguyên (a, b) và biến (larger) để kiểm tra nếu (a > b). Nếu (a > b) biểu thức trên sẽ trả về (true) và gán cho (larger), ngược lại nếu (a le b) biểu thức trên sẽ trả về (false) và (larger) sẽ có giá trị là (false).
Ternary operator rất hữu ích khi chúng ta cần đưa ra quyết định ngắn gọn dựa trên một điều kiện duy nhất và trả về một giá trị tương ứng.
Tips sử dụng macro để biết được tên biến
Ta có thể sử dụng dấu (‘#’) để biến được chính xác tên của argument được truyền vào macro.
Ví dụ:
#define debug(x) cerr << #x << " is " << x << endl; int K = -273; debug(K) // K is -273 debug(abs(K)) // abs(K) is 273
Việc sử dụng macro trên sẽ giúp chúng ta dễ dàng hơn nhiều trong việc debug.
Tips sử dụng {} để khởi tạo giá trị cho các container
Pair, Tuple
Thay vì
pair<int, int> a = make_pair(1, 2); tuple<char, int, int> b = make_tuple('x', 1, 2);
ta có thể code như sau
pair<int, int> a = {1, 2}; tuple<char, int, int> b = {'x', 1, 2};
STL containers
vector<int> a = {2, 7, 0, 6}; for (auto v : a){ cout << v << " "; } // 2 7 0 6 set<pair<int, int>> b = {{4, 3}, {2, 1}, {6, 7}, {3, 2}, {2, 1}}; for (auto v : b){ cout << v.first << " " << v.second << endl; } /* 2 1 * 3 2 * 4 3 * 6 7 */ deque<vector<int>> c = { {2, 1, 3, 4}, {6, 1, 4, 9, 2}, {7, 0, 1, 5, 0}, }; for (auto v : c){ for (auto x : v){ cout << x << " "; } cout << endl; } /* * 2 1 3 4 * 6 1 4 9 2 * 7 0 1 5 0 */
Lưu ý: cách gán trên không áp dụng được cho stack và queue.
Tips sử dụng bitset để chuyển số từ hệ thập phân sang nhị phân
Một cách phổ biến thường được dùng là:
vector<int> ToBinary(int val){ vector<int> ans; while (val > 0){ ans.push_back(val % 2); val /= 2; } reverse(ans.begin(), ans.end()); return ans; }
Ta có thể sử dụng bitset để code nhìn gọn hơn:
int val = 27; cout << bitset<31>(val).to_string() << endl; // 0000000000000000000000000011011
Lưu ý: Với cách làm này ta cần phải xác định được trước số bit cần được in ra.
Một vài hàm hữu dụng trong C++
(all(v))
Hàm này được mình tự viết lại và sử dụng thường xuyên bởi sự tiện lợi và ngắn gọn của nó.
#define all(v) v.begin(), v.end() vector<int> a = {3, 2, 4, 1, 9, 2}; sort(all(a)); // Thay vì phải viết đầy đủ sort(a.begin(), a.end()) ta // đã rút gọn lại thành sort(all(a)) ngắn gọn và dễ hiểu. for (auto v : a) cout << v << " "; // 1 2 2 3 4 9
(unique(v))
Hàm (unique) được sử dụng để loại bỏ các phần tử trùng lặp liên tiếp trong một dãy. Có thể áp dụng hàm này để có thể thực hiện “nén số” với những bài tập chỉ cần quan tâm đến tính “lớn bé” của các phần tử.
vector<int> v = {1, 1, 1, 2, 2, 3, 3, 3, 4, 4}; v.erase(unique(all(v)), v.end()); for (auto val : v){ cout << v << " "; } // 1 2 3 4
Ngoài ra có thể áp dụng hàm này để có thể thực hiện “nén số” với những bài tập chỉ cần quan tâm đến tính “lớn bé” của các phần tử. Phương pháp này bạn sẽ cần sử dụng nhiều trong các bài tập lập trình thi đấu.
#define all(v) v.begin(), v.end() ... vector<int> a = {1009, 2012, 2016, 4096, 2706, 2012, 2005, 4096}; vector<int> b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); // 1009 2005 2012 2016 2706 4096 for (auto &v : a){ v = lower_bound(all(b), v) - b.begin() + 1; cout << v << " "; } // 1 3 4 6 5 3 2 6
(fill)
Hàm (fill) trong C++ được sử dụng để gán giá trị nhất định cho tất cả các phần tử trong dãy
#define all(v) v.begin(), v.end() vector<int> a(10); fill(all(a), 5); for (auto v : a) cout << v << " "; // 5 5 5 5 5 5 5 5 5 5
(iota)
Hàm (iota) được sử dụng để gán giá trị tăng dần cho các phần tử trong dãy
#define all(v) v.begin(), v.end() vector<int> a(10); iota(all(a), 1); for (auto v : a) cout << v << " "; // 1 2 3 4 5 6 7 8 9 10 iota(all(a), 10); for (auto v : a) cout << v << " "; // 10 11 12 13 14 15 16 17 18 19
(accumulate)
Hàm (accumulate) được sử dụng để tính tổng các phần tử trong dãy số
#define all(v) v.begin(), v.end(); vector<int> a = {6, 1, 2, 3, 7, 0, 9, -6, 4, 5}; cout << accumulate(all(a), 0) << endl; // 31
Lưu ý: tham số thứ 3 của hàm là giá trị khởi điểm của tổng và được cộng dần với các phần tử trong dãy. Nếu tổng của dãy lớn hơn giá trị thuộc (int) thì phải gán (long ; long) cho giá trị khởi điểm, nếu không sẽ xảy ra hiện tượng tràn số.
#define all(v) v.begin(), v.end(); vector<int> a = {1000000000, 1000000000, 1000000000}; cout << accumulate(all(a), 0) << endl; // -1294967296 cout << accumulate(all(a), 0ll) << endl; // 3000000000
(generate)
Hàm (generate) trong C++ được sử dụng để tạo ra các giá trị trong một dãy dựa trên một hàm sinh giá trị.
int gen() { return rand() % 1000 + 1; } // Sinh các giá trị ngẫu nhiên từ 1 -> 1000 #define all(v) v.begin(), v.end() vector<int> a(10); generate(all(a), gen); for (auto v : a) cout << v << " "; // 384 887 778 916 794 336 387 493 650 422
(rotate)
Hàm (rotate) trong C++ được sử dụng để xoay (quay) các phần tử trong một dãy.
#define all(v) v.begin(), v.end() vector<int> a = {3, 2, 4, 1, 5}; rotate(a.begin(), a.begin() + 2, a.end()); for (auto v : a) cout << v << " "; // 4 1 5 3 2
(merge)
Hàm (merge) trong C++ được sử dụng để trộn (hợp nhất) hai dãy đã được sắp xếp thành một dãy mới
#define all(v) v.begin(), v.end() vector<int> a = {1, 3, 5}; vector<int> b = {2, 4, 6}; vector<int> c((int)a.size() + (int)b.size()); merge(all(a), all(b), c.begin()); for(auto v : c){ cout << v << " "; } // 1 2 3 4 5 6
Lời kết
Trong bài viết trên, chúng ta đã khám phá một số tips và tricks trong lập trình C++ áp dụng trong việc giải lập trình thuật toán, hi vọng bạn đọc thấy thú vị và có thể áp dụng vào các bài tập của mình. Ngoài ra vẫn còn nhiều tips và tricks nữa, nếu bạn thấy bài viết này hay hãy cho bọn mình biết để tiếp tục ra phần 2 của bài viết nhé.
Xem thêm tại: https://codedream.edu.vn/hoc-thuat-toan/ và https://www.facebook.com/codedreamedu
