Tài liệu môn Tin Học | Đại học Ngoại Ngữ - Tin Học Thành Phố Hồ Chí Minh

gv : Huỳnh Bình Buổi 02
THUẬT TOÁN TÌM KIẾM Yêu cầu :
Cài đặt class IntArray và các thuật toán tìm kiếm tuần tự (Sequental Search) và nhị phân (Binary
Search) với các yêu cầu như sau : Thành phần : int[] arr Phương thức : 
IntArray() : Constructor không đ i s ố (ch ố khai báo bi ỉ n) ế 
IntArray(int n) : Constructor có đ i s ố n và t ố o ng ạ u ẫ nhiên n ph n t ầ cho dãy arr ử 
IntArray(int[] b) : Constructor có đ i s ố là m ố t array b ộ và copy dãy b -> dãy arr 
IntArray(IntArray obj) : Constructor copy v i đ ớ i ố s là object obj ố  Output() : Xu t ấ dãy arr lên màn hình  Sort() : S p ắ xếp dãy tăng d n (nh ầ đã h ư c ọ môn KTLT) ở 
SequentialSearch(int x) : Tìm ki m tu ế n ầ t ự v i x là giá tr ớ c ị n tìm ầ 
BinarySearch(int x, int left, int right) : Tìm ki m b ế ng ằ ph ng pháp Nh ươ phân ị
Chương trình có sử dụng class Menu đã dùng trong buổi 01
Cài đặt : project Buoi02
1. Add \ Existing Item : Menu.cs (trong Buoi01) vào project 2. Class IntArray.cs Thư viện sử dụng : using System;
using System.Collections.Generic; using System.Text; class IntArray { int[] arr; //Propeties
public int[] Arr { get => arr; set => arr = value; } // Constructor
// Constructor không đối số public () IntArray { } // Constructor có đ i ố s n và t ố o ng ạ u nhiên n ẫ ph n t ầ cho dãy arr ử public IntArray(int n) { // n là số phần t c ử a array ar ủ arr = new int[n];
// khai báo biến rd ki u Random ể Random rd = new Random();
for (int i = 0; i < n; i++)
arr[i] = rd.Next(0,100); // Tạo số ngẫu nhiên t ừ 0 -> 99 } // Constructor có đ i
ố s là array b và copy b -> arr ố public IntArray(int[] b) { arr = new int[b.Length]; arr = b; } // Constructor copy : Đ i ố s là object obj ố public (I IntArray ntArray obj) {
arr = new int[obj.Arr.Length]; arr = obj.Arr; } // Xu t dãy arr lê ấ n màn hình public void Output() gv : Huỳnh Bình { // Ph n làm bài ầ } // Tìm ki m tu ế ần tự
public int SequentialSearch(int x) { // Ph n làm bài ầ // Duy t ệ t n ừ g ph n t ầ arr[i]c ử a ủ array arr // N u arr ế i] ơ = x, tr v ả v ề trí i ị // Tr v ả - ề 1 (lúc này k t thúc duy ế t nh ệ ng không tìm th ư y) ấ } // S p x ắ p ế dãy tăng d n (nh ầ đã h ư c ọ môn KTLT) ở public void Sort() { // Ph n làm bài ầ } // Tìm ki m b ế ằng ph ng pháp Nh ươ phân ị // Tìm x trong kho n
ả từ left đ n right trong dãy ế
public int BinarySearch(int x) { // S p x ắ p ế dãy arr tăng d n ầ // Đ t giá ặ
trị ban đầu cho 2 bi n left = 0 và right ế = arr.Lenght – 1 // Khai báo biến mid (int) // L p (kh ặ i left <= right)
Đặt giá tr mid = (left + right) / 2 ị
N u x = arr[mid] return mid (tìm ế th y) ấ Ng c l ượ i, n ạ u x < arr[mid ế ] Đ t right = mid – 1 ặ Ng c l ượ i : left = mid + 1 ạ
// return -1 (không tìm th y) ấ }
// Phương thức (đ qui) Tìm x trong kho ệ n ả t
ừ left đ n right trong dãy (đ ế c ọ thêm)
public int BinarySearch_DQ(int x, int left, int right) { Sort(); //left<=right là đi u ki ề n ti ệ p ế t c ụ tìm (g i đ ọ qui) ệ if (left <= right) { int mid = (left + right) / 2; // N u ế arr[mid] = x, tr v ả ề ch s ỉ và k ố t thúc. ế if (arr[mid] == x) return mid; // N u
ế arr[mid] > x, thực hi n tìm ki ệ m n ế a trái c ử a ủ dãy else if (arr[mid] > x)
return BinarySearch_DQ(x, left, mid - 1); // N u
ế arr[mid] < x, thực hi n tìm ki ệ m n ế a ph ử i c ả a dãy ủ else if (arr[mid] < x)
return BinarySearch_DQ(x, mid + 1, right); } // Khi c n ậ trái left > c n ph ậ i right ả // không tìm  th y (đi ấ u ki ề ện d ng c ừ a đ ủ qui) ệ return -1; } } 3. Class Program.cs gv : Huỳnh Bình
Thư viện sử dụng trong chương trình using System;
using System.Collections.Generic; using System.Text; class Program {
static void Main(string[] args) { // Xu t te ấ xt theo Unicode (có d u ti ấ n ế g Vi t) ệ
Console.OutputEncoding = Encoding.Unicode; // Nh p te ậ xt theo Unicode (có d u ti ấ n ế g Vi t) ệ
Console.InputEncoding = Encoding.Unicode; /* T o men ạ u */ Menu menu = new Menu();
string title = "THUẬT TOÁN TÌM KIẾM"; // Tiêu đ menu ề // Danh sách các m c ụ ch n ọ
string[] ms = { "1. T o dãy s ạ ng ố u
ẫ nhiên", "2. Xu t dãy lên ấ màn hình", "3. Tìm kiếm Tu n t ầ " ự , "4. Tìm ki m nh ế phân" ị , "0. Thoát" };
// Khai báo biến ds (dãy s ) ố IntArray ds = new IntArray(); int chon; do { // Xuất menu menu.ShowMenu(title, ms); Console.Write(" Ch n : " ọ );
chon = int.Parse(Console.ReadLine()); switch (chon) { case 1: { // Nh p s ậ ph ố n ầ tử n = ? // Kh i t ở o ds : ạ ds = new IntArray(n) } case 2: { // Xu t dãy s ấ arr lên ố màn hình } case 3: { // Nh p s ậ c ố n ầ tìm : x = ? // Tìm ki m nh ế phân v ị i bi ớ n
ế : int vt = ds.SequentialSearch(x) // Xu t l ấ t qu ế ả theo giá trị vt } case 4: { // Nh p s ậ c ố n ầ tìm : x = ? // Tìm ki m nh ế phân v ị i bi ớ n
ế : int vt = ds.BinarySearch(x) // Xu t l ấ t qu ế ả theo giá trị vt } } Console.WriteLine(" Nh n m ấ t ph ộ ím b t kỳ" ấ ); Console.ReadKey(); Console.Clear(); } while (chon != 0); } } Bài tập gv : Huỳnh Bình
Phần 1 : tạo project Buoi02 với các class theo hướng dẫn trên, và hoàn thành các yêu cầu sau : 
Trong class IntArr viết các phương thức : Output(),SequentialSearch(int x), Sort(), BinarySearch(int x) . 
Trong Program.cs, trình bày các mục (case) để sử dụng các phương thức trên.
Phần 2 : Bài tập áp dụng thuật toán tìm kiếm nhị phân. (Bài làm được viết dưới dạng hàm trong Program.cs)
Ý tưởng của thuật toán tìm kiếm nhị phân là tìm kiếm một vấn đề đúng trong một không gian
(có thứ tự) được giới hạn bởi cận dưới (low) và cận trên (hight) nào đó. Việc tìm kiếm được thực hiện
trên từng nửa đoạn thông qua một giá trị mid = (cận dưới + cận trên) div 2 S p th ắ ứ tự các phần t c ử a không gian tìm ki ủ p (n ế u ch ế a th ư t ứ ); ự Xác đ nh c ị n d ậ i ban đ ướ u : ầ đ u (lo, left, … ầ ); Xác đ nh c ị n trên ban đ ậ u
ầ : cuối (hi, right, … ); while(đ u ầ <= cu i) ố { mid = (đ u + ầ cu i) / 2; ố
if (Mệnh đề tìm ki m đúng t ế i v ạ trí mid) ị return mid; else Hai tr ng h ườ p xác đ ợ nh l ị i c ạ n ậ d i ho ướ c c ặ n trên; ậ }
Bài 1 : bài toán cổ "Vừa gà vừa chó. Bó lại cho tròn. Ba mươi sáu con. Một trăm chân chẵn”
Hỏi có bao nhiêu gà bao nhiêu chó?
Hướng dẫn : Tất cả có 36 con vật. Chúng không thể đều là gà vì như vậy sẽ chỉ có 72 chân, Cũng không
thể nào là chó cả vì như vậy sẽ có cả thảy 144 chân (Số chân của chúng là 100 chân).
Áp dụng tư tưởng chặt nhị phân cho bài toán này như sau:
- Sắp xếp số gà theo thứ tự tăng dần (theo chiều từ dưới lên)
- Chia đôi tổng số gà, nếu tại điểm giữa đó tổng số chân gà và chân chó lớn hơn 100 thì lấy nửa
trên, và ngược lại lấy nửa dưới. Thuật toán: 
Đặt cận dưới d(đầu) = 0, cận trên c(cuối) = 36, tổng số chân x = 100  điều kiện lặp : d < c và
mệnh đề tìm kiếm đúng là : (x = 2*g + 4*(36 - g))  Lặp khi (d < c)
Gọi g là số gà cần tìm và đặt g = (d+c) / 2;
Nếu (x = 2*g + 4*(36 - g)) thì Số gà là g, Số chó là y = 36 – g.
Nếu (x > 2*g + 4*(36 - g)) thì đặt lại cận trên c = g
Nếu (x < 2*g + 4*(36 - g)) thì cận dưới d = g
Bài 2 : Cho chuỗi s gồm các ký tự ‘0’ ở đầu chuỗi, còn cuối chuỗi là các ký tự ‘1’. Ví dụ :
string s = "0000000000000000000000011111111111111";
Hãy tìm vị trí cuối cùng của ký tự ‘0’ trong s bằng thuật toán tìm kiếm nhị phân.
Hướng dẫn : bắt đầu từ vị trí 0 (left) và tìm cho đến vị trí s.Lenght – 1 (right) với vị trí tìm nhị phân là
mid = (left + right) / 2  vị trí tìm đúng là : (s[mid] = '0' và s[mid+1] = '1') Thuật toán : B t đ ắ
ầu left = 0, right = s.Length - 1; L p khi ặ (left <= right) g i ọ mid = (left + right) / 2; N u
ế (s[mid] = '0' và s[mid+1] = '1')
Vị trí số 0 cu i cùng : là ố mid D ng ừ tìm ki m ế Ng c l ượ i, ạ N u
ế (s[mid] == '0') left = mid + 1; Ng c l ượ i ạ right = mid - 1; gv : Huỳnh Bình
Bài 3 : bài toán vận chuyển hàng hóa. Một băng chuyền phải vận chuyển các gói hàng theo thứ tự cho
trước trong giới hạn là ngày days
. Gói hàng thứ i có trọng lượng
. Biết mỗi ngày băng chuyền weights[i]
chỉ có thể vận chuyển tổng khối lượng tối đa là MAX. Hãy tìm MAX nhỏ nhất để băng chuyền có thể
hoàn thành nhiệm vụ được giao trong days ngày theo yêu cầu. Ví dụ : 
Trọng lượng các gói hàng là : { 5, 6, 3, 2, 4, 8, 9, 10, 12 }; 
Số ngày giao hàng theo yêu cầu là : days = 5 ngày; 
Tìm trọng lượng hàng hóa nhỏ nhất vận chuyển trong mỗi ngày để hoàn thành trong 5 ngày Thuật toán
Chọn cận dưới : lo = trọng lượng gói hàng nặng nhất. Cận trên : hi = tổng trọng lượng các gói hàng
 vị trí tìm kiếm nhị phân : mid = lo + (hi – lo)/2 // Kh i gán c ở n ậ d i, c ướ n trên ậ // Ch n c ọ n ậ dưới lo = tr ng l ọ ng gói hàng n ượ ng ặ nh t, ấ // c n trên ho = ậ t ng các gói hàng ổ L p khi ặ (lo < hi) ch n ọ mid = lo + (hi - lo) / 2; N u
ế (check(mid, weights, days)) : hi = mid; Ng c l ượ i ạ : lo = mid + 1; // k t qu ế ả cu i cùng : lo ố
Mệnh đề tìm kiếm đúng check(mid, weights, days) được xử lý với hàm sau :
bool check(int capacity, int[] weights, int days) { g i tr ọ n
ọ g lượng hàng giao hi n t ệ i : ạ current_weight = 0; s ngày giao gi ố ảm đi 1 : --days; Duy t ệ tr ng l ọ
ượng từng gói hàng (int i = 0; i < weights.Length; i++) N u
ế (current_weight + weights[i] <= capacity) : current_weight += weights[i]; Ng c l ượ i ạ : --days; current_weight = weights[i]; return (days >= 0); }