quay lui

[damnguyenhuu]

Một bàn có 4 chỗ ngồi ; có tất cả 6 bàn . Hãy tìm tất cả các cách sắp xếp các học sinh dự thi sao cho một học sinh k có các bạn cùng trường ngồi xung quanh . Lưu ý tất cả các trường hợp đối xứng ( tâm , Ox , Oy ... ) được coi là 1 cách

///
/a/
///
/ : không phải là học sinh cùng trường với học sinh a

Dữ liệu vào : số thí sinh dự thi ( n,m<24 )
dòng 1 gồm các số báo danh của học sinh trường 1
dòng 2 gồm các số báo danh của học sinh trường 2
...
dòng m gồm các số báo danh của học sinh trường m

Dữ liệu ra : tất cả các cách sx

[quangtq]

Nếu quay lui thuần túy thì sẽ phải thử 24! cách. Con số này quá lớn.
Đang tìm cách cắt nhánh

[mini_bestboy]

Làm thì được mà chả biết bỏ mấy cái đối xứng sao cả, Hix. Mà tới bài đệ quy quay lui chưa anh damnguyenhuu ?

[happyman_1x]

chỉ giải được nếu m=9. Nhìn từa tựa như bài toán suduko!

[chick chick]

Nếu quay lui thuần túy thì sẽ phải thử 24! cách. Con số này quá lớn.
Đang tìm cách cắt nhánh

đây là phần học ơc bản mà, không quan trọng thời gian

[quangtq]

Hả. Nếu như anh nói thế thì thử thật 24! cách à?
Cứ cho đặt 1 người vào 1 chỗ mất 1/1000s.
Thế phải mất 24!/1000 s. Ai ngồi chờ máy chạy được.

[hang_vt]

đây là phần học ơc bản mà, không quan trọng thời gian

- Đề thi hs giỏi năm 2002-2003 BR-VT ( năm đó vẫn còn thi viết )
- Có 1 số nhận định cho rằng , bài này chỉ có thể vik đc trên giấy mới có điểm ( chấm điểm ý tưởng )
- Tìm tất cả các cách thì chỉ có cách quay lui
- Vẽ ra thì có thể thấy , mỗi trường chỉ có thể tối đa 6 hs
- K giống suduku đâu vì mỗi hàng có thể có 2 hs cùng trường , có thể có chỗ trống

[chick chick]

nếu chỉ hỏi số cách thì có thể tính bằng tổ hợp
nhưng bắt liệt kê thì chắc chỉ có vét cạn là phù hợp

[quangtq]

Nhưng vét thế thì = killer. Phải có cách cắt nhánh chứ

[hang_vt]

c cũng chưa có code bài này . Nói chính xác hơn là chưa bik vik =)) . Nhưng chắc chắn chỉ có thể là quay lui

[=========> Bổ sung bài viết <=========]


nếu chỉ hỏi số cách thì có thể tính bằng tổ hợp
nhưng bắt liệt kê thì chắc chỉ có vét cạn là phù hợp
wat ?
-----------------

[chick chick]

Nhưng vét thế thì = killer. Phải có cách cắt nhánh chứ

thực ra tớ vẫn chưa hiểu hết đề,
"Hãy tìm tất cả các cách sắp xếp các học sinh dự thi sao cho một học sinh k có các bạn cùng trường ngồi xung quanh"
vậy có bao nhiêu học sinh cùng trường?

[damnguyenhuu]

Anh ví dụ như thế này nha. Cái này chỉ là một trường hợp nho nhỏ thôi.

c b c
d a d
c b c

[hang_vt]

:( ,bài k thể tìm ra tất cả các cách , lại còn xét đối xứng nữa
thua cá độ ùi

[=========> Bổ sung bài viết <=========]



vậy có bao nhiêu học sinh cùng trường?

có tối đa 24 hs thì có tối đa 24 trường và có tối đa 24 hs cùng trường

[chick chick]

nhận xét cuối cùng: quay lui có cải tiến là tốt nhất

[hang_vt]

chẳng có cách nào , sửa đề đi 1 tí thì đc :))

[mini_bestboy]

Thế có ai chỉ mình cách xét đối xứng không vậy :( , nghĩ tới nghĩ lui cũng không nghĩ ra, chài .

[hang_vt]

k có phương pháp giải tối ưu cho bài này . Đề cải tiến 1 tí : xếp liên tục , k có chỗ trống . Chỉ in ra 1 cách :)) . Mình code rồi mà chẳng ra , ai coi giúp ik
inp
1 2 3
4 5
6 7 8
9 10
11 12 13
14 15 16
17 18 19
20 21 22 23
24

out
1 4 2 5
6 9 7 10
3 11 14 15
8 20 17 21
15 13 16 24
18 22 19 23



const fi='xepcho.inp';
fo='xepcho.out';

var f:text;
t: array [0..100] of integer;
a: array [1..100] of integer;
dd:array [1..100] of boolean;
x: array [0..100,0..100] of integer;
m,n,k:integer;

procedure inp;
var i,j:integer;
begin
assign(f,fi);
reset(f);
while not eof(f) do
begin
inc(n);
while not eoln(f) do
begin
inc(m);
read(f,a[m]);
t[a[m]]:=n;
end;
readln(f);
end;
close(f);
for j:=1 to 4 do
x[0,j]:=0;
for i:=1 to 6 do
x[i,0]:=0;
fillchar(dd,sizeof(dd),true);
t[0]:=0;
end;

procedure pri;
var i,j:integer;
begin
for i:=1 to 6 do
begin
for j:=1 to 4 do
write(f,x[i,j],' ');
writeln(f);
end;
close(f);
halt;
end;

function kt(k,i,j:integer):boolean;
var h:integer;
begin
kt:=false;
for h:=1 to 3 do
if (t[a[k]]=t[x[i-1,h]]) then exit;
if (t[x[i,j-1]]<>t[a[k]]) then kt:=true;
end;

procedure try(i,j:byte);
begin
for k:=1 to m do
if (dd[a[k]]) and (kt(k,i,j)) then
begin
x[i,j]:=a[k];
dd[a[k]]:=false;
if (i=6) and (j=4) then pri
else
if j=4 then try(i+1,1)
else
try(i,j+1);
dd[a[k]]:=true;
end;
end;

begin
inp;
assign(f,fo);
rewrite(f);
try(1,1);
close(f);
end.