chỗ sai của 1 bài tập quay lui

[metoodiep247]

Xin các anh chị giúp em bài tập này ạ.
Đề: Cho danh sách tên của n học sinh(n<=10) (các tên đôi một khác nhau) và số nguyên dương k(k<=n). Hãy liệt kê tất cả các cách chọn k học sinh trong n học sinh
​ Ví dụ:
Dữ liệu vào
Kết quả ra
N=4; k=2
Danh sách tên học sinh:
An
Binh
Hong
Minh
6 cách chọn
1. An Binh
2. An Hong
3. An Minh
4. Binh Minh
5.Binh Hong
6.Hong Minh
em đã viết chương trình như sau:
​

const
fo='tenhs.inp';
fi='tenhs.out';
type mang=array[1..20] of string[7];
var
f:text;
a,b:mang;
n,k:integer;
procedure inputdata;
var
f:text;
i:integer;
begin
assign(f,fo);reset(f);
readln(f,n,k);
for i:=1 to n do readln(f,b);
close(f);
end;
procedure xuat;
var
i:integer;
begin
for i:=1 to k do write(f,a,' ');
writeln(f);
end;
procedure xuli(i:integer);
var
j:integer;
begin
for j:=i to n-k+1 do
begin
a:=b[j];
if (i=k) then xuat
else xuli(i+1);
end;
end;
begin
assign(f,fi);rewrite(f);
inputdata;
xuli(1);
close(f);
end.

và nó hiện ra như thế này:
An Binh
An Hong
Binh Binh
Binh Hong
Hong Binh
Hong Hong
​Xin các anh chị giúp em tìm chỗ sai ạ!



​

[thienan]

Vì cách làm đệ quy của mình khác của bạn nên đành tự viết 1 chương trình vậy:

const vao='tenhs.inp';
ra='tenhs.out';

var fi,fo:text;
free:array[1..20]of boolean;
a:array[1..20]of string[7];
i,n,k:longint;

procedure nhap;
begin
assign(fi,vao); reset(fi);
assign(fo,ra); rewrite(fo);
readln(fi,n,k);
for i:=1 to n do readln(fi,a);
close(fi);
end;

procedure xuat;
var i1:longint;
begin
for i1:=1 to n do
if not free[i1] then write(fo,a[i1],' ');
writeln(fo);
end;

procedure chon(so,ht:longint);
var i1:longint;
begin
if n-ht<so then exit;
for i1:=ht to n do
if free[i1] then
begin
free[i1]:=false;
if so=k then xuat
else chon(so+1,i1);
free[i1]:=true;
end;
end;

begin
nhap;
fillchar(free,sizeof(free),true);
chon(1,1);
close(fo);
end.

Mới thử với test bạn đưa, bạn thử các test khác, nếu có chỗ sai bảo mình để kiểm tra nhé

[bigrat96]

Xin cảm ơn đã giúp đỡ! Với giải thuật này luongminh sẽ về thử các text khác, và với giải thuật ban đầu của luongminh (theo giải thuật quay lui vét cạn tổ hợp) chưa hoàn chỉnh thì xin anh chị giúp luongminh tìm chỗ sai để biết đường làm lại. Xin cảm ơn.

[nguyenvietanh123]

Bài của bạn sai 2 chỗ như thế này:
- Duyệt không đủ hết đến giá trị thứ N (trong test vd bạn đã mất Minh).
- Khi duyệt một tên rồi, chương trình của bạn có thể lặp lại việc duyệt trùng VD như:
4 2
An
Binh
Hong
Minh

Tại phần duyệt An, thì đã có An Binh, An Hong, An Minh.
Qua đến duyệt Binh, tuy là băt đầu bỏ duyệt An nhưng bạn vẫn còn vướng Binh -> Binh Binh.
Tuy Hong Binh và Binh Hong là một, chương trình của bạn vẫn đưa ra 2 đáp án, vì khi duyệt Hong, tập nghiệm của bạn có chứa Binh.

Tớ đề nghị như sau:
- Sửa mảng a thành lưu chỉ số chứ không lưu tên.
- Sửa lại vòng lặp trong đệ quy: for j:=a[i-1]+1 to n do. Làm 2 công việc a=j. Và xét xuất hoặc đệ quy lên i+1.
Thân! [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[nhungdo]

Bài của bạn sai 2 chỗ như thế này:
- Duyệt không đủ hết đến giá trị thứ N (trong test vd bạn đã mất Minh).
- Khi duyệt một tên rồi, chương trình của bạn có thể lặp lại việc duyệt trùng VD như:
4 2
An
Binh
Hong
Minh

Tại phần duyệt An, thì đã có An Binh, An Hong, An Minh.
Qua đến duyệt Binh, tuy là băt đầu bỏ duyệt An nhưng bạn vẫn còn vướng Binh -> Binh Binh.
Tuy Hong Binh và Binh Hong là một, chương trình của bạn vẫn đưa ra 2 đáp án, vì khi duyệt Hong, tập nghiệm của bạn có chứa Binh.

Tớ đề nghị như sau:
- Sửa mảng a thành lưu chỉ số chứ không lưu tên.
- Sửa lại vòng lặp trong đệ quy: for j:=a[i-1]+1 to n do. Làm 2 công việc a=j. Và xét xuất hoặc đệ quy lên i+1.
Thân! [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Khó sửa nhỉ hì hì. Binhnguyen xem luôn hộ anh xem code anh còn chỗ nào sai không? Code xong test mỗi test bạn chủ pic đưa lên rồi post bài, chắc không tránh khỏi sai xót.

[daohoa]

Xin cảm ơn rất nhiều ạ. Em sẽ về thử bằng chương trình và các bộ text khác nhau.
Còn với đề bài khó nuốt dưới đây xin mọi người hãy gợi ý cho em hướng giải ạ.
Đề: Cho số nguyên dương N (N<=10000). Hãy thêm các dấu '+' hoặc '-' vào dãy 1....n bằng với tổng số k cho trước.
Hình như là quay lui tìm mọi nghiệm.

[bebannha]

Xin cảm ơn rất nhiều ạ. Em sẽ về thử bằng chương trình và các bộ text khác nhau.
Còn với đề bài khó nuốt dưới đây xin mọi người hãy gợi ý cho em hướng giải ạ.
Đề: Cho số nguyên dương N (N<=10000). Hãy thêm các dấu '+' hoặc '-' vào dãy 1....n bằng với tổng số k cho trước.
Hình như là quay lui tìm mọi nghiệm.

Nếu tìm mọi nghiệm thì không làm được với n quá 30 đâu bạn.
Bài này hình như có công thức qhd thì phải, lâu rồi không nhớ.

[jaybee]

ui, xin lỗi anh nhưng em đang học về giải thuật quay lui nên với bài này em chỉ có thể dùng quay lui thôi ạ(không thể quy hoạch động đc ạ). Mong anh chị giúp em cách quay lui!
Theo em nghĩ với bài này sẽ dùng tới 4 mảng:
x:array[1..max] of char;{chứa các chữ số 1..n(dùng khi xuất)}
s:array[1..max] of '+'..'-';{thêm dấu vào nếu thỏa đk(dùng vào khi xuất)}
a:array[1..max] of 0..1;{nếu dùng để xem phần tử nào đã chọn rồi}
b:array[1..max] of longint;{chứa giá trị các số 1...n}
Không biết các anh chị nghĩ thế nào ạ?

[metoodiep247]

Nếu đành phải làm = quay lui thì chịu rồi, nhưng cùng lắm code của bạn cũng chỉ chạy được tới n=25 là còn chấp nhận được.
Bài này sử dụng quay lui tìm các dãy nhị phân độ dài n-1. Code có trong quyển ebook DSAP của thầy Lê Minh Hoàng rồi, luongminh nên đọc quyển đó, rất hay. Còn vì sao lại là nhị phân thì vì chỉ có thể chèn vào + hoặc - nên với mỗi vị trí giữa 2 số, ta có 2 cách chọn dấu, từ đó => nhị phân. Và bạn chỉ cần dùng 2 mảng thôi: 1 mảng chứa các số nhập vào, 1 mảng là 0,1 tương ứng với + hoặc - . Và việc in ra thì in xen kẽ 2 mảng này với nhau là ok.

[sccom123]

vâng em đã đọc cuốn sách đó rồi ạ. Thật là rất hay nhưng trình độ của em quá kém, phải mất gần 1 ngày hẳn hoi mới hiểu trọn vẹn 1 phương pháp sinh (huống hồ là những cái khó hơn). Còn đối với bài này làm theo cách của anh thì đúng song em đã thử rồi và gặp lỗi, lỗi nhỏ thôi đó là không cần điều kiện:
if n-t<i then exit;
.......
​trong thủ tục ghi nghiệm vào file cũng không cần đến câu lệnh:
if not free then.......
​Còn đối cách mà anh binhnguyenLQD-kg đề cập đến em đã thử qua rồi nhưng không ra. Chắc tại viết sai nên chẳng ra kết quả gì cả. Nếu mọi người biết cách viết giải thuật chính thì xin chỉ giáo ạ!