Ôn tập tài liệu cuối học phần 2 - GGFORLEARN - Tài liệu tham khảo | Đại học Hoa Sen

ÔN TẬP CTDL&GT
Bài 2: Chuyen doi so nhi phan dung ngan xep (sử dụng stack) #include using namespace std; int main(){ int n; cin >> n; stack st; while(n != 0) { st.push(n % 2); n /= 2; } while(!st.empty()) { cout << st.top(); st.pop(); } return 0; }
Bài 3: Kiem tra dau ngoac hop le(Valid Parentheses) (sử dụng stack) #include using namespace std; void solve() { string s; cin >> s; stack st; for(char x : s) { if(x == '(') { st.push(x); }else { if(st.empty()) {
cout << "INVALID\n";//thieu dau ( return; }else { st.pop(); } } } if(st.empty()) { cout << "VALID\n"; }else {
cout << "INVALID\n"; // thieu dau ) } } int main(){ int t; cin >> t; while(t--) { solve(); } return 0; }
Bài 4: In sâu ký tự ngược lại(sử dụng stack)
Ví dụ nhập: python java php c++ js, In: js c++ php java python #include using namespace std; int main(){ string s; getline(cin, s); stringstream ss(s); string token; stack st; while(ss >> token) { st.push(token); } while(!st.empty()) {
cout << st.top() << " "; st.pop(); } return 0; }
Bài 5: Liệt kê các số nhị phân từ 1->N (sử dụng queue) #include using namespace std; vector res; void init() { queue q; q.push("1"); res.push_back("1"); while(res.size() < 10000) { string top = q.front(); q.pop(); res.push_back(top + "0"); res.push_back(top + "1"); q.push(top + "0"); q.push(top + "1"); } } int main(){ init(); int t; cin >> t; while(t--) { int n; cin >> n; for(int i = 0; i < n; i++) {
cout << res[i] << " "; } } return 0; }
Bài 6: Bội số chỉ chứa 0 va 9 của một số nguyên (sử dụng queue) #include using namespace std; using ll = long long; vector res; ll ans[101]; void init() { queue q; q.push("9"); res.push_back(9); while(1) { string top = q.front(); q.pop(); if(top.length() == 10) break;
res.push_back(stoll(top + "0"));// stoll: chuyen tu string sang long long
res.push_back(stoll(top + "9")); q.push(top + "0"); q.push(top + "9"); }
for(int i = 1; i <= 100; i++) { for(ll x : res) { if(x % i == 0) { ans[i] = x; break; } } } } int main(){ init(); int t; cin >> t; while(t--) { int n; cin >> n;
cout << ans[n] << endl; } return 0; }
Bài 7: In ra dãy các số chỉ chứa các số lộc phát(6,8) (sử dụng queue) #include using namespace std; using ll = long long; vector res; void init() { queue q; q.push("6"); q.push("8"); res.push_back("6"); res.push_back("8"); while(1) { string top = q.front(); q.pop(); if(top.length() == 15) break; res.push_back(top + "6"); res.push_back(top + "8"); q.push(top + "6"); q.push(top + "8"); } } int main(){ init(); int t; cin >> t; while(t--) { int n; cin >> n; vector tmp; for(string x : res) { if(x.length() == n + 1) break; tmp.push_back(x); }
reverse(tmp.begin(), tmp.end()); for(string x : tmp) { cout << x << " "; } cout << endl; } return 0; }
Bài 14: Sap xep vun dong (heapsort) #include using namespace std;
void heapify(int a[], int n, int i) { int l = 2 * i + 1; int r = 2 * i + 2; int largest = i;
if(l < n && a[l] > a[largest]) { largest = l; }
if(r < n && a[r] > a[largest]) { largest = r; } if(largest != i) { swap(a[i], a[largest]); heapify(a, n, largest); } } void heapsort(int a[], int n) {
for(int i = n / 2 - 1; i >= 0; i--) { heapify(a, n, i); }
for(int i = n - 1; i >= 0; i--) { swap(a[i], a[0]); heapify(a, i, 0); } } int main(){ int n; cin >> n; int a[1000]; for(int i = 0; i < n; i++) { cin >> a[i]; } heapsort(a, n); for(int i = 0; i < n; i++) {
cout << a[i] << " "; } return 0; }
Bài 15: In sâu nhị phân n phần tử ( thuật toán quay lui) #include using namespace std; int N, x[100]; void inkq() { for(int i = 1; i <= N; i++) {
cout << x[i] << " "; } cout << endl; } void Try(int i) { //Duyet cac kha nang cua x[i] for(int j = 0; j <= 1; j++) { x[i] = j; if(i == N) { inkq(); }else { Try(i + 1); } } } int main(){ cin >> N; Try(1); return 0; }
Bai.. Cay nhi phan va cac thao tac #include using namespace std; typedef int Item; struct Node {
Item infor; // Thông tin của node
Node* left; // Con trỏ node bên trái
Node* right; // Con trỏ node bên phải }; typedef Node* Tree;
// Khởi tạo cây nhị phân void Init(Tree* T) {
*T = NULL; // Đưa cây T về trạng thái rỗng }
// Cấp phát miền nhớ cho một node Tree GetNode() {
Tree p = new Node; // Cấp phát miền nhớ cho node
return p; // Trả lại node được cấp phát }
// Giải phóng một node p cho cây T void FreeNode(Tree p) {
delete p; // Giải phóng node p }
// Kiểm tra tính rỗng của cây T int isEmpty(Tree* T) {
return (*T == NULL); // Nếu T rỗng trả lại giá trị đúng } // Tạo một node cho cây T