Bài 1. Viết chương trình sử dụng toán tử cin, cout để nhập vào 3 số nguyên, kiểm tra xem nó có thể tạo thành 3 cạnh của tam giác vuông không?

Bài 2. Nhập vào xâu ký tự (kiểu string) bằng cin, chuyển đổi xâu ký tự đó thành xâu ký tự hoa, xâu ký tự thường, in ra màn hình xâu ký tự hoa, xâu ký tự thường.

Ví dụ:

• Nhập vào: Hello World
• In ra màn hình: HELLO WORLD và hello world

Bài 3. Viết hàm tìm giá trị lớn nhất (max) và giá trị nhỏ nhất (min) của 3 số nguyên theo nguyên mẫu dưới đây. Viết hàm main cho phép nhập vào 3 số nguyên tìm giá trị lớn nhất và nhỏ nhất bằng hàm đã xây dựng.

void maxmin(int a, int b, int c, int &max, int &min);

Bài 4. Viết hàm có đối mặc định để có thể vừa tìm max hoặc tìm min tùy theo đối ismax theo nguyên mẫu dưới đây, sau đó viết hàm main nhập vào 3 số nguyên khác nhau tìm số không phải max, min bằng cách tính tổng rồi trừ đi max và min.

int MaxMin(int a, int b, int c, bool ismax = true);

Ví dụ:

• Nhập vào 3 số: 10 5 15
• Số không phải max, min là: (10+5+15) – MaxMin(10,5,15) – MaxMin(10,5,15, false)

Bài 5. Viết hàm mẫu (template) tìm max của hai số, áp dụng tìm max của 2 số nguyên và hai số thực.

Bài 6. Viết hàm mẫu (template) tìm ước chung lớn nhất của 2 số.

Bài 7. Viết hàm mẫu (template) nhập 1 dãy số từ bàn phím, hàm mẫu (template) in một dãy số ra màn hình. Viết hàm main, sử dụng các hàm này nhập vào và in ra màn hình 1 dãy số thực.

};

Bài 3. Sử dụng lớp Point trong bài 7 xây dựng tam giác (Triangle) có thuộc tính là tọa độ của 3 đỉnh và các phương thức: nhập tọa độ đỉnh từ bàn phím, in tọa độ 3 đỉnh lên màn hình, tính diện tích, tính chu vi.

Viết hàm main, nhập vào 1 tam giác, in lên màn hình diện tích, chu vi của tam giác đó.

Bài 4. Bổ sung hàm tạo có đối cho các lớp Time, Point, Triangle ở các bài 6, 7, 8.

Bài 5. Cải tiến các lớp Time, Point, Traingle bằng cách thay các phương thức input, display bằng các toán tử nhập >>, toán tử xuất <<.

Bài 6. Xây dựng lớp biểu diễn các Vector mẫu (template) trong không gian n chiều có các phương thức toán tử: +, - hai vector, * tích vô hướng hai vector, - đổi dấu một vector, toán tử >>, <<.

Viết hàm main, nhập vào 2 vector cùng số chiều, in lên màn hình các vector tổng, hiệu của 2 vector đã nhập.

III. Phân tích độ phức tạp

Bài 1. Phân tích độ phức tạp tiêm cận của từng thuật toán dưới đây (Ex1,..,Ex5)

Algorithm Ex1(A): Input: An array A storing n ≥ 1 integers. Output: The sum of the elements in A. s←A[0] for i←1 to n−1 do s←s+A[i] return s Algorithm Ex2(A): Input: An array A storing n ≥ 1 integers. Output: The sum of the elements at even cells in A. s←A[0] for i←2 to n−1 by increments of 2 do s←s+A[i] return s Algorithm Ex3(A): Input: An array A storing n ≥ 1 integers. Output: The sum of the prefix sums in A. s← for i←0 to n−1 do s←s+A[0]

for j ←1 to i do s←s+A[j] return s Algorithm Ex4(A): Input: An array A storing n ≥ 1 integers. Output: The sum of the prefix sums in A. s←A[0] t ←s for i←1 to n−1 do s←s+A[i] t ← t+s return t Algorithm Ex5(A,B): Input: Arrays A and B each storing n ≥ 1 integers. Output: The number of elements in B equal to the sum of prefix sums in A. c← for i←0 to n−1 do s← for j ←0 to n−1 do s←s+A[0] for k←1 to j do s←s+A[k] if B[i] = s then c←c+ return c

Bài 2. Cài đặt thuật toán prefixAverages1 và prefixAverages2 trong bài giảng, thực hiện phân tích thử nghiệm thời gian chạy của từng thuật toán với các bộ dữ liệu đầu vào có kích thước n = 100, 200, ...., 2000. Vẽ biểu đồ log-log biểu thị quan hệ giữa thời gian và kích thước dữ liệu đầu vào của 2 thuật toán.

Bài 3. Hãy viết thuật toán giả mã (Pseudo-code) tính giá trị của 1 đa thức 𝑝(𝑥) = ∑ 𝑛𝑖=0𝑎𝑖 𝑥𝑖

1. Thuật toán có độ phức tạp O(n 2 ) b. Thuật toán có độ phức tạp O(n)

Bài 4. Mô tả thuật toán giả mã (pseudo-code) nhân hai ma trận A, B trong đó A có kích thước n×m, B có kích thước m× p. Lưu ý C = A được định nghĩa như sau 𝐶[𝑖][𝑗] = ∑ 𝑚𝑘=1 𝐴[𝑖][𝑘] ∗ 𝐵[𝑘][𝑗]. Phân tích thời gian tiệm cận của thuật toán?

1. Bổ sung 1 sinh viên vào danh sách (bổ sung vào cuối)
2. Xóa sinh viên khi biết mã sinh viên
3. Cập nhật thông tin của sinh viên khi biết mã
4. Hiển thông tin của sinh viên khi biết mã
5. In danh sách các sinh viên hiện có lên màn hình, mỗi thí sinh trên 1 dòng.

Biết mỗi sinh viên gồm các thông tin: Mã sinh viên, họ tên, năm sinh, giới tính, quê quán

Bài 6. Cài đặt lớp DblNode, lớp DoubleList, lớp bộ lặp của lớp DoubleList theo lý thuyết đã học.

IV. Ngăn xếp và hàng đợi

Bài 1. Cài đặt lớp Stack bằng danh sách liên kết đơn (các phần tử của danh sách được lưu trữ trong 1 danh sách liên kết đơn)

Bài 2. Viết chương trình cho phép nhập vào một biểu thức dạng trung tố bất kỳ. Tính giá trị của biểu thức đó.

Bài 3. Cài đặt lớp Queue bằng danh sách liên kết đơn (các phần tử của danh sách được lưu trữ trong 1 danh sách liên kết đơn)

Bài 4. Cài đặt lớp ứng dụng sử dụng lớp Queue để tổ chức lưu trữ các đối tượng là các số nguyên. Lớp có các chức năng:

1. Thêm vào Queue 1 phần tử
2. Lấy phần tử ra khỏi queue và hiển thị lên màn hình
3. Cho biết số phần tử hiện có của Queue
4. Cho biết Queue rỗng hay đầy

V. Cây

Bài 1. Cài đặt các lớp biểu diễn cấu trúc cây theo lý thuyết đã học.

Bài 2. Vẽ cây biểu diễn biểu thức sau đây

(((a+b)-c) *((45-a)/(x-y)))/(a-x)

Bài 3. Vẽ cây theo mô tả sau đây: Nút gốc là X, X có 4 con là A, B, C,D, nút con A có 2 con A 1 , A 2 , nút con B có 3 nút con M, N, K, nút K có 2 con K 1 , K 2 , nút D có 3 con D 1 , D 2 , D 3 , nút D 3 có 2 con Z, Y.

VI. Thuật toán tìm sắp xếp

Bài 1. Tìm hiểu lý thuyết cách xây dựng hàm có đối là hàm và hoàn thành cài đặt mã trong ví dụ vào máy.

Lý thuyết

Như chúng ta đã biết, khi xây dựng các hàm thì đối của nó có thể là con trỏ/tham chiếu (cần truyền địa chỉ khi gọi hàm), tham trị (cần truyền giá trị khi gọi hàm). Vậy có khi nào chúng ta cần truyền một hàm vào trong hàm không? Câu trả lời là có, ví dụ bài toán sắp xếp. Giả sử bạn được đưa cho 1 yêu cầu: hãy xây dựng một hàm sắp xếp một dãy phần tử bất kỳ bằng một thuật toán sắp xếp nào đó chẳng hạn thuật toán sắp xếp Bubble sort. Thuật toán sắp xếp thì bạn đã biết, tuy nhiên để sắp xếp các thuật toán cần phải so sánh các phần tử với nhau. Với yêu cầu của bài toán là sắp xếp dãy các phần tử bất kỳ thì chúng ta không thể sử dụng các phép so sánh hông thường >, < để so sánh được. Ví dụ các phần tử cần sắp là các thí sinh, khi đó với hai thí sinh x, y ta không thể viết x>y. Chúng ta không thể so sánh 2 thí sinh với nhau, nhưng chúng ta có thể so sánh trên một thuộc tính nào đó chẳng như họ tên của thí sinh hoặc năm sinh, ..... Khi sắp xếp các thí sinh thì chúng chỉ có thể sắp xếp dựa trên một thuộc tính nào đó. Để xây dựng hàm sắp xếp các phần tử bất kỳ thì chúng ta cần truyền vào cho hàm một hàm so sánh của đối tượng dữ liệu cần sắp. Hàm này thực hiện so sánh trên 1 thuộc tính nào đó của tập dữ liệu mà ta cần sắp xếp.

Khai báo hàm có đối là hàm hay con trỏ hàm Type1 Tên_hàm([Danh sách đối],Type2 (*Tên_con_trỏ_hàm) ([Type3,])

{ Code }

Ví dụ: Cài đặt các thuật toán sắp xếp nổi bọt (Bubble sort)

template <class T>

friend istream & operator >>(istream &is, Student &s); friend ostream & operator <<(ostream &os, Student s); }; istream & operator >>(istream &is, Student &s) { cout<<"\nNhap ma sv:"; is>>s; cout<<"Nhap ho va ten:"; is(1); is(s,30); cout<<"Nhap gioi tinh:"; is(1); is(s,4); return is; } ostream & operator <<(ostream &os, Student s) { os<<s<<"\t"<<s<<"\t" <<s; return os; }

endif

1. Xây dựng hàm nhập, in các phần tử của mảng

ifndef ARRAY_H

define ARRAY_H 0

include"iostream"

using namespace std;

template <class T>

void InputArr(T *a, int n, char *c){

for(int i=0;i<n;i++){ cout<<c<<"["<<i<<"]="; cin>>a[i]; }

}

template <class T>

void PrintArr(T *a, int n, int xuongdong){

//xuongdong=1 thi in ra theo cot, nguoc lai in ra theo hang for(int i=0;i<n;i++)

if (xuongdong) cout<<a[i]<<"\n"; else cout<<a[i]<<" ";

}

endif

1. Xây dựng hàm so sánh, hàm main

include"conio"

include"stdio"

include"string"

include"iostream"

include"sortnn"

include"array"

include"student" using namespace std; int compare_Name(Student x, Student y){ if (strcmp(x(),y())<0) return 1; else return 0; } int main(){ Student *a; int n; system("cls"); cout<<"Nhap so sinh vien n="; cin>>n; a = new Student[n]; InputArr(a, n, "Nhap SV thu "); system("cls"); cout<<"Danh sach sinh vien:\n"; BubbleSort(a,n,compare_Name); cout<<"\nDanh sach sinh vien sau khi sap xep:\n"; PrintArr(a,n,1); getch(); return 0; }

Bài 2. Cài đặt các hàm sắp xếp một mảng các phần tử bất kỳ bằng các thuật toán sắp xếp chọn (Selecton Sort), thuật toán sắp xếp chèn (Insertion Sort), sắp xếp nhanh (Quick Sort), sắp xếp trộn (Merge Sort), sắp xếp vun đống (Heap Sort).