PDA

View Full Version : phương trình đệ quy



echcoms
12-04-2005, 09:36
ai có thể giúp mình thành lập pt đệ quy của bài toán đệ quy quay lui "8 con hậu không"?

htbn_hoang
12-04-2005, 09:38
Chào, bạn có thể nói rõ hơn được không

echcoms
12-04-2005, 09:54
mình nói sơ qua về cái bài này nhé:
đệ quy quay lui thì chắc ai cũng biết rồi,giải thuật của bài toán của mình như sau:
try(int i)
for(int j = 0;j<=n;j++)
{
if (b[j]) and (c[i+j] ) and (d[i-j])
{
a[i]= j;
b[j]=c[j+i]=d[i-j]=false; //đây là ba biến trạng thái được
//lưu trạng thái có quan hau tren các
//duong dọc ngang và hai đường cheo.
if i= n then thông báo kết quả;
else try(i+1);
}
}
(có thể giải thuật mình code ở đây chưa chuẩn lắm nhưng nói chung tư tưởng là thế)
mục đích của mình là muốn đánh giá độ phức tạp của giải thuật này nhưng chưa thành lập được pt đệ quy của nó.mong mọi người giúp đỡ.thankx

echcoms
12-04-2005, 22:28
không có ai chịu giúp mình sao?

bete
13-04-2005, 00:36
Thân gửi echcom: nếu tui hiểu không sai cách giải của bạn:

Thử đặt con hậu thứ nhứt vô cột thứ nhứt

Khi thử đặt con hậu thứ i vô cột thứ i: thử đặt lần lượt trên 8 dòng; chỉ thực sự đặt trên dòng j nếu dòng j & 2 đường chéo chứa ô (i,j) chưa bị chiếm. Nếu đặt được con hậu thứ i tại ô (i,j) thì thử đặt con hậu thứ (i+1) vô cột (i+1) (đệ qui chỗ này). Khi đặt được con hậu thứ 8 vô cột thứ 8 thì in ra và quay lui

Nếu bạn muốn đánh giá độ phức tạp của cách giải bạn đưa ra thì thử lập luận:

Thử đặt con hậu thứ 8 vô cột 8: phải thử hết 8 dòng ở cột 8 khi đặt con hậu thứ 8
Thử đặt con hậu thứ 7 vô cột 7: phải thử hết 8 dòng ở cột 7 khi đặt con hậu thứ 7; với mỗi dòng: nếu đặt được thì thử đặt con hậu thứ 8
Thử đặt con hậu thứ 6 vô cột 6: phải thử hết 8 dòng ở cột 6 khi đặt con hậu thứ 6; với mỗi dòng: nếu đặt được thì thử đặt con hậu thứ 7
...............
Thử đặt con hậu thứ 1 vô cột 1: phải thử hết 8 dòng ở cột 1 khi đặt con hậu thứ 1; với mỗi dòng: nếu đặt được thì thử đặt con hậu thứ 2

=> tệ nhứt là 8^8; nhưng tui không nghĩ lớn tới như vậy. Bạn có thể thử tìm trên mạng "8 queens". Cũng đã có 1 thread về bài này nhưng hình như chức năng tìm kiếm trên diễn đàn đang bị tạm ngưng

-thân

echcoms
15-04-2005, 10:25
cảm ơn bete.sử dụng phương pháp nhân của bạn là đúng.độ phức tạp của giải thuật này là n^n,phải tính toán với trường hợp xấu nhất.

Mach2
15-04-2005, 12:46
Cho mình comment tí.

Cách vét của bete mô tả trên là O(N^N).
Improve một ít.
- Khi con hậu thứ nhất được đặt ở hàng thứ nhất thì chỉ còn 7 trường hợp có thể đặt con hậu thứ 2 ở hàng thứ hai và cứ thế. Như vậy thì chỉ còn O(N!) mà thôi.
Improve thêm.
- Khi con hậu thứ nhất được đặt ở hàng thứ nhất thì xét trên hai đường chéo đi ngang qua nó có thể loại bỏ thêm 1-2 vị trí nữa ở hàng thứ hai (và cả trên các hàng kế tiếp). Ở hàng thứ 3 thay vì có 6 cách đặt (như ở trên) thì chỉ còn 6-1(hay 2 do ảnh hưởng con hậu thứ 1)-1(hay 2 do ảnh hửơng con hậu thứ 2). Tiếp tục như vậy thì có thể improve thêm một ít. Complexity lúc này tính chính xác thì ko được, chỉ có nước ước lượng. Với trường hợp 8 thì còn < 8*6*4*2 tests. Có thể xấp xỉ tương đối là N!-(N-1)!-(N-2)!... Nói chung vẫn rất lớn.

Hình như là bài toán này hiện nay chỉ giải được đến N=24 do hạn chế của máy tính (đối với yêu cầu vét toàn bộ feasible solutions).

bete
15-04-2005, 12:53
Thân gửi mach2: 2 bước làm cho nhanh hơn như bạn đề nghị đã được cài đặt trong cách giải nguyên thủy của echcoms (3 biến trạng thái: dòng & 2 đường chéo) => tui không dám nói là O(n^n) mà chỉ dám nói "tệ nhứt là....". Nhưng công thức ước lượng của mach2: N!-(N-1)!-(N-2)!... => chính xác hơn sự ước lượng n^n của tui rất nhiều :)

-thân

netwalker
15-04-2005, 21:52
tui thấy với mấy bài toán cơ bản như vầy mình nói miệng = thuật toán chứ đừng ghi ra code
như vầy còn khó hiểu hơn nữa

Ngoc iu
13-10-2009, 22:37
các bạn ơi chỉ mình cách thành lập phương trình đệ quy cau bài toán 8 hậu với

JackDaiHiep
14-10-2009, 17:25
Cái này trên mạng code với giải thích nhiều lắm, hình như trong sách toán tin cũng có nhiều sách giải rồi mà. còn nếu tự nghĩ thì kể ra cũng thú vị đấy, he he, đọc sách toán rời rạc nhé