Bài tập lớn Nhập môn lập trình: Ứng dụng gọi xe BKAR | Môn: Nhập môn Kỹ thuật lập trình - Trường: Đại học Bách khoa Thành phố Hồ Chí

lOMoAR cPSD| 37879319
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
Nhập môn lập trình - CO1003 Bài tập lớn ỨNG DỤNG GỌI XE BKAR
TP. HỒ CHÍ MINH, THÁNG 03/2025 ĐẶC TẢ BÀI TẬP LỚN lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH Phiên bản 1.0 1 Chuẩn đầu ra
Sau khi hoàn thành bài tập lớn này, sinh viên ôn lại và sử dụng thành thục:
• Các cấu trúc rẽ nhánh • Các cấu trúc lặp
• Mảng 1 chiều và mảng 2 chiều • Xử lý chuỗi ký tự • Hàm và lời gọi hàm
• Cấu trúc do người dùng tự định nghĩa (Struct) 2 Dẫn nhập
Trong thời đại công nghệ phát triển mạnh mẽ, các ứng dụng xe công nghệ đang ngày càng trở nên
phổ biến và có tính cạnh tranh cao. Với mong muốn tham gia vào thị trường này, công ty BKAR –
một công ty cung cấp dịch vụ gọi xe – đang có kế hoạch xây dựng một hệ thống nhận/trả khách tối
ưu và hiệu quả. Mục tiêu của hệ thống này là xây dựng một hệ thống tính toán lộ trình di chuyển
thông minh của các phương tiện di chuyển nhằm tối ưu thời gian di chuyển của khách hàng.
Là nhóm trưởng của nhóm phát triển thuật toán cho dự án này, bạn và nhóm của mình có
nhiệm vụ nghiên cứu, đề xuất và triển khai một mô hình tối ưu hóa lộ trình cho hệ thống gọi xe
BKAR. Cụ thể, nhóm cần giải quyết các vấn đề sau:
• Xây dựng bản đồ di chuyển của các phương tiện: Biểu diễn hệ thống đường phố mô phỏng
trong thành phố của bạn, với các địa điểm đón/trả khách mà người dùng có thể đặt dịch vụ,
cũng như các phương tiện có thể lưu thông.
• Tìm đường tối ưu: Áp dụng thuật toán để xác định tuyến đường ngắn nhất giữa điểm đón và
điểm trả khách, nhằm tối ưu hóa thời gian di chuyển.
• Sắp xếp và tối ưu chuyến xe: Phân bổ xe hợp lý để phục vụ nhiều khách hàng cùng lúc, giảm
thời gian chờ và hạn chế xe chạy không hiệu quả. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH 3 Yêu cầu
Mục này nêu ra các yêu cầu để sinh viên xây dựng một Ứng dụng gọi xe BKAR bằng các hiện thực
các hàm tương ứng theo mô tả yêu cầu. Mỗi yêu cầu có số điểm đi kèm biểu diễn số điểm tối đa đạt
được nếu sinh viên hiện thực đúng yêu cầu. 3.1 Kiểu của câu lệnh
Hệ thống sẽ tự động nhận các yêu cầu của người dùng và chuyển thành các câu lệnh để xử lý. Có
tổng cộng 6 loại lệnh: Add, Schedule, Pick, Drop, Move, Create. Enum commandType được sử dụng
để biểu diễn loại lệnh gồm các giá trị ADD, SCHEDULE, PICK, DROP, MOVE, CREATE, INVALID lần lượt
tương ứng với các loại lệnh Add, Schedule, Pick, Drop, Move Create và lệnh không hợp lệ.
Yêu cầu 1 (0.4 điểm): Hiện thực hàm getCommandType để trả về loại của câu lệnh, thông tin cụ thể:
• Khai báo hàm: enum commandType getCommandType(char* command) • Tham số đầu vào:
– command (kiểu char*): chuỗi chứa một lệnh.
• Trả về: giá trị trả về có kiểu là commandType tương ứng với kiểu của lệnh command được truyền vào.
• Yêu cầu hàm: Gọi w là từ đầu tiên xuất hiện trong câu lệnh. Nếu w trùng với một trong kiểu
câu lệnh được mô tả ở trên thì trả về giá trị enum commandType tương ứng. Ngược lại, w là
một từ không hợp lệ thì trả về giá trị INVALID. Lưu ý, các lệnh không biệt chữ hoa và chữ
thường. Xem ví dụ 3.1 để hiểu rõ hơn. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH 3.2 Khởi tạo bản đồ
Thành phố sẽ có N địa điểm, các địa điểm sẽ được đánh số từ 0 đến (N −1). Nếu có thể đi từ địa
điểm thứ nhất đến địa điểm thứ hai thì sẽ có đường nối giữa 2 địa điểm này và một giá trị khoảng
cách (đơn vị là km). Hình 1 mô phỏng bản đồ thành phố có 5 địa điểm.
Bản đồ thành phố được biểu diễn dưới dạng một mảng hai chiều (N ×N) kiểu số nguyên, với N
là số lượng địa điểm trong bản đồ. Mỗi hàng và mỗi cột đại diện cho 1 địa điểm trong bản đồ. Giá
trị trong ô giao giữa hàng i và cột j cho biết khoảng cách trực tiếp từ địa điểm i đến địa điểm j. Nếu
không có đường đi trực tiếp từ địa điểm i đến địa điểm j thì giá trị này bằng 0. Lưu ý, các chỉ số trong
mảng được đánh số bằng đầu từ 0. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH 5 × 5 N =5 0 2 3 0 6 2 0 0 4 5 3 0 0 0 3 0 4 0 0 3 6 5 3 3 0
Sinh viên cần hiện thực 2 hàm: createMapFromArray để khởi tạo bản đồ từ mảng 1 chiều cho
trước và createMapFromDescription để khởi tạo bản đồ từ một mô tả, 2 hàm sẽ được trình bày kỹ
hơn ở các yêu cầu phía dưới.
Chú ý rằng, hàm createMapFromDescription nhận đầu vào là 1 mô tả, sinh viên được yêu cầu
hiện thực hàm checkDescription để kiểm tra tính hợp lệ của mô tả này. Mô tả của bản đồ được quy
định phải thoả mãn các điều kiện sau:
• Độ dài tối đa là 400 ký tự.
• Mô tả chỉ chứa các loại ký tự: lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
– Ký tự chữ cái thường. – Ký tự chữ cái hoa. – Ký tự chữ số.
– Các ký tự đặc biệt: khoảng trắng, dấu phẩy, dấu chấm, dấu gạch ngang, dấu hai chấm.
• Không được bắt đầu và không được kết thúc bằng ký tự khoảng trắng.
Yêu cầu 2 (0.5 điểm): Hiện thực hàm checkDescription để kiểm tra mô tả, thông tin cụ thể:
• Khai báo hàm: int checkDescription(char* description) • Tham số đầu vào:
– description (kiểu char*): chuỗi chứa mô tả của bản đồ bằng Tiếng Anh. • Trả về:
– Nếu mô tả hợp lệ với các điều kiện trên thì trả về giá trị -1.
– Nếu mô tả không hợp lệ do vi phạm về độ dài tối đa thì trả về độ dài hiện tại của mô tả.
– Nếu mô tả là không hợp lệ do vi phạm các điều kiện còn lại (ngoài điều kiện về độ dài tối
đa) thì trả về vị trí của ký tự đầu tiên vi phạm điều kiện. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
Trước khi đi vào yêu cầu tiếp theo, sinh viên cần đọc qua nội dung dưới đây:
Trong lập trình, có kỹ thuật để sử dụng tham số được truyền vào hàm để lưu kết quả đầu ra
của hàm, sinh viên đọc ví dụ 3.5 để hiểu rõ hơn. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
Yêu cầu 3 (0.7 điểm): Hiện thực hàm createMapFromDescription khởi tạo giá trị cho bản đồ từ
mô tả, thông tin cụ thể:
• Khai báo hàm: void createMapFromDescription(char* description, int** map) • Đầu vào:
– description (kiểu char*): chuỗi chứa mô tả của bản đồ bằng Tiếng Anh. • Đầu ra:
– map (kiểu int**): chứa mảng 2 chiều sau khi đã được khởi tạo giá trị. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH • Yêu cầu hàm:
– Sử dụng hàm checkDescription để kiểm tra tính hợp lệ của mô tả. Nếu mô tả không hợp
lệ thì in ra "Invalid Description!" và ngay lập tức kết thúc hàm.
– Sinh viên xử lý chuỗi mô tả để lấy giá trị đưa vào mảng 2 chiều. Chuỗi bao gồm các cậu,
mỗi câu luôn có dạng "The distance from to is km., trong đó: + là điểm bắt đầu + là điểm đến
+ là khoảng cách giữa 2 điểm
Các giá trị , , luôn có 1 chữ số và testcase sẽ đảm bảo và sẽ nằm trong
các địa điểm của bản đồ truyền vào.
– Nếu câu sau mô tả khoảng cách giữa 2 điểm đã xuất hiện ở các câu trước, thì lấy giá trị
khoảng cách của câu sau. Tham khảo ví dụ 3.6 lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH 0 5 0 0 5 0 6 3 0 6 0 1 0 3 1 0
Lưu ý quan trọng: Đối với các yêu cầu cần in ra màn hình, sinh viên cần in ĐÚNG CHÍNH XÁC
từng ký tự như mô tả, nếu chỉ sai khác một ký tự cũng sẽ bị tính là sai testcase đó (cho dù là dư dấu 1 khoảng trắng).
Yêu cầu 4 (0.5 điểm): Hiện thực hàm createMapFromArray khởi tạo giá trị cho bản đồ từ một
mảng 1 chiều, thông tin cụ thể:
• Khai báo hàm:void createMapFromArray(int inputArray[], int mapSize, int** map) • Đầu vào: lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
– inputArray (kiểu mảng int): mảng 1 chiều chứa các giá trị cần được gán vào mảng 2 chiều
theo thứ tự từ trái sang phải, từ trên xuống dưới. Mảng này luôn được đảm bảo có kích thước là mapSize2
– mapSize (kiểu int): số lượng địa điểm của bản đồ (số N trong ví dụ 3.2) • Đầu ra:
– map (kiểu int**): chứa mảng 2 chiều sau khi đã được khởi tạo giá trị. 5 × 5 5 × 5 0 2 3 0 6 2 0 0 4 5 3 0 0 0 3 0 4 0 0 3 6 5 3 3 0 3.3 Cập nhật bản đồ
Quản trị viên của hệ thống có thể cập nhật lại các khoảng cách trong bản đồ theo một công thức
được định nghĩa từ trước. Sinh viên cần hiện thực hàm updateMap để giúp quản trị viên hiện thực tác vụ này.
Yêu cầu 5 (0.5 điểm): Hiện thực hàm updateMap cập nhật giá các trị của mảng 2 chiều, thông tin cụ thể:
• Khai báo hàm: void updateMap(int** map, int mapSize) • Tham số đầu vào:
– map (kiểu int**): biến lưu trữ mảng 2 chiều
– mapSize (kiểu int): số lượng địa điểm của bản đồ (số N trong ví dụ 3.2) lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH • Yêu cầu hàm:
– Đọc vào một giá trị k từ đầu vào chuẩn (các giá trị nhập từ bàn phím).
– Kiểm tra xem giá trị nào trong mảng 2 chiều khác 0 thì sẽ tăng lên một khoảng bằng (2 × k + 7)
– Mỗi giá trị của mảng 2 chiều chỉ được cập nhật 1 lần duy nhất.
3.4 Đường đi trực tiếp trong bản đồ
Trong bản đồ, đường đi trực tiếp giữa 2 địa điểm là đường nối trực tiếp 2 địa điểm đó mà không
thông qua một điểm trung gian nào. Ví dụ trong hình 1, giữa địa điểm 1 và địa điểm 2 tồn tại đường
đi trực tiếp, nhưng địa điểm 1 và địa điểm 4 không tồn tại đường đi trực tiếp. Trong bản đồ này tổng
cộng có 7 đường đi trực tiếp.
Yêu cầu 6 (0.5 điểm): Hiện thực hàm countPath để đếm số đường đi trực tiếp trong bản đồ, thông tin cụ thể:
• Khai báo hàm: int countPath(int** map, int mapSize) • Tham số đầu vào:
– map (kiểu int**): biến lưu trữ mảng 2 chiều
– mapSize (kiểu int): số lượng địa điểm của bản đồ (số N trong ví dụ 3.2)
• Trả về: Số lượng đường đi trực tiếp trong bản đồ. 3.5 In bản đồ
Yêu cầu 7 (0.5 điểm): Hiện thực hàm printMap in ra mảng 2 chiều biểu diễn bản đồ, thông tin cụ thể:
• Khai báo hàm: void printMap(int** map, int mapSize) • Tham số đầu vào:
– map (kiểu int**): biến lưu trữ mảng 2 chiều.
– mapSize (kiểu int): số lượng địa điểm của bản đồ (số N trong ví dụ 3.2)
• Yêu cầu hàm: In ra mảng 2 chiều theo định dạng như ví dụ 3.8 bên dưới. Lưu ý,
sau dấu phẩy là 01 khoảng trắng, cuối mỗi hàng không có khoảng trắng, dòng
cuối cùng không có ký tự xuống dòng. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
[0 , 2 , 3 , 0 , 6
2 , 0 , 0 , 4 , 5
3 , 0 , 0 , 0 , 3
0 , 4 , 0 , 0 , 3
6 , 5 , 3 , 3 , 0]
3.6 Cấu trúc mô tả khách hàng
Các khách hàng sử dụng dịch vụ của công ty, được mô tả bởi cấu trúc (Struct) Customer, gồm có 3 trường:
• customerID (kiểu mảng char): mã của mỗi khách hàng, bao gồm 3 ký tự. Chỉ
bao gồm các ký tự chữ in hoa.
• pickUpLocation (kiểu int): địa điểm đón khách hàng. • dropOffLocation (kiểu
int): địa điểm trả khách hàng.
Hàm printCustomer được hiện thực sẵn để in ra màn hình thông tin của một khách hàng theo
địng dạng. Sinh viên dùng hàm này nếu có yêu cầu hiển thị thông tin khách hàng ở các yêu cầu phía dưới.
3.7 Cấu trúc mô tả một xe
Các xe của công ty được gọi là Car, được mô tả bởi cấu trúc (Struct) Car, gồm có 11 trường:
• carID (kiểu mảng char): mã của mỗi xe, bao gồm tối đa 5 ký tự. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
• speed (kiểu int): tốc độ của xe (đơn vị: km/h).
• operationTypeArray (kiểu mảng int kích thước 6): danh sách nhiệm vụ (đón/trả) của xe đối với
khách hàng hiện tại trên xe.
• numberOfOperations (kiểu int): số lượng nhiệm vụ của xe hiện có. Tối đa là 6
• customerList (kiểu mảng struct Customer kích thước 3): danh sách khách hàng hiện tại trên xe.
• numberOfCustomer (kiểu int): số lượng khách hàng hiện tại trên xe. Tối đa là 3.
• currentLocation (kiểu int): vị trí hiện tại của xe.
• headToLocation (kiểu int): vị trí xe đang chạy đến.
• timeToDestination (kiểu int): thời gian xe chạy đến đích hiện tại.
• timeOnTheWay (kiểu int): thời gian xe đã chạy trên đường.
Hàm printCarInfo được hiện thực sẵn để in ra màn hình thông tin của một xe theo địng dạng.
Sinh viên dùng hàm này nếu có yêu cầu hiển thị thông tin của xe ở các yêu cầu phía dưới.
3.8 Thêm một xe vào mảng
Thông tin về các xe của công ty sẽ được lưu trong một mảng, gọi là carArray, vì lí do kinh phí duy trì
nên số lượng xe của công ty có thể thay đổi tuỳ thời điểm nhưng không được vượt quá 20 xe.
Yêu cầu 8 (0.6 điểm): Hiện thực hàm addCar để thêm một xe vào mảng, thông tin cụ thể:
• Khai báo hàm:int addCar(struct Car* carArray, int numberOfCar, char* carID) • Tham số đầu vào:
– carArray (kiểu struct Car*): mảng 1 chiều lưu trữ danh sách xe.
– numberOfCar (kiểu int): số lượng xe hiện tại trong mảng.
– carID (char*): chuỗi chứa mã xe mới cần được thêm vào mảng. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
• Yêu cầu hàm: Thêm một xe mới vào cuối mảng theo các yêu cầu sau:
+ Mã của xe mới là carID được truyền vào.
+ Tốc độ mặc định là 20 km/h.
+ Giá trị của các phần trử trong mảng operationTypeArray mặc định là -1.
+ Các giá trị còn lại gán mặc định là 0.
+ Nếu số lượng xe trong mảng đã đạt tối đa thì không thêm, trường hợp này được tính là thêm không thành công.
• Trả về: Số lượng xe trong mảng sau khi thêm thành công. Nếu thêm không thành công thì trả
về số lượng xe hiện tại.
3.9 Kiểm tra trạng thái của xe
Tác vụ này yêu cầu sinh viên hiện thực 3 hàm: isFull, isEmpty, carStatus. Thông tin cụ thể từng hàm
sẽ được mô tả bên dưới. Sinh viên có thể tái sử dụng hàm isFull và isEmpty bên trong thàm carStatus.
Yêu cầu 9 (0.3 điểm): Hiện thực hàm isFull kiểm tra xe một xe đã đầy khách hay chưa, thông tin cụ thể:
• Khai báo hàm: int isFull(struct Car car) • Tham số đầu vào:
– car (kiểu struct Car): xe cần kiểm tra.
• Trả về: Trả về 1 nếu xe đã đầy khách. Ngược lại, trả về 0.
Yêu cầu 10 (0.3 điểm): Hiện thực hàm isEmpty kiểm tra xe một xe có trống hay không, thông tin cụ thể:
• Khai báo hàm: int isEmpty(struct Car car) • Tham số đầu vào:
– car (kiểu struct Car): xe cần kiểm tra.
• Trả về: Trả về 1 nếu xe không có khách nào. Ngược lại, trả về 0.
Yêu cầu 11 (0.4 điểm): Hiện thực hàm carStatus kiểm tra trạng thái của xe theo mã xe, thông tin cụ thể: lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
• Khai báo hàm: int carStatus(struct Car carArray[], int numberOfCar, char* carID) • Tham số đầu vào:
– carArray (kiểu mảng struct Car): mảng 1 chiều lưu trữ danh sách xe.
– numberOfCar (kiểu int): số lượng xe hiện tại trong mảng.
– carID (kiểu char*): chuỗi chứa mã xe cần được kiểm tra. • Trả về:
– Giá trị -1 nếu không tìm thấy xe trong mảng.
– Giá trị 0 nếu xe trống.
– Giá trị 1 nếu xe còn có thể chứa thêm khách.
– Giá trị 2 nếu xe đã đầy. 3.10
Xử lý yêu cầu từ khách hàng
Yêu cầu đón các khách hàng sẽ được mã hoá thành một chuỗi, trong đó sẽ chứa thông tin về mã
khách hàng, điểm đón khách và điểm trả khách đối với từng khách hàng. Xem ví dụ 3.11 để hiểu rõ hơn. pX
Sinh viên cần thực hiện 2 hàm countCustomerRequests và handleCustomerRequests để xử lý tác vụ này. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
Yêu cầu 12 (0.6 điểm): Hiện thực hàm countCustomerRequests đếm số lượng khách hàng từ
yêu cầu, thông tin cụ thể:
• Khai báo hàm: int countCustomerRequests(char* customerRequests) • Tham số đầu vào:
– customerRequests (kiểu char*): chuỗi thông tin yêu cầu của các khách hàng.
• Yêu cầu hàm: Hàm cần quét qua chuỗi đầu vào và đếm số lượng yêu cầu của khách hàng
trong đó. Cách nhận dạng yêu cầu tuỳ thuộc vào cách triển khai của sinh viên. Biết rằng các
chuỗi đầu vào luôn hợp lệ. Xem ví dụ 3.12 để hiểu rõ hơn.
• Trả về: Số lượng khách hàng yêu cầu.
Yêu cầu 13 (0.65 điểm): Hiện thực hàm handleCustomerRequests để trích xuất yêu cầu của
khách hàng từ chuỗi, thông tin cụ thể:
• Khai báo hàm: void handleCustomerRequests(char* customerRequests, struct Customer* customers) • Tham số đầu vào:
– customerRequests (kiểu char*): chuỗi thông tin yêu cầu của các khách hàng. • Đầu ra:
– customers (kiểu struct Customer*): mảng chứa thông tin khách hàng đã được trích xuất.
• Yêu cầu hàm: Hàm cần quét qua chuỗi đầu vào, trích xuất thông tin (giá trị của trường) của
từng khách hàng. Gán các giá trị được trích xuất này vào các trường tương ứng của các biến
kiểu Customer tại ví trị phù hợp trong danh sách khách hàng đầu vào customers.
Xem ví dụ 3.13 để hiểu rõ hơn. lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH 3.11 Thêm khách hàng vào xe
Sau khi xử lý chuỗi đầu vào chứa thông tin khách hàng, hệ thống sẽ đưa khách hàng vào danh sách của xe.
Sinh viên cần thực hiện 2 hàm addCarOperationType và addCustomer để xử lý tác vụ này.
Yêu cầu 14 (0.3 điểm): Hiện thực hàm addCarOperationType để thêm tác vụ kế tiếp của xe vào
danh sách nhiệm vụ, thông tin cụ thể:
• Khai báo hàm: void addCarOperationType(struct Car* car, int type) • Tham số đầu vào:
– car (kiểu struct Car*): xe sẽ thêm tác vụ vào.
– type (kiểu int): kiểu tác vụ được thêm vào. • Yêu cầu hàm: .
– Nếu số lượng tác vụ hiện tại numberOfOperations vượt quá 6, in ra thông báo "Car :
Operation list is full!", với là giá trị carID của xe và kết thúc hàm. – Nếu không, thêm
tác vụ mới type vào mảng tác vụ của xe.
Yêu cầu 15 (0.3 điểm): Hiện thực hàm addCustomer để thêm khách hàng mới vào xe, thông tin cụ thể:
• Khai báo hàm: void addCustomer(struct Car* car, struct Customer customer) • Tham số đầu vào: lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
– car (kiểu struct Car*): xe sẽ thêm khách hàng vào.
– customer (kiểu struct Customer): khách hàng được thêm vào. • Yêu cầu hàm:
– Nếu số lượng khách hàng trên xe hiện tại numberOfCustomer bằng 3, in ra thông báo
"Car : Customer list is full!", với là giá trị carID của xe và kết thúc hàm.
– Nếu số lượng khách hàng hiện tại trên xe ít hơn 3 thì thêm khách hàng mới customer mảng khách hàng của xe.
– Sau khi đã thêm khách hàng mới vào mảng, thực hiện hàm addCarOperationType để
thêm 2 tác vụ Đón, Trả vào mảng tác vụ của xe.
– Nếu tác vụ là Đón, type = 0.
– Nếu tác vụ là Trả, type = 1. 3.12
Sắp xếp lộ trình đón khách
Yêu cầu 16 (0.65 điểm): Hiện thực hàm schedulePassengers để thêm khách hàng vào danh sách
khách hàng của xe theo mô tả yêu cầu hàm bên dưới, thông tin cụ thể: • Khai báo hàm:
void schedulePassengers(struct Car* car, char* customerRequests) • Tham số đầu vào:
– car (kiểu struct Car*): xe sẽ thêm khách hàng vào.
– customerRequests (kiểu char*): chuỗi thông tin yêu cầu của các khách hàng. • Yêu cầu hàm:
– Nếu danh sách khách hàng đã đầy, in ra thông báo "Car is full, cannot add more
customers!", với là giá trị carID của xe.
– Nếu danh sách không đầy, hàm sẽ cố gắng thêm nhiều khách nhất có thể vào danh sách
khách hàng của xe. Sinh viên được khuyến khích sử dụng lại các hàm
countCustomerRequests và handleCustomerRequests để trích xuất thông tin đưa vào
danh sách khách hàng, sau đó tiến hành thêm khách hàng vào danh sách khách hàng của xe.
– Lưu ý, sức chứa của xe tối đa là 3 khách hàng. Nếu danh sách vẫn còn khách hàng cần
được thêm vào nhưng xe đã quá tải, những khách hàng này sẽ bị bỏ qua. Cuối cùng, in lOMoAR cPSD| 37879319
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG-HCM
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH
ra thông báo "Car is full now, Customer is skipped!", với là giá trị carID của
xe, là giá trị customerID của khách hàng. Xem ví dụ 3.14 để hiểu rõ hơn. Ví dụ 3.14
Ví dụ, ta có xe có mã BK24, hiện đang có 2 hành khách trên xe, và chuỗi đầu vào
LMHp1d5TKQp4d10. Như vậy, theo quy định, danh sách của xe chỉ có thể thêm được vị khách
đầu tiên, và nên bỏ qua vị khách thứ hai. Cụ thể: Giả sử, xe hiện có khách hàng A và khách
hàng B, customerList của xe như sau:
• Customer A: ID=XXX, pickUpLocation=0, dropOffLocation=1.
• Customer B: ID=YYY, pickUpLocation=2, dropOffLocation=3.
Sau khi tiến hành hàm schedulePassengers, customerList của xe như sau:
• Customer A: ID=XXX, pickUpLocation=0, dropOffLocation=1.
• Customer B: ID=YYY, pickUpLocation=2, dropOffLocation=3.
• Customer C: ID=LMH, pickUpLocation=1, dropOffLocation=5.
Và dòng thông tin, "Car BK24 is full now, Customer TKQ is skipped!". 3.13
Tính toán thời gian tối ưu
Một trong những yêu cầu của hệ thống là phải tối ưu hoá thời gian di chuyển giữa các địa điểm. Do
giả định tốc độ di chuyển không đổi và không xảy ra ùn tắc giao thông, nên để tối ưu hoá thời gian
di chuyển giữa 2 địa điểm thì cần phải tìm quãng đường ngắn nhất giữa 2 địa điểm này. Mã nguồn
sẽ cung cấp sẵn cho sinh viên hàm findShortestPath để tìm quãng đường ngắn nhất, thông tin cụ thể: • Tham số đầu vào:
– map (kiểu int**): biến lưu trữ mảng 2 chiều.
– mapSize (kiểu int): số lượng địa điểm trong bản đồ.
– start (kiểu int): địa điểm bắt đầu.
– end (kiểu int): địa điểm muốn đến.