bài tạp về môn Cấu Trúc Dữ Liệu & Giải Thuật

[nhokkoolny]

Em vừa mới học môn này được 2 bữa mà thầy đã cho bài tập về nhà rồi, có vài điểm em không hiểu là làm bài tập môn này là mình viết core để chạy chương trình hay là viết để khung sườn cho để dựa vào đó mà viết core dễ hơn, em thấy môn này hơi mơ hồ
VD: đề bài là :
''Trên bàn cớ quốc tế đặt 1 quân Hậu trắng tại ô(x,y). Hãy xây dựng CTDL để lưu trạng thái của bàn cờ thể hiện các ô mà 1 quân đen có thể đi vào mà không bị quân Hậu trắng ăn.''

[07520182]

Em vừa mới học môn này được 2 bữa mà thầy đã cho bài tập về nhà rồi, có vài điểm em không hiểu là làm bài tập môn này là mình viết core để chạy chương trình hay là viết để khung sườn cho để dựa vào đó mà viết core dễ hơn, em thấy môn này hơi mơ hồ
VD: đề bài là :
''Trên bàn cớ quốc tế đặt 1 quân Hậu trắng tại ô(x,y). Hãy xây dựng CTDL để lưu trạng thái của bàn cờ thể hiện các ô mà 1 quân đen có thể đi vào mà không bị quân Hậu trắng ăn.''

Tức là lưu dữ liệu kiểu gì. Hết. Đề có vậy thôi.

[10520237]

chỉ cần chỉ ra cái cấu trúc dữ liệu cần dùng thôi mà :baffle:

[nhokkoolny]

là sao, ai chỉ mình chi tiết xíu được ko

[11520246]

là sao, ai chỉ mình chi tiết xíu được ko

Quân hậu nó lộn xộn quá, bây h giả sử với quân xe thôi nhá, quân xe chỉ đi ngang-dọc thôi, giả sử nhá!
Thế này nhé, có ông thầy nào đó hỏi em là "Bây giờ trên bàn cờ tui có quân xe màu trắng ở góc trái (bàn cờ 64 ô ^^), thế thì tui cho em cầm quân đen thì em hãy chỉ ra những chỗ nào trên bàn cờ mà em có thể di chuyển quân đen hiện tại của mình để lượt sau quân xe trắng đó của tui không có khả năng ăn quân của em được"

Nói dài dòng nhưng mục đích là như vầy: hãy khoanh vùng/xác định những vị trí an toàn mà quân cờ của bạn có thể đi mà không sợ quân xe trắng của ông thầy.
Rồi về Cấu trúc dữ liệu thì sao? Thì ta biểu diễn nó ra thôi, rõ ràng nhất là bàn cờ có 8 hàng ngang, 8 hàng dọc, tổng cộng là 64 ô, trông giống mảng 2 chiều nhỉ?
Như vậy con xe của ông thầy trong giả sử ở trên hiện nằm ở góc trái, tức vị trí (1,1), như vậy thì phải gắn cờ báo hiệu là nó đang đứng ở đó, vd Bàn Cờ(1,1) = 1 ("Có địch").
rồi từ vị trí (1,1) đó suy ra những vị trí khác mà lượt sau con xe đó có thể đi, rồi nhiệm vụ là đi gắn cờ báo hiệu.
Hic hic dài dòng quá.

[nhokkoolny]

làm vậy đúng chưa
Int A[7][7];
Nhập toạ độ quân hậu trắng (x,y);
Cùng hàng với quân hậu: ko thể đi vào: A[x][i]=0 (0<=i<=7);
Cùng cột với hậu: ko thể đi vào A[i][y]=0 (0<=i<=7);
Có thể dùng 1 dòng for chung
Đường chéo thứ nhất: chỉ số ô này có tính chất :i+j=x+y=ko đổi;
Vậy nếu i+j=x+y thì A[i][j]=0
Đường chéo thứ hai: i-j=x-y;
Vậy nếu i-j=x-y thì A[i][j]=0

[10520237]

làm vậy đúng chưa
Int A[7][7];
Nhập toạ độ quân hậu trắng (x,y);
Cùng hàng với quân hậu: ko thể đi vào: A[x][i]=0 (0<=i<=7);
Cùng cột với hậu: ko thể đi vào A[i][y]=0 (0<=i<=7);
Có thể dùng 1 dòng for chung
Đường chéo thứ nhất: chỉ số ô này có tính chất :i+j=x+y=ko đổi;
Vậy nếu i+j=x+y thì A[i][j]=0
Đường chéo thứ hai: i-j=x-y;
Vậy nếu i-j=x-y thì A[i][j]=0

cái này đâu phải là CTDL :tire:
theo đề ra thì chỉ cần 2 struct là xong chứ mấy.:vip: