1. Đề tài về sắp xếp, tìm kiếm
Có n cuộc hội thảo đánh số thứ tự từ 1 đến n, cùng đăng kí sử dụng một phòng hội trường trong khoảng thời gian từ ngày 1 đến ngày 30 cùng tháng. Cuộc hội thảo thứ i diễn ra từ ngày ai đến ngày bi. Biết rằng tại một thời điểm, phòng hội trường chỉ có thể cho phép bố trí được một cuộc hội thảo. Hãy tìm cách xếp lịch sao cho có nhiều cuộc hội thảo được tổ chức nhất.
Dữ liệu vào cho trong một file văn bản có tên là XEPLICH.INP: Dòng thứ nhất ghi số n. Trong n dòng tiếp theo, dòng thứ i ghi hai số ai và bi , i = 1, 2, ..., n.
Dữ liệu ra ghi vào một file văn bản khác có tên là XEPLICH.OUT: Dòng thứ nhất ghi số m, là số (lớn nhất) các cuộc hội thảo được bố trí tổ chức. Trong m dòng tiếp theo, ghi danh sách các cuộc hội thảo được tổ chức, dòng thứ i ghi số thứ tự của một cuộc họp.
Ví dụ
| XEPLICH.INP | XEPLICH.OUT |
| 6 4 7 11 13 8 9 3 5 1 3 6 11 | 4 1 3 4 7 8 9 11 12 |
Bài toán: Vận chuyển hàng tối ưu
Một nhà vận chuyển (bên B) nhận hợp đồng chuyên chở hàng hóa từ các kho của một tổng công ty (bên A) đến các địa điểm giao hàng. Hợp đồng ghi rõ một số điều khoản như sau:
1) Công việc vận chuyển được tiến hành từ ngày đầu tiên của một tháng nào đó do bên B quyết định. Xem như mỗi tháng có 30 ngày.
2) Phải vận chuyển N loại hàng khác nhau, kí hiệu từ 1 đến N.
3) Trong cùng một ngày tổng công ty chỉ xuất kho một loại hàng. Khi đã xuất hết một loại hàng thì tổng công ty mới cho xuất loại hàng khác.
4) Thời gian vận chuyển trễ một loại hàng được coi là số ngày tính từ ngày đầu tiên đến ngày bắt đầu vận chuyển loại hàng đó. Cứ mỗi ngày vận chuyển trễ loại hàng i thì bên B bị trừ một lượng tiền là Ci nghìn đồng (gọi là tiền phạt).
5) Bên B được quyền quyết định trình tự trước sau các loại hàng cần vận chuyển.
Từ bảng thông tin về các loại hàng cần vận chuyển, nhà vận chuyển đã tính toán thấy rằng loại hàng thứ i muốn chuyển hết về các nơi giao phải mất Ti ngày.
Hãy giúp nhà vận chuyển sắp xếp một trình tự từng loại hàng cần chuyên chở sao cho tổng số tiền phạt là ít nhất.
Dữ liệu vào cho trong một file văn bản có tên là TRANS.INP, trong đó dòng thứ nhất ghi số nguyên dương N (N ≤ 200). Với 1 ≤ i ≤ N, dòng thứ i + 1 ghi hai số nguyên Ti và Ci.
Dữ liệu ra ghi vào một file văn bản với một tên khác là TRANS.OUT. Dòng thứ nhất ghi tổng số tiền bị phạt. Từ dòng thứ hai, mỗi dòng ghi một bộ ba số: số thứ nhất là số hiệu loại hàng cần vận chuyển, số thứ hai là ngày bắt đầu vận chuyển, số thứ ba là số tiền phạt. Trình tự từ trên xuống dưới là trình tự các loại hàng lần lượt được vận chuyển.
Ví dụ
| TRANS.INP | TRANS.OUT |
| 5 2 10 15 4 10 5 20 2 25 15 | 1660 4 1 0 2 21 80 3 26 175 5 46 675 1 71 700 |
2. Đề tài về cấu trúc dữ liệu ngăn xếp và hàng đợi
Bài toán: Kho sửa tầu
Xét mạng đường sắt sau đây:
Các toa tàu ở đường ray A bên phải (được đánh số 1, 2, ..., n) cần phải hoán vị chuyển sang đường ray B bên trái. B được xem như đầu ra của các toa tầu, còn A được xem là đầu vào. Như hình vẽ đã chỉ ra, một toa có thể chuyển thẳng sang đường ray bên trái, hay nó có thể rẽ xuống đường ray bên cạnh (để sửa chữa) để sau này sẽ đi ra đường ray bên trái. Các toa tàu không được phép đi được ngược chiều các mũi tên đã chỉ dẫn.
Cho trước một hoán vị toa tầu ở đầu ra B. Hãy cho biết liệu hoán vị đó có xảy ra hay không.
Ví dụ: ở đầu vào, có 4 toa tầu, ở đầu ra các toa tầu theo thứ tự là 3, 1, 4, 2. Hoán vị này không thể xảy ra. Vì toa đầu tiên là toa 3, điều này chứng tỏ nó đi thẳng ra đầu ra B, còn các toa 1 và 2 được chuyển vào kho. Khi ra khỏi kho thì toa 2 phải ra trước nghĩa là phải có thứ tự 2 trước 1. Điều này mâu thuẫn với thứ tự 2 sau 1 trong hoán vị 3, 1, 4, 2.
Dữ liệu vào cho trong một file văn bản có tên là TRAINS.INP.
- Dòng một ghi số n biểu thị số toa tầu ở đường ray vào A, theo thứ tự các toa được đánh số liên tục 1, 2, ..., n từ trái sang phải.
- Từ dòng 2 trở đi, mỗi dòng ghi một hoán vị toa tầu ở đường ra ra B.
- Dòng cuối cùng của file dữ liệu vào ghi một số 0.
Dữ liệu ra ghi vào một file văn bản có tên là TRAINS.OUT. Tương ứng với mỗi dòng dữ liệu vào (từ dòng thứ hai trở đi trong file input) là một dòng thông báo (được ghi trên một dòng của file output) là “Possible” hoặc “Impossible” tùy theo hoán vị các toa tầu tương ứng (trên dòng dữ liệu vào) có xảy ra được hay không.
Ví dụ
| TRAINS.INP | TRAINS.OUT |
| 4 3 1 4 2 3 2 1 4 1 3 4 2 1 4 2 3 | Impossible Possible Possible Impossible |
Bài toán: Hội chợ triển lãm
Một hội chợ triển lãm các mặt hàng của một số công ty và doanh nghiệp (gọi tắt là đơn vị). Nhu cầu về không gian thuê trưng bày sản phẩm của từng đơn vị rất khác nhau, ví dụ đơn vị trưng bày các sản phẩm gạch lát cần diện tích rộng hơn so với đơn vị trưng bày sản phẩm mĩ nghệ đắt tiền. Do vậy bản đồ hội chợ khá phức tạp, và có dạng như hình dưới đây:
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 1 | 1 | | 1 | | | | 2 |
| 2 | 1 | | | 1 | | 1 | | 2 |
| 3 | 1 | 1 | | | | 1 | | |
| 4 | | | | | 1 | 1 | | |
| 5 | 1 | 1 | 1 | | | | | 2 |
| 6 | 1 | 1 | 1 | | 1 | 1 | 1 | 2 |
Một vùng chỉ gồm các ô vuông ghi chữ số 1 kề cạnh nhau biểu diễn một gian hàng của một đơn vị nào đó. Hai gian hàng khác nhau không chung cạnh hay chung đỉnh tại bất kì ô vuông nào. Các ô vuông kề cạnh ghi chữ số 2 biểu diễn một cửa vào/ra của khu hội chợ. Các ô vuông không ghi chữ số nào (gọi là vị trí trống) biểu thị cho lối đi. Các ô vuông ghi số chữ số 2 cũng được xem như vị trí trống (đi được đến cửa ra/vào). Các gian hàng được bố trí sao luôn có đường đi giữa hai vị trí trống bất kì.
Yêu cầu: Từ bản đồ hội chợ, hãy cho biết
1) Hội chợ có bao nhiêu gian hàng?
2) Gian hàng có diện tích lớn nhất là bao nhiêu?
3) Một vị khách đang đứng tại một vị trí (trống) nào đó trong hội chợ. Hãy chỉ cho vị khách lối đi ngắn nhất để ra ngoài khu hội trợ. Người khách đến được vị trí nào đó của cửa ra/vào được xác nhận là ra được khu hội chợ.
Dữ liệu vào cho trong một file văn bản có tên là HOICHO.INP:
- Dòng một ghi số m và n là số hàng và số cột của bản đồ.
- Dòng hai ghi cặp số u0 và v0 biểu thị vị trí trống của vị khách.
- Trong m dòng tiếp theo, số thứ j trên dòng thứ i có giá trị bằng 0 hoặc 1 hoặc 2 là giá trị của ô vuông ở dòng i cột j và tương ứng biểu thị đó là vị trí hoặc của lối đi hoặc thuộc vào một gian hàng hoặc thuộc vào cửa ra vào.
Dữ liệu ra ghi vào một file văn bản khác có tên là HOICHO.OUT.
- Dòng 1 ghi một số nguyên biểu thị số lượng gian hàng
- Dòng 2 ghi một số nguyên biểu thị diện tích của gian hàng chiếm nhiều không gian nhất.
- Dòng 3 ghi một dãy các cặp số nguyên theo dạng:
(x1, y1) à (x2, y2) à .... (xk, yk) biểu thị đường đi ngắn nhất từ vị trí (u0, v0) đến cửa ra vào. (Trong đó (x1, y1) = (u0, v0)).
Ví dụ
| HOICHO.INP | HOICHO.OUT |
| 6 8 4 4 1 1 0 1 0 0 0 2 1 0 0 1 0 1 0 2 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 2 1 1 1 0 1 1 1 2 | 5 6 (4, 4) -> (5, 4) -> (5, 5) -> (5, 6) -> (5, 7) -> (5, 8) |
3. Đề tài về Đồ thị
Bài toán: Mạng truyền tin an toàn
Người ta cần lắp đặt một mạng truyền tin của một trường đại học gồm n trạm và m đường truyền tin hai chiều trực tiếp giữa các trạm. Chi phí để lắp đặt giữa hai trạm i và j là a[i,j], i, j = 1, 2, ..., n. Các bản tin thường được phát đi từ trạm S thuộc Trung tâm thông tin của nhà trường đến các trạm của các khoa. Để đảm bảo tính an toàn cho việc truyền tin, khoa Tin học của trường đã yêu cầu lắp đặt sao cho thông tin truyền giữa trạm S của Trung tâm và trạm T của Khoa đi theo hai con đường khác nhau (hai đường được gọi là khác nhau nếu chúng không có đường truyền chung). Khoa Tin học còn tư vấn để hai đường truyền tin giữa S và T có tổng chi phí lắp đặt là thấp nhất. Hãy lập trình chỉ ra hai đường truyền tin khác nhau đó mà tổng chi phí lắp đặt là nhỏ nhất.
Dữ liệu vào cho trong file văn bản TWOWAYS.INP
- Dòng đầu tiên chứa bốn số nguyên dương N, M, S, T, trong đó N ≤ 200, 1≤ M ≤ 1/2*N*(N-1). S và T tương ứng là trạm của Trung tâm thông tin và của trạm Khoa Tin học.
- M dòng tiếp theo, mỗi dòng miêu tả các đường truyền trực tiếp gồm ba số nguyên dương i, j, k thể hiện chi phí lắp đặt đường truyền trực tiếp giữa hai trạm i và j là k, (k ≤ 3000).
Dữ liệu ra Ghi vào file văn bản TWOWAYS.OUT
- Dòng đầu tiên ghi tổng chi phí nhỏ nhất của hai đường truyền đã tìm được.
- Dòng thứ hai biểu thị đường truyền thứ nhất.
- Dòng thứ ba biểu thị đường truyền thứ hai.
Mỗi đường truyền là một “đường đi”, gồm một dãy các trạm bắt đầu là trạm S và kết thúc là trạm T.
Ví dụ
| TWOWAYS.INP | TWOWAYS.OUT |
| 6 8 2 5 1 2 1 1 4 2 2 3 3 3 4 2 3 6 5 4 5 3 4 6 2 5 6 1 | 14 2 1 4 5 2 3 4 6 5 |
Bài toán: Mạng giao thông
Theo thiết kế, một mạng giao thông gồm n nút, có tên từ 1 đến n (n ≤ 100). Chi phí để xây dựng đường hai chiều trực tiếp từ nút i đến nút j bằng a[i,j] = a[j,i]. Qui ước a[i,i]= 0 với mọi i. Hai tuyến đường khác nhau không cắt nhau tại hai điểm không là đầu mút. Hiện đã xây dựng được k tuyến đường.
Bài toán đặt ra như sau: Hệ thống đường đã xây dựng đã đảm bảo sự đi lại giữa hai nút bất kì chưa? Nếu chưa, hãy chọn một số tuyến đường cần xây dựng thêm sao cho:
1. Các tuyến đường xây dựng thêm cùng với các tuyến đường đã xây dựng đảm bảo sự đi lại giữa hai nút bất kì.
2. Tổng kinh phí xây dựng các tuyến đường thêm là ít nhất.
Dữ liệu vào cho trong file văn bản có tên là MGT.INP, trong đó dòng thứ nhất ghi hai số n và k. Trong k dòng tiếp theo, mỗi dòng ghi hai số là tên của hai nút, đó là hai đầu (mút) của một tuyến đường đã xây dựng. Cuối cùng là n dòng, dòng thứ i ghi n số a[i,1], a[i, 2], ..., a[i, n].
Dữ liệu ra ghi vào file văn bản có tên là MGT.OUT như sau: Dòng thứ nhất ghi số CP là chi phí xây dựng thêm nhỏ nhất đã tìm được. Nếu CP > 0, trong một số dòng tiếp theo, mỗi dòng ghi hai số là tên của hai nút, đó là hai đầu (mút) của một tuyến đường xây dựng thêm.
Ví dụ;
| MGT.INP | MGT.OUT |
| 5 4 1 2 2 3 3 1 4 5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 | 1 3 4 |
3. Đề tài về danh sách liên kết
Bài toán Quản lí hàng
Một mặt hàng gồm các thông tin sau đây:
- Mã hàng
- Tên hàng
- Đơn giá
- Số lượng
- Đơn vị tính
Viết chương trình trong đó có ít nhất các chức năng sau
1. Tạo một tệp QLHANG.DAT mới để chuẩn bị chứa thông tin các mặt hàng
2. Nhập một mặt hàng mới để ghi vào tệp QLHANG.DAT
3. Hiển thị thông tin các mặt hàng hiện có
4. Tìm kiếm một mặt hàng theo mã hàng và đưa ra các thông tin (nếu tìm thấy)
5. Đưa ra danh sách gồm tên hàng, đơn giá, số lượng và thành tiền.
Yêu cầu chương trình sử dụng danh sách liên kết để chứa thông tin các mặt hàng và đọc/ghi từ file văn bản trên đĩa.
Cô có thể cho 1 số gợi ý về đề tài "Vận chuyển hàng tối ưu" được không ạ
Trả lờiXóa