ĐỀ BÀI
Đệ Quy
Trong lý thuyết đệ quy, chúng ta có thể chọn bài toán tính giai thừa Giai thừa của một số nguyên dương n, ký hiệu là n!, được định nghĩa là n! = n × (n-1)! với điều kiện dừng là 0! = 1 Ví dụ, để tính 5!, chúng ta có các bước gọi đệ quy như sau: 5! = 5 × 4!, 4! = 4 × 3!, 3! = 3 × 2!, 2! = 2 × 1!, và 1! = 1 Cây đệ quy sẽ có cấu trúc như sau: ở đỉnh là 5!, nhánh bên trái là 4!, tiếp theo là 3!, 2!, và cuối cùng là 1! Qua đó, ta thấy rõ tính chất đệ quy trong việc tính toán giai thừa.
• Giải bài toán tính tổng các chữ số của một số nguyên dương gồm chữ ii Nhóm 2: số.
• Giải bài toán tính số fibonacci thứ
Để giải bài toán tính tổ hợp chập và tìm số lớn nhất trong một mảng, bạn cần tạo một lớp trong ngôn ngữ lập trình mà bạn đang sử dụng Sử dụng đệ quy để định nghĩa mã cho hai ví dụ đã chọn và đảm bảo rằng bạn có một phương thức main() để kiểm tra kết quả Việc này không chỉ giúp bạn thực hành kỹ năng lập trình mà còn củng cố kiến thức về tổ hợp và xử lý mảng.
Sắp xếp
Sinh viên cần tạo một mảng số nguyên gồm 10 phần tử với thứ tự ngẫu nhiên, không được sắp xếp trước Để thực hiện việc sắp xếp, sinh viên sẽ chọn 02 trong 03 thuật toán: Bubble Sort, Insertion Sort hoặc Selection Sort, và trình bày từng bước sắp xếp, thể hiện rõ sự thay đổi của các phần tử trong mảng Ngoài ra, sinh viên cũng cần áp dụng 01 trong 02 thuật toán Merge Sort hoặc Quick Sort, đồng thời minh họa quá trình sắp xếp với từng bước thay đổi của các phần tử trong mảng.
Giải thuật sử dụng Stack để chuyển đổi biểu thức từ dạng trung tố sang dạng hậu tố (Reverse Polish notation - RPN) bắt đầu bằng việc quét qua biểu thức, phân tích các toán hạng và toán tử, đồng thời quản lý các dấu ngoặc Ví dụ, với biểu thức infix: (3 + 5) * (2 - 4) / 2, ta sẽ chuyển đổi thành hậu tố: 3 5 + 2 4 - * 2 / Để tính toán kết quả từ biểu thức postfix, giải thuật sử dụng Stack sẽ thực hiện bằng cách đẩy các toán hạng vào Stack và khi gặp toán tử, sẽ lấy các toán hạng từ Stack để thực hiện phép toán và đẩy kết quả trở lại Áp dụng cho biểu thức postfix trên, ta sẽ tính toán để có kết quả cuối cùng.
IV Cấu trúc dữ liệu Danh sách và Cây
Bài viết phân tích quản lý sinh viên thông qua ba cấu trúc dữ liệu: Mảng (Array), Danh sách liên kết (Linked List) và Cây AVL Mỗi cấu trúc dữ liệu có những ưu điểm và nhược điểm riêng, ảnh hưởng đến hiệu suất trong các thao tác cụ thể Đối với việc thêm một sinh viên mới, Mảng có thể gặp khó khăn khi kích thước cố định, trong khi Danh sách liên kết và Cây AVL cho phép thêm linh hoạt hơn Khi xóa sinh viên, Danh sách liên kết có thể thực hiện nhanh chóng mà không cần dịch chuyển dữ liệu, nhưng Cây AVL giữ được sự cân bằng tốt hơn Cuối cùng, trong thao tác tìm kiếm, Cây AVL thường cho kết quả nhanh nhất nhờ vào cấu trúc tự cân bằng, trong khi Mảng và Danh sách liên kết có thể tốn thời gian hơn.
Cài đặt bài toán sử dụng Linked List và cây AVL (không dùng thư viện) với ít nhất 15 đối tượng sinh viên, mỗi sinh viên có mã số (8 ký tự, ký tự đầu có thể là chữ cái), họ tên, điểm trung bình tích lũy và 2 thuộc tính tự chọn Cần hiện thực các thao tác: thêm sinh viên mới, xóa sinh viên, và tìm kiếm thông tin theo mã số sinh viên, trong đó cây AVL lưu trữ theo mã số sinh viên.
Để xây dựng đồ thị biểu diễn người dùng cho một mạng xã hội, mỗi người dùng cần có các thông tin cơ bản như mã người dùng, tên người dùng, số tuổi, giới tính và nghề nghiệp Những thông tin này không chỉ giúp xác định danh tính người dùng mà còn hỗ trợ trong việc phân tích và tối ưu hóa trải nghiệm người dùng trên nền tảng.
Để xây dựng đồ thị, hãy vẽ đồ thị với các đỉnh được ký hiệu bằng mã người dùng, trong đó mỗi người dùng kết bạn với nhau sẽ được biểu diễn bằng các cạnh nối giữa hai đỉnh Đồ thị cần có ít nhất 30 đỉnh và 50 cạnh, có thể bao gồm một số đỉnh cô lập Sau đó, thực hiện duyệt đồ thị bằng thuật toán BFS và DFS, bắt đầu từ một đỉnh sinh viên tự chọn, để thu được kết quả duyệt.
Sinh viên cần tự tạo một file text, sau đó đọc nội dung file và biểu diễn dữ liệu dưới dạng đồ thị Có thể sử dụng các cấu trúc như ma trận kề, danh sách kề hoặc danh sách cạnh để thực hiện việc này.
Để viết phương thức trả về danh sách bạn bè của một người dùng, bạn cần xác định tài khoản người dùng đó và truy xuất thông tin bạn bè từ cơ sở dữ liệu Đối với phương thức xác định số lượng bạn chung giữa hai tài khoản, bạn sẽ so sánh danh sách bạn bè của cả hai tài khoản và đếm số lượng bạn bè chung.
PHẦN 2 - PHÂN TÍCH VÀ GIẢI QUYẾT YÊU CẦU
Lũy thừa bật 0 của một số bất kỳ thì bằng 1 Áp dụng điều này ta có được điều kiện dừng của chương trình đệ quy là: if (y == 0) return 1;
Tùy theo giá trị của y mà biểu thức đệ quy có thể khác nhau Các trường hợp có thể xảy ra đối với y:
Biểu thức đệ quy lúc này sẽ là:
Kết quả chạy của chương trình sẽ được biểu diễn ở cây đệ quy sau:
Trình tự thực hiện như sau:
Đệ quy lần 1: int S(int 2, int 5) //(int x, int y){ if (5 == 0) // false return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,4); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Đệ quy lần 2: int S(int 2, int 4) //(int x, int y){ if (4 == 0) // false return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,3); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return if (3 == 0) // false
10 return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,2); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Đệ quy lần 4: int S(int 2, int 2) //(int x, int y){ if (2 == 0) // false return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,1); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Đệ quy lần 5: int S(int 2, int 1) //(int x, int y){ if (1 == 0) // false return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,0); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Đệ quy lần 6: int S(int 2, int 0) //(int x, int y){ if (0 == 0) // true return 1; // thực hiện lệnh return
//Không thực hiện các lệnh bên dưới if (y > 0) // false return 2*S(2,0); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Sau khi chương trình gặp điều kiện dừng tại lần gọi đệ quy thứ 6, kết quả của phép toán như sau:
Kết quả của chương trình được biểu diễn ở cây đệ quy sau:
Trình tự thực hiện như sau:
Đệ quy lần 1 là một hàm S nhận hai tham số int x và int y Trong hàm, nếu y bằng 0, hàm sẽ trả về 1, nhưng điều này không xảy ra trong trường hợp này Nếu y lớn hơn 0, hàm sẽ trả về 2*S(x, y-1), nhưng cũng không thực hiện lệnh này vì y không lớn hơn 0 Cuối cùng, nếu y nhỏ hơn 0, hàm sẽ trả về 1 nhân với x và 0.
Đệ quy lần 2 là một hàm S với hai tham số int x và int y, trong đó S(2, -4) được gọi Điều kiện đầu tiên kiểm tra nếu y bằng 0, nhưng điều này không đúng, vì vậy lệnh return không được thực hiện Tiếp theo, hàm kiểm tra nếu y lớn hơn 0, nhưng điều này cũng không đúng, do đó lệnh return lại không được thực hiện Cuối cùng, với điều kiện y nhỏ hơn 0, hàm sẽ trả về giá trị 1 nhân với x và 0, dẫn đến kết quả cuối cùng của hàm.
Đệ quy lần 3 là một hàm S với hai tham số x và y Trong hàm này, điều kiện đầu tiên kiểm tra xem y có bằng 0 hay không, nhưng điều này không đúng, do đó lệnh return không được thực hiện Tiếp theo, điều kiện kiểm tra y có lớn hơn 0 hay không cũng sai, vì vậy lệnh return lại không được thực hiện Cuối cùng, khi kiểm tra y có nhỏ hơn 0, điều này đúng và hàm trả về giá trị 1 nhân với x.0.
Đệ quy lần 4: int S(int 2, int -2) //(int x, int y){ if (-2 == 0) // false return 1; //không thực hiện lệnh return trong if
13 if (y > 0) // fasle return 2*S(x, y-1); // không thực hiện lệnh return trong if if (y < 0) // true return 1 x.0
Đệ quy lần 5 là một hàm S nhận hai tham số x và y Nếu y bằng -1, điều kiện trong câu lệnh if đầu tiên không đúng nên không thực hiện lệnh return Khi y lớn hơn 0, điều kiện cũng không đúng, dẫn đến việc không thực hiện lệnh return thứ hai Cuối cùng, khi y nhỏ hơn 0, điều kiện này đúng và hàm trả về giá trị 1 nhân với 0.
Đệ quy lần 6: int S(int 2, int 0) //(int x, int y)
{ if (0 == 0) // true return 1; //thực hiện lệnh return //Không thực hiện các lệnh bên dưới if (y > 0) // fasle return 2*S(x, y-1); // không thực hiện lệnh return trong if if (y < 0) // false return 1 x.0
*S(x, y + 1); //Không thực hiện lệnh return }
Sau khi chương trình gặp điều kiện dừng tại lần gọi đệ quy thứ 6, kết quả của phép toán như sau:
Tính chất của tổ hơp:
Dựa vào các tính chất trên ta thấy:
Khi: o k = 0 hoặc k = n thì C k n = 1 if (k == 0 || k == n) return 1; o k = 1 thì C k n = n if (k == 1) return n;
Tính dừng của đệ quy
Kết quả chạy của chương trình được biểu diễn ở cây đệ quy sau: return 1
Trình tự thực hiện của chương trình như sau: int C(5,4) // (int n, int k) { if (4 == 0 || 4 == 5) // (k == 0 || k == n) false return 1;
không thực thi if if (4 == 1) // (k == 1) false return 5; // return n
không thực thi if return C(4,4) + C(4,3); // C(n-1, k) + C(n-1, k-1) //Gọi đệ quy
} int C(4,4) // (int n, int k) { if (4 == 0 || 4 == 4) // (k == 0 || k == n) true return 1;
thực thi if if (4 == 1) // (k == 1) false return 4; // return n
không thực thi if return C(n-1, k) + C(n-1, k-1) //Không thực hiện gọi đệ quy } int C(4,3) // (int n, int k) { if (3 == 0 || 3 == 4) // (k == 0 || k == n) false return 1;
không thực thi if if (3 == 1) // (k == 1) false return 4; // return n
không thực thi if return C(3,3) + C(3,2); // C(n-1, k) + C(n-1, k-1) //Gọi đệ quy
} int C(3,3) // (int n, int k) { if (3 == 0 || 3 == 3) // (k == 0 || k == n) true return 1;
thực thi if if (3 == 1) // (k == 1) false return 3; // return n
không thực thi if return C(n-1, k) + C(n-1, k-1)
//không thực hiện gọi đệ quy
} int C(3,2) // (int n, int k) { if (2 == 0 || 2 == 3) // (k == 0 || k == n) false return 1;
không thực thi if if (2 == 1) // (k == 1) false return 3; // return n
không thực thi if return C(2,2) + C(2,1); // C(n-1, k) + C(n-1, k-1) //Gọi đệ quy
} int C(2,2) // (int n, int k) { if (2 == 0 || 2 == 2) // (k == 0 || k == n) true return 1;
thực thi if if (2 == 1) // (k == 1) false return 2; // return n
không thực thi if return C(n-1, k) + C(n-1, k-1) //không thực hiện gọi đệ quy } int C(2,1) // (int n, int k) { if (1 == 0 || 1 == 2) // (k == 0 || k == n) false return 1;
không thực thi if if (1 == 1) // (k == 1) true return 2; // return n
thực thi if return C(n-1, k) + C(n-1, k-1) //không thực hiện gọi đệ quy }
Kết quả của chương trình như sau:
1.2 Thực hành public class Cau1 { public static double Xy(int x, int y) { if (y == 0) return 1; if (y > 0) return x*Xy(x, y-1); else return (1.0/x)*Xy(x, y+1);
} public static int C(int n, int k) { if (k == 0 || k == n) return 1; if (k == n) return n; return C(n-1, k) + C(n-1, k-1);
} public static void main(String[] args) { System.out.println("2^5 " + (int)Xy(2,5)); System.out.println("2^(-5) = " + Xy(2,- 5)); System.out.println("To ho chap 4 cua 6 phan tu 6C4
2.1 Khởi tạo mảng gồm 10 phần tử:
Bắt đầu từ đầu hoặc cuối mảng, ta di chuyển phần tử nhỏ nhất hoặc lớn nhất đến vị trí đầu tiên hoặc cuối cùng của mảng và không xem xét phần tử đó nữa Sau đó, mảng còn lại n-1 phần tử từ mảng ban đầu, và ta tiếp tục xử lý phần tử thứ hai của mảng.
Các bước thực hiện như sau:
- Màu vàng biểu thị cho số nhỏ nhất tìm được.
- Màu cam biểu thị cho phần tử cần đổi chỗ.
- Màu xanh biểu thị cho dãy đã sắp xếp.
Bước 1: Tìm phần tử nhỏ nhất từ a[0] tới a[9] và đổi chỗ nó với a[0] Ở đây, ta thấy a[2] = 1 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[0].
Bước 2: Tìm phần tử nhỏ nhất từ a[1] tới a[9] và đổi chỗ nó với a[1] Ở đây, ta thấy a[8] = 2 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[1].
Bước 3: Tìm phần tử nhỏ nhất từ a[2] tới a[9] và đổi chỗ nó với a[2] Ở đây, ta thấy a[5] = 4 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[2].
Bước 4: Tìm phần tử nhỏ nhất từ a[3] tới a[9] và đổi chỗ nó với a[3] Ở đây, ta thấy a[8] = 5 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[3].
Bước 5: Tìm phần tử nhỏ nhất từ a[4] tới a[9] và đổi chỗ nó với a[4] Ở đây, ta thấy a[6] = 6 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[4].
Bước 6: Tìm phần tử nhỏ nhất từ a[5] tới a[9] và đổi chỗ nó với a[5] Ở đây, ta thấy a[7] = 9 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[5].
1Bước 7: Tìm phần tử nhỏ nhất từ a[6] tới a[9] và đổi chỗ nó với a[6] Ở đây, ta thấy a[7] = 10 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[6].
Bước 8: Tìm phần tử nhỏ nhất từ a[7] tới a[9] và đổi chỗ nó với a[7] Ở đây, ta thấy a[8] = 13 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[7].
Bước 9: Ta thấy a[8] = 20 > a[9] = 14 Tiến hành đổi chỗ cho nhau.
Bước 10: a[9] là phần tử cuối cùng của mảng, vậy nên đã sắp xếp xong mảng. Kết quả như sau:
Hoán đổi vị trí của hai số liền kề nếu chúng không đúng thứ tự, với số sau nhỏ hơn số trước trong trường hợp sắp xếp tăng dần, cho đến khi dãy số được sắp xếp hoàn chỉnh Thuật toán này sử dụng một biến cờ hiệu để kiểm tra xem có sự thay đổi vị trí trong mảng hay không; nếu không còn sự thay đổi, chương trình sẽ kết thúc.
Các bước thực hiện: Lần 1: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 10 > 5 nên đổi chỗ cho nhau, flag = false.
- So sánh a[1] và a[2] thấy 10 > 1 nên đổi chỗ cho nhau, flag = false.
- So sánh a[2] và a[3] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[3] và a[4] thấy 13 < 20 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 4 < 20 nên đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 6 < 20 nên đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 9 < 20 nên đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 2 < 20 nên đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 1:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 2.
Lần 2: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 > 5 nên đổi chỗ cho nhau, flag = false.
- So sánh a[1] và a[2] thấy 5 < 10 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[2] và a[3] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[3] và a[4] thấy 4 < 13 nên đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 6 < 13 nên đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 9 < 13 nên đổi chỗ cho nhau flag = false.
- So sánh a[6] và a[7] thấy 2 < 13 nên đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 2:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 3.
Lần 3: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 5 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[1] và a[2] thấy 5 < 10 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[2] và a[3] thấy 4 < 10 nên đổi chỗ cho nhau, flag = false.
- So sánh a[3] và a[4] thấy 6 < 10 nên đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 9 < 10 nên đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 9 < 13 nên đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 3:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 4.
Lần 4: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 5 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[1] và a[2] thấy 4 < 5 nên đổi chỗ cho nhau, flag = false.
- So sánh a[2] và a[3] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[3] và a[4] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 2 < 9 nên đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 4:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 5.
Lần 5: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 4 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[1] và a[2] thấy 4 < 5 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[2] và a[3] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[3] và a[4] thấy 2 < 6 nên đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = flase.
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
14526910131420 - So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 5:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 4.
Lần 6: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 4 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[3] và a[4] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false. 1
- Kết quả so sánh lần 6:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 7.
Lần 7: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 4 nên không đổi chỗ cho nhau, flag = true. 1
- So sánh a[1] và a[2] thấy 2 < 4 nên đổi chỗ cho nhau, flag = false.
- So sánh a[2] và a[3] thấy 4 < 5 nên không đổi chỗ cho nhau, flag = false. 1
- So sánh a[3] và a[4] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = false. 1
- So sánh a[4] và a[5] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = false. 1
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = false.1
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false. 1
- Kết quả so sánh lần 7:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 8.
Lần 8: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 2 nên không đổi chỗ cho nhau, flag = true. 1
- So sánh a[1] và a[2] thấy 2 < 4 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[2] và a[3] thấy 4 < 5 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[3] và a[4] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[4] và a[5] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = true.
- Kết quả so sánh lần 8:
Vì không xuất hiện sự thay đổi vị trí các phần tử trong mảng nên flag = true Kết thúc chương trình. b) Merge Sort
Chia mảng thành hai phần: bên phải và bên trái Tiếp tục chia mỗi bên thành hai cho đến khi mỗi mảng chỉ còn một phần tử Sau đó, tiến hành sắp xếp và gộp các mảng lại, tạo ra mảng đã được sắp xếp với đầy đủ số phần tử như mảng ban đầu.
Các bước thực hiện như sau:
- Chia mảng trên thành 2 nữa, ta thu được 2 mảng con như bên dưới 4 6 9 2 14
- Tiếp tục chia từng mảng thành 2 mảng con, ta sẽ thu được 4 mảng con mới.
- Lần nữa chia các mảng thành 2 mảng con ta thu được các mảng như sau.
- Chia mảng lần cuối ta thu được các mảng con chứa 1 phần tử.
- Sau đó ta tiến hành sắp xếp và gộp các mảng lại với nhau.
- Tiếp tục sắp xếp và gộp thành 2 mảng 4 phần tử và 1 mảng 2 phần tử.
- Tiếp tục sắp xếp và gộp 2 mảng 4 phần tử lại với nhau.
- Ta tiến hành gộp và sắp xếp lần cuối để thu được mảng đã được sắp xếp gồm
Cấu trúc dữ liệu Danh sách và Cây
Bài viết phân tích bài toán quản lý sinh viên thông qua ba cấu trúc dữ liệu: Mảng (Array), Danh sách liên kết (Linked List) và Cây AVL Mỗi cấu trúc dữ liệu có những ưu điểm và nhược điểm riêng, ảnh hưởng đến hiệu suất trong các thao tác quản lý sinh viên Cụ thể, việc thêm một sinh viên mới có thể thực hiện nhanh chóng với Mảng nhưng gặp khó khăn khi phải mở rộng kích thước, trong khi Danh sách liên kết cho phép thêm dễ dàng nhưng tốn thời gian tìm kiếm vị trí Đối với thao tác xóa sinh viên, Cây AVL mang lại hiệu suất tốt hơn nhờ khả năng duy trì cân bằng, trong khi Mảng và Danh sách liên kết có thể gặp khó khăn do phải dịch chuyển các phần tử Cuối cùng, việc tìm kiếm sinh viên cho thấy Cây AVL có ưu thế vượt trội với thời gian tìm kiếm logarit, so với Mảng và Danh sách liên kết, nơi thời gian tìm kiếm có thể lên tới tuyến tính.
Cài đặt bài toán sử dụng Linked List và cây AVL mà không cần thư viện, với ít nhất 15 đối tượng sinh viên Mỗi sinh viên có mã số (8 ký tự, ký tự đầu có thể là chữ), họ tên, điểm trung bình tích lũy và hai thuộc tính tự chọn Cần hiện thực các thao tác: thêm sinh viên mới, xóa sinh viên và tìm kiếm thông tin theo mã số sinh viên, trong đó cây AVL lưu trữ theo mã số sinh viên.
PHÂN TÍCH VÀ GIẢI QUYẾT YÊU CẦU
Đệ quy
Lũy thừa bật 0 của một số bất kỳ thì bằng 1 Áp dụng điều này ta có được điều kiện dừng của chương trình đệ quy là: if (y == 0) return 1;
Tùy theo giá trị của y mà biểu thức đệ quy có thể khác nhau Các trường hợp có thể xảy ra đối với y:
Biểu thức đệ quy lúc này sẽ là:
Kết quả chạy của chương trình sẽ được biểu diễn ở cây đệ quy sau:
Trình tự thực hiện như sau:
Đệ quy lần 1: int S(int 2, int 5) //(int x, int y){ if (5 == 0) // false return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,4); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Đệ quy lần 2: int S(int 2, int 4) //(int x, int y){ if (4 == 0) // false return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,3); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return if (3 == 0) // false
10 return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,2); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Đệ quy lần 4: int S(int 2, int 2) //(int x, int y){ if (2 == 0) // false return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,1); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Đệ quy lần 5: int S(int 2, int 1) //(int x, int y){ if (1 == 0) // false return 1; //không thực hiện lệnh return trong if if (y > 0) // true return 2*S(2,0); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Đệ quy lần 6: int S(int 2, int 0) //(int x, int y){ if (0 == 0) // true return 1; // thực hiện lệnh return
//Không thực hiện các lệnh bên dưới if (y > 0) // false return 2*S(2,0); // Gọi đệ quy if (y < 0) // false return 1 x.0
*S(x, y + 1); //không thực hiện lệnh return }
Sau khi chương trình gặp điều kiện dừng tại lần gọi đệ quy thứ 6, kết quả của phép toán như sau:
Kết quả của chương trình được biểu diễn ở cây đệ quy sau:
Trình tự thực hiện như sau:
Đệ quy lần 1 là một hàm S với hai tham số int x và int y Khi gọi hàm S(2, -5), điều kiện đầu tiên kiểm tra nếu y bằng 0 thì trả về 1, nhưng điều này không đúng Tiếp theo, nếu y lớn hơn 0, hàm sẽ trả về 2*S(x, y-1), nhưng cũng không thực hiện do y không lớn hơn 0 Cuối cùng, nếu y nhỏ hơn 0, hàm sẽ trả về 1 nhân với x.0.
Đệ quy lần 2 là một hàm S với hai tham số int x và int y Trong hàm này, nếu y bằng -4 thì điều kiện đầu tiên không đúng, do đó không thực hiện lệnh return 1 Tiếp theo, nếu y lớn hơn 0 thì cũng không thực hiện lệnh return 2*S(x, y-1) vì điều kiện này sai Cuối cùng, nếu y nhỏ hơn 0, hàm sẽ trả về giá trị 1 nhân với x, tức là 1*x.
Đệ quy lần 3 là một hàm có tên S với hai tham số x và y Trong hàm, điều kiện đầu tiên kiểm tra xem y có bằng 0 hay không, nhưng điều kiện này không đúng nên không thực hiện lệnh return Tiếp theo, hàm kiểm tra xem y có lớn hơn 0 hay không, điều kiện này cũng không đúng nên lại không thực hiện lệnh return Cuối cùng, hàm kiểm tra y có nhỏ hơn 0, điều kiện này đúng và hàm sẽ trả về giá trị 1 nhân với x.0.
Đệ quy lần 4: int S(int 2, int -2) //(int x, int y){ if (-2 == 0) // false return 1; //không thực hiện lệnh return trong if
13 if (y > 0) // fasle return 2*S(x, y-1); // không thực hiện lệnh return trong if if (y < 0) // true return 1 x.0
Đệ quy lần 5 là một hàm S với hai tham số nguyên x và y Trong hàm này, điều kiện đầu tiên kiểm tra nếu y bằng -1 thì không thực hiện lệnh return Nếu y lớn hơn 0, hàm sẽ không thực hiện lệnh return do điều kiện sai Cuối cùng, nếu y nhỏ hơn 0, hàm sẽ trả về giá trị 1 nhân với 0.
Đệ quy lần 6: int S(int 2, int 0) //(int x, int y)
{ if (0 == 0) // true return 1; //thực hiện lệnh return //Không thực hiện các lệnh bên dưới if (y > 0) // fasle return 2*S(x, y-1); // không thực hiện lệnh return trong if if (y < 0) // false return 1 x.0
*S(x, y + 1); //Không thực hiện lệnh return }
Sau khi chương trình gặp điều kiện dừng tại lần gọi đệ quy thứ 6, kết quả của phép toán như sau:
Tính chất của tổ hơp:
Dựa vào các tính chất trên ta thấy:
Khi: o k = 0 hoặc k = n thì C k n = 1 if (k == 0 || k == n) return 1; o k = 1 thì C k n = n if (k == 1) return n;
Tính dừng của đệ quy
Kết quả chạy của chương trình được biểu diễn ở cây đệ quy sau: return 1
Trình tự thực hiện của chương trình như sau: int C(5,4) // (int n, int k) { if (4 == 0 || 4 == 5) // (k == 0 || k == n) false return 1;
không thực thi if if (4 == 1) // (k == 1) false return 5; // return n
không thực thi if return C(4,4) + C(4,3); // C(n-1, k) + C(n-1, k-1) //Gọi đệ quy
} int C(4,4) // (int n, int k) { if (4 == 0 || 4 == 4) // (k == 0 || k == n) true return 1;
thực thi if if (4 == 1) // (k == 1) false return 4; // return n
không thực thi if return C(n-1, k) + C(n-1, k-1) //Không thực hiện gọi đệ quy } int C(4,3) // (int n, int k) { if (3 == 0 || 3 == 4) // (k == 0 || k == n) false return 1;
không thực thi if if (3 == 1) // (k == 1) false return 4; // return n
không thực thi if return C(3,3) + C(3,2); // C(n-1, k) + C(n-1, k-1) //Gọi đệ quy
} int C(3,3) // (int n, int k) { if (3 == 0 || 3 == 3) // (k == 0 || k == n) true return 1;
thực thi if if (3 == 1) // (k == 1) false return 3; // return n
không thực thi if return C(n-1, k) + C(n-1, k-1)
//không thực hiện gọi đệ quy
} int C(3,2) // (int n, int k) { if (2 == 0 || 2 == 3) // (k == 0 || k == n) false return 1;
không thực thi if if (2 == 1) // (k == 1) false return 3; // return n
không thực thi if return C(2,2) + C(2,1); // C(n-1, k) + C(n-1, k-1) //Gọi đệ quy
} int C(2,2) // (int n, int k) { if (2 == 0 || 2 == 2) // (k == 0 || k == n) true return 1;
thực thi if if (2 == 1) // (k == 1) false return 2; // return n
không thực thi if return C(n-1, k) + C(n-1, k-1) //không thực hiện gọi đệ quy } int C(2,1) // (int n, int k) { if (1 == 0 || 1 == 2) // (k == 0 || k == n) false return 1;
không thực thi if if (1 == 1) // (k == 1) true return 2; // return n
thực thi if return C(n-1, k) + C(n-1, k-1) //không thực hiện gọi đệ quy }
Kết quả của chương trình như sau:
1.2 Thực hành public class Cau1 { public static double Xy(int x, int y) { if (y == 0) return 1; if (y > 0) return x*Xy(x, y-1); else return (1.0/x)*Xy(x, y+1);
} public static int C(int n, int k) { if (k == 0 || k == n) return 1; if (k == n) return n; return C(n-1, k) + C(n-1, k-1);
} public static void main(String[] args) { System.out.println("2^5 " + (int)Xy(2,5)); System.out.println("2^(-5) = " + Xy(2,- 5)); System.out.println("To ho chap 4 cua 6 phan tu 6C4
2.1 Khởi tạo mảng gồm 10 phần tử:
Bắt đầu từ đầu (hoặc cuối) mảng, chúng ta di chuyển phần tử nhỏ nhất (hoặc lớn nhất) về vị trí đầu tiên (hoặc cuối cùng) và loại bỏ phần tử đó khỏi quá trình xét Sau đó, mảng còn lại sẽ có n-1 phần tử, và chúng ta tiếp tục xem xét phần tử thứ hai trong mảng.
Các bước thực hiện như sau:
- Màu vàng biểu thị cho số nhỏ nhất tìm được.
- Màu cam biểu thị cho phần tử cần đổi chỗ.
- Màu xanh biểu thị cho dãy đã sắp xếp.
Bước 1: Tìm phần tử nhỏ nhất từ a[0] tới a[9] và đổi chỗ nó với a[0] Ở đây, ta thấy a[2] = 1 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[0].
Bước 2: Tìm phần tử nhỏ nhất từ a[1] tới a[9] và đổi chỗ nó với a[1] Ở đây, ta thấy a[8] = 2 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[1].
Bước 3: Tìm phần tử nhỏ nhất từ a[2] tới a[9] và đổi chỗ nó với a[2] Ở đây, ta thấy a[5] = 4 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[2].
Bước 4: Tìm phần tử nhỏ nhất từ a[3] tới a[9] và đổi chỗ nó với a[3] Ở đây, ta thấy a[8] = 5 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[3].
Bước 5: Tìm phần tử nhỏ nhất từ a[4] tới a[9] và đổi chỗ nó với a[4] Ở đây, ta thấy a[6] = 6 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[4].
Bước 6: Tìm phần tử nhỏ nhất từ a[5] tới a[9] và đổi chỗ nó với a[5] Ở đây, ta thấy a[7] = 9 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[5].
1Bước 7: Tìm phần tử nhỏ nhất từ a[6] tới a[9] và đổi chỗ nó với a[6] Ở đây, ta thấy a[7] = 10 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[6].
Bước 8: Tìm phần tử nhỏ nhất từ a[7] tới a[9] và đổi chỗ nó với a[7] Ở đây, ta thấy a[8] = 13 là phần tử nhỏ nhất, tiến hành đổi chỗ với a[7].
Bước 9: Ta thấy a[8] = 20 > a[9] = 14 Tiến hành đổi chỗ cho nhau.
Bước 10: a[9] là phần tử cuối cùng của mảng, vậy nên đã sắp xếp xong mảng. Kết quả như sau:
Hoán đổi vị trí của hai số liên tiếp nếu chúng không đúng thứ tự trong dãy số, với điều kiện số sau nhỏ hơn số trước trong sắp xếp tăng dần Thuật toán này sử dụng một biến cờ hiệu để kiểm tra xem có sự thay đổi vị trí trong mảng hay không; nếu không còn sự thay đổi, chương trình sẽ kết thúc.
Các bước thực hiện: Lần 1: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 10 > 5 nên đổi chỗ cho nhau, flag = false.
- So sánh a[1] và a[2] thấy 10 > 1 nên đổi chỗ cho nhau, flag = false.
- So sánh a[2] và a[3] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[3] và a[4] thấy 13 < 20 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 4 < 20 nên đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 6 < 20 nên đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 9 < 20 nên đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 2 < 20 nên đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 1:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 2.
Lần 2: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 > 5 nên đổi chỗ cho nhau, flag = false.
- So sánh a[1] và a[2] thấy 5 < 10 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[2] và a[3] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[3] và a[4] thấy 4 < 13 nên đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 6 < 13 nên đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 9 < 13 nên đổi chỗ cho nhau flag = false.
- So sánh a[6] và a[7] thấy 2 < 13 nên đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 2:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 3.
Lần 3: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 5 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[1] và a[2] thấy 5 < 10 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[2] và a[3] thấy 4 < 10 nên đổi chỗ cho nhau, flag = false.
- So sánh a[3] và a[4] thấy 6 < 10 nên đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 9 < 10 nên đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 9 < 13 nên đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 3:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 4.
Lần 4: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 5 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[1] và a[2] thấy 4 < 5 nên đổi chỗ cho nhau, flag = false.
- So sánh a[2] và a[3] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[3] và a[4] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 2 < 9 nên đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 4:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 5.
Lần 5: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 4 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[1] và a[2] thấy 4 < 5 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[2] và a[3] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[3] và a[4] thấy 2 < 6 nên đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = flase.
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
14526910131420 - So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false.
- Kết quả so sánh lần 5:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 4.
Lần 6: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 4 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[3] và a[4] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[4] và a[5] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false. 1
- Kết quả so sánh lần 6:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 7.
Lần 7: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 4 nên không đổi chỗ cho nhau, flag = true. 1
- So sánh a[1] và a[2] thấy 2 < 4 nên đổi chỗ cho nhau, flag = false.
- So sánh a[2] và a[3] thấy 4 < 5 nên không đổi chỗ cho nhau, flag = false. 1
- So sánh a[3] và a[4] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = false. 1
- So sánh a[4] và a[5] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = false. 1
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = false.1
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = false.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = false. 1
- Kết quả so sánh lần 7:
Vì flag = false nghĩa là có sự xuất hiện thay đổi vị trí các phần tử nên tiếp tục so sánh lần 8.
Lần 8: Đặt biến cờ hiệu: flag = true
- So sánh a[0] và a[1] thấy 1 < 2 nên không đổi chỗ cho nhau, flag = true. 1
- So sánh a[1] và a[2] thấy 2 < 4 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[2] và a[3] thấy 4 < 5 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[3] và a[4] thấy 5 < 6 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[4] và a[5] thấy 6 < 9 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[5] và a[6] thấy 9 < 10 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[6] và a[7] thấy 10 < 13 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[7] và a[8] thấy 13 < 14 nên không đổi chỗ cho nhau, flag = true.
- So sánh a[8] và a[9] thấy 14 < 20 nên không đổi chỗ cho nhau, flag = true.
- Kết quả so sánh lần 8:
Vì không xuất hiện sự thay đổi vị trí các phần tử trong mảng nên flag = true Kết thúc chương trình. b) Merge Sort
Chia mảng thành hai phần: bên phải và bên trái Tiếp tục chia mỗi bên thành hai cho đến khi mỗi mảng chỉ còn một phần tử Sau đó, thực hiện sắp xếp các mảng và gộp chúng lại Kết quả cuối cùng là mảng đã được sắp xếp với đầy đủ số phần tử như mảng ban đầu.
Các bước thực hiện như sau:
- Chia mảng trên thành 2 nữa, ta thu được 2 mảng con như bên dưới 4 6 9 2 14
- Tiếp tục chia từng mảng thành 2 mảng con, ta sẽ thu được 4 mảng con mới.
- Lần nữa chia các mảng thành 2 mảng con ta thu được các mảng như sau.
- Chia mảng lần cuối ta thu được các mảng con chứa 1 phần tử.
- Sau đó ta tiến hành sắp xếp và gộp các mảng lại với nhau.
- Tiếp tục sắp xếp và gộp thành 2 mảng 4 phần tử và 1 mảng 2 phần tử.
- Tiếp tục sắp xếp và gộp 2 mảng 4 phần tử lại với nhau.
- Ta tiến hành gộp và sắp xếp lần cuối để thu được mảng đã được sắp xếp gồm
3.1Chuyển đổi biểu thức trung tố (Infix) sang hậu tố (postfix) Đặt mảng postFix[] để lưu kết quả của biểu thức hậu tố và cấu trúc dữ liệu
Stack để lưu các toán tử.
Giả sử ta có một biểu thức A = a + b * (c – d) (dạng Infix)
Bước 1: Ta bắt đầu đọc từ trái sang phải Gọi phần tử đọc được trong biểu thức là s Khi đó sẽ xảy ra các trường hợp sau:
Nếu s là toán hạng thì đưa vào mảng postfix.
Nếu s là dấu ‘)’ thì đưa vào Stack.
Nếu s là các phép toán +, -, *, / thì thực hiện các bước sau: o Xét phần tử s1 ở đỉnh Stack
Nếu s1 có độ ưu tiên lớn hơn hoặc bằng s, thì pop phần tử khỏi Stack và đưa vào mảng postfix, sau đó đưa s vào Stack.
Nếu s1 có độ ưu tiên nhỏ hơn s thì đưa s vào Stack.
Khi gặp dấu ‘)’, chúng ta sẽ lần lượt pop các phần tử từ đỉnh Stack và thêm vào postfix cho đến khi gặp dấu ‘(’ Lúc này, chúng ta sẽ pop dấu ‘(’ ra khỏi Stack mà không đưa nó vào postfix và dừng lại.
Bước 2: Lặp lại bước 1 cho đến khi nào đọc hết biểu thức A và đưa các phần tử vào mảng postFix cho đến khi Stack rỗng.
Ví dụ: Chuyển biểu thức 10 + (2 * (9 – 1) + 3) – 1/3 sang biểu thức hậu tố. s Stack
3.2 Tính biểu thức hậu tố (postfix)
Sau khi có mảng postFix chứa các phần tử của biểu thức hậu tố, chúng ta sẽ tiến hành các bước để tính giá trị của biểu thức.
Bước 1: Duyệt lần lượt các phần tử của mảng (từ trái sang phải), gọi x là phần tử đọc được
Nếu x là toán hạng thì đưa vào Stack.
Nếu x là toán tử thì pop 2 phần tử đầu tiên ở đỉnh Stack để thực hiện phép toán tương ứng, sau khi thu được kết quả thì push vào Stack.
Để tính giá trị của biểu thức, bạn cần lặp lại bước 1 cho đến khi chỉ còn lại một phần tử duy nhất trên đỉnh Stack Phần tử này chính là giá trị của biểu thức cần tính, ví dụ như biểu thức postFix "10291-*3++13/".
10 là toán hạng nên đưa vào Stack
Sau khi tính hết các phần tử của biểu thức postFix ta thu được kết quả của biểu thức: 10 + (2 * (9 – 1) + 3) – 1/3 là 86/3
IV Cấu trúc dữ liệu Danh sách và Cây
Thêm Khi thêm vào phải tái cấu mảng.
Cái với nhau bằng con trỏ, nên khi thêm node danh cần tạo một node mới
Linked giá trị con trỏ của
List node bằng node cần thêm
AVL Khi thêm 1 node vào khiến cây mất cân bằng và phải thực hiện tái cấu trúc lại cây
4.2.1 Cài đặt code bằng Linked List public interface LinkedListInterface { public void add(E item); public void remove(E s); public E findStudent(String studentID); public void print();
} import java.util.NoSuchElementException; public class MLinkedList implements LinkedListInterface
{ private Node head; private int n; public MLinkedList() { head = null; n = 0;
@Override public void add(E item) {
Node node = new Node (item); if(head == null) head = node; else {
Node temp = head; while (temp.getNext() != null) temp = temp.getNext(); temp.setNext(node);
Node currNode = head, prevNode = null; if (head == null) throw new NoSuchElementException("Can't remove element from an empty list"); else if (s == head.getData()) { head = head.getNext();
} else { while (currNode != null) { if (currNode.getData() == s) prevNode.setNext(currNode.getNext()); prevNode = currNode; currNode = currNode.getNext();
@Override public E findStudent(String studentID) throws NoSuchElementException{
Node currNode = head; while (currNode != null) {
Student temp = (Student) currNode.getData(); if (temp.getStudentID().equals(studentID)) return currNode.getData(); currNode = currNode.getNext();
} throw new NoSuchElementException("Can't find student"); }
Node temp = head; if (head == null) System.out.print("List is empty"); else { while (temp != null) {
System.out.println( temp.getData().toString()); temp = temp.getNext();
} public class Node { private E data; private Node next; public Node() {} public Node(E data) { this(data, null);
} public Node(E data, Node next) { this.data = data; this.next = next;
} public Node getNext() { return next;
} public void setNext(Node n) { next = n;
The `Student` class represents a student with attributes such as student ID, name, GPA, hometown, and age It includes a constructor that initializes these properties, allowing for the creation of a student object with specific details.
} public String getStudentID() { return studentID;
} public void setStudentID(String s) { studentID = s;
} public String getName() { return name;
} public void setName(String n) { name = n;
} public double getGPA() { return GPA;
} public void setGPA(int gpa) {
} public String getHomeTown() { return homeTown;
} public void setHomeTown(String ht) { homeTown = ht;
} public int getAge() { return age;
} public void setAge(int a) { age = a;
@Override public String toString() { return "Student [" + studentID + ", " + name + ", " + homeTown + ", " + age + ", " + GPA + "]";
} public class TestLL { public static void main(String[] args) { MLinkedList mLL = new MLinkedList(); Student a = new
Student b = new Student("00000002", "Bao", 10, "Phu Yen",19);
Student c = new Student("00000003", "Canh", 5, "Ha Tinh", 19);
Student d = new Student("00000004", "Dong", 9, "HCM", 19); Student e = new Student("00000005", "Duy", 6.1, "Ha Noi", 19);
Student f = new Student("00000006", "Nguyen", 8.4, "Yen Bai", 19);
Student g = new Student("00000007", "Long", 7.1, "Can Tho", 19);
Student h = new Student("00000008", "Hieu", 2.2, "HCM", 19); Student i = new Student("00000009", "Ha", 9.2, "Da Nang", 19); Student k = new Student("000000010", "Kien", 7.8, "Khanh Hoa", 19);
Student l = new Student("000000011", "Linh", 5.0, "Ca Mau", 19);
Student m = new Student("000000012", "My", 7.2, "Phu Yen", 19);
Student o = new Student("000000014", "Thanh", 4.1, "Hue", 19);
In this code snippet, a new student object named "Nga" with ID "000000015" and a grade of 8.2 from Can Tho is created and added to a linked list The linked list, represented by mLL, includes multiple student entries (a through o), and upon completion of the additions, the list is printed Additionally, the student entry "g" is subsequently removed from the list.
System.out.println("Danh sach sau khi xoa sinh vien Long:
System.out.println("Sinh vien can tim: "
4.2.2 Cài đặt code bằng cây AVL public class AVL { private Node root; public AVL(){ this.root = null;
} public Node getRoot() { return root;
} public void setRoot(Node root) { this.root = root;
} public int height(Node node){ if (node == null) return -1; return node.getHeight();
} private void updateHeight(Node node) { int leftHeight height(node.getLeft()); int rightHeight height(node.getRight()); node.setHeight(Math.max(leftHeight, rightHeight) + 1);}
42 private int checkBalance(Node x){ return height(x.getLeft()) - height(x.getRight()); } private Node balance(Node x) { int cb = checkBalance(x); if (cb < -1) { if (checkBalance(x.getRight()) > 0) x.setRight(rotateRight(x.getRight())); x = rotateLeft(x);
} else if (checkBalance(x) > 1) { if (checkBalance(x.getLeft()) < 0) x.setLeft(rotateLeft(x.getLeft())); x = rotateRight(x);
Node y = x.getLeft(); x.setLeft(y.getRight()); y.setRight(x); updateHeight(x); updateHeight(y); return y;
Node y = x.getRight(); x.setRight(y.getLeft()); y.setLeft(x); updateHeight(x); updateHeight(y); return y;
} private Node insert(Node node, Student student)
To insert a student node into a binary search tree, check if the current node is null; if so, create a new node with the student If the student's ID is less than the current node's ID, recursively insert the student into the left subtree Conversely, if the student's ID is greater, insert it into the right subtree If the IDs are equal, update the existing node with the new student information After insertion, update the height of the node and balance the tree to maintain its structure.
} public void insertStudent(Student student){ this.root = insert(this.root, student);
} public void NLR(Node node){ if (node != null) {
System.out.println(node.getStudent().toString()) ;
} private Node search(Node x, String studentID)
{ if (x == null) return null; if (x.getStudent().getStudentID() == studentID) return x; return (x.getStudent().getStudentID().compareTo(studentID) < 0)
} public String search(String studentID){ return search(root, studentID).getStudent().toString();
44 private Node deleteMax(Node x) { if (x.getRight() == null) return x.getLeft(); x.setRight(deleteMax(x.getRight())); return x;
} public void deleteMax() { deleteMax(root);
} private Node deleteMin(Node x) { if (x.getLeft() == null) return x.getRight(); x.setLeft(deleteMin(x.getLeft())); return x;
} public void deleteMin() { deleteMin(root);
} public Node min(Node x) { if (x.getLeft() == null) return x; return min(x.getLeft());
} public Node max(Node x) { if (x.getRight() == null) return x; return max(x.getRight());
} private Node deleteStudent(Node x, String s)
To delete a student from a binary search tree, first check if the node is null; if it is, return null Next, compare the student's ID with the current node's ID If the ID is smaller, recursively delete from the left subtree; if larger, delete from the right subtree If a match is found, handle the deletion by returning the left child if the right child is null, or vice versa, ensuring the tree remains properly structured.
Node t = x; x = min(t.getRight()); x.setRight(deleteMin(t.getRight())); x.setLeft(t.getLeft());
} public void deleteStudent(String studentID) { deleteStudent(this.root, studentID);
} public class Node { private Student student; private Node left, right; private int height; public Node(Student student) { this.student = student; this.left = this.right = null; this.height = 0;
} public Student getStudent() { return student;
} public void setStudent(Student student) { this.student = student;
} public void setLeft(Node left) { this.left = left;
} public Node getRight() { return right;
} public void setRight(Node right) { this.right = right;
} public int getHeight() { return height;
} public void setHeight(int height) { this.height = height;