Xem mẫu
- BÀI TẬP CHƯƠNG 4
Bài 1: Hội nghị bàn tròn
Tổng thư ký Đại hội đồng Liên hợp quốc triệu tập một cuộc họp có N nhà
ngoại giao của N tổ chức tham gia. Các đại diện ngoại giao được bố trí ngồi
quanh một bàn tròn. Giữa một số tổ chức có quan hệ căng thẳng, vì vậy
không thể xếp họ ngồi cạnh nhau được. Thông tin về quan hệ giữa các tổ
chức được cho dưới dạng cặp số nguyên i, j nếu giữa 2 tổ chức này có quan
hệ căng thẳng.
Hãy lập trình giúp Tổng thư ký Liên hợp quốc bố trí chỗ ngồi quanh bàn
họp. Các tổ chức được đánh số từ 1 tới N, 0 < N
- 57
10 7
10 8
10 9
34
00
Bài 2: Domino
Cho trước N con cờ domino, hãy viết chương trình cho biết rằng có cách
sắp N con cờ đó theo đúng luật domino sao cho các con cờ hình thành vòng
tròn hay không, nếu có hãy chỉ ra một cách sắp.
Dữ liệu vào: file DOMINO.INP
Dòng đầu chứa số N
N dòng tiếp theo, mỗi dòng chứa 2 số từ 0 đến 6 mang giá
trị đại diện cho 2 đầu của domino.
Dữ liệu ra: file DOMINO.OUT
Dòng đầu chứa số 1 hoặc 0 tương ứng với sắp được quân
domino thành vòng tròn và không sắp được.
Nếu dòng đầu là 1 (tương ứng với sắp được) thì dòng thứ hai
liệt kê ra N chỉ số của N con cờ domino theo thứ tự để sắp
- thành vòng tròn. Nếu dòng đầu là 0 thì không có dòng thứ
hai.
Ví dụ:
DOMINO.INP
4
53
56
23
62
DOMINO.OUT
1
1342
Bài 3: Kiểm tra đường
Một trạm quảng đường giao thông phải chịu trách nhiêm về tình trạng của
một mạng lưới giao thông nối giữa các điểm dân cư. Hàng tháng, họ phải
cử một đội đi kiểm tra một vòng qua khắp mạng lưới để xem xét tình trạng
hiện thời của các đường giao thông nhằm báo sửa chữa kịp thời nếu có nhu
cầu. Hãy viết chương trình nhập vào mạng lưới giao thông và giúp trạm
quyết định lộ trình của đội kiểm tra sao cho có thể thăm tất cả các con
đường mà tổng chiều dài đoạn đường đi qua là nhỏ nhất.
- Bài 4: Mã đi tuần
Hãy cài đặt chương trình xác định lộ trình của con mã trên bàn cờ 8x8 ô
bắt đầu từ ô (i, j) đi qua tất cả các ô của bàn cờ vàmỗi ô chỉ 1 lần duy nhất.
Mở rộng với trường hợp bàn cờ kích thước NxN.
Bài 5: Hội nghị bàn tròn
Có 12 người ngồi chung 1 bàn tiệc tròn. Mỗi người có ít nhất 6 người quen.
Hãy chỉ ra cách sắp xếp sao cho mỗi người đều ngồi cạnh người mình quen
. Tổng quát, hãy sắp N người ngồi chung quanh bàn tròn sao cho mỗi người
đều ngồi cạnh người mình quen. Biết mỗi người có ít nhất (N + 1)/2 người
quen.
nguon tai.lieu . vn
