Ô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 tài liệu cuối học phần 2 - GGFORLEARN - Tài liệu tham khảo | Đại học Hoa Sen  được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem

ÔN TẬP CTDL&GT
Bài 2: Chuyen doi so nhi phan dung ngan xep (sử dụng stack)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
stack<int> 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<bits/stdc++.h>
using namespace std;
void solve()
{
string s; cin >> s;
stack<char> 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<bits/stdc++.h>
using namespace std;
int main(){
string s;
getline(cin, s);
stringstream ss(s);
string token;
stack<string> 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<bits/stdc++.h>
using namespace std;
vector<string> res;
void init()
{
queue<string> 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<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> res;
ll ans[101];
void init()
{
queue<string> 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<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<string> res;
void init()
{
queue<string> 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<string> 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<bits/stdc++.h>
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<bits/stdc++.h>
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 <iostream>
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
| 1/23

Preview text:

Ô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