# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  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;
> ...


_
 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;
> ...


_
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
> 
> ...


_
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 ạ!_

----------


## taitrochoifree11

Cái if bên trên bạn nói mình chưa nghĩ hẳn hoi về nó nhưng thông thường đó là những lệnh an toàn để giúp bạn thoát khỏi chương trình con, còn câu lệnh bên dưới là cần thiết vì những cái nào có free=false là những cái mình chọn, bỏ đi thì sẽ in sai.

----------


## teenddeem

Mình chép bài của bạn rồi sửa tí, mình chưa thử test nào sai, bạn thử test thử xem:


```
const
              fo='tenhs.inp';
              fi='tenhs.out';
type mang=array[1..20] of string[7];
var
       f:text;
       b:mang;
       a:array[0..10] of byte;
       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[i]);
          close(f);
end;
procedure xuat;
var
        i:integer;
begin
         for i:=1 to k do write(f,b[a[i]],' ');
         writeln(f);
end;
procedure xuli(i:integer);
var
         j:integer;
begin
         for j:=a[i-1]+1 to n do
              begin
                      a[i]:=j;
                      if (i=k) then xuat
                         else xuli(i+1);
             end;
end;
Begin
          assign(f,fi);rewrite(f);
          inputdata;
          xuli(1);
          close(f);
End.
```

À còn bài điền phép toán mà N=1000 thế kia thì tớ chào thua, không thể quay lui

----------


## chimlonvng5

xin lỗi anh Ginta_ITFam nhưng khi em thử thì không in ra đc Hồng Minh ạ.
Còn với bài n=1000 thì chắc em sẽ suy nghĩ khá khá lâu để tìm ra phương pháp.
Và xin mời mọi người lại cùng em sửa chữa 1 bài tập quay lui nửa, xin hãy giúp đỡ
Đề: 4.4:Cho số nguyên dương n(n<=20), hãy liệt kê tất cả các xâu độ dài n chỉ gồm hai kí tự A và B sao cho không có 2 kí tự B nào đứng cạnh nhau.
​ Ví dụ: 
Dữ liệu vào
Kết quả ra
N=4
AAAB
AABA
ABAA
ABAB
BAAA
BAAB
BABA

và em đã viết chương trình như sau: 

[IMGRIGHT]const
fo='xau.inp';
fi='xau.out';
var
a:string[20];
n:byte;
f:text;
procedure inputdata;
var
f:text;
begin
assign(f,fo);reset(f);
read(f,n);
close(f);
end;
procedure init;
var
i:byte;
begin
for i:=1 to n do a:=a+'A';
end;
function thoadk(x:string[20]):boolean;
begin
thoadk:=(pos('BB',x)=0)=true;
end;
procedure xuat;
begin
writeln(f,a);
end;
procedure xuli(i:byte);
var
j:char;
begin
for j:='A' to 'B' do
begin
a_:=j;
if (i=n)and thoadk(a) then xuat
else xuli(i+1);
end;
end;
{-----------------}
begin
assign(f,fi);rewrite(f);
inputdata;
init;
xuli(1);
close(f);
end.
[/IMGRIGHT]
em viết trên FreePascal-2.2.0 thế là nó hiện lỗi là 

 program
  exited with
 exitcode = 201
​Mong anh chị giúp em tìm chỗ sai ạ.

_

----------


## new led

a, xin lỗi ạ. Bài này em đã làm đc rồi, em sẽ post lên để các anh chị xem sau. Còn vấn đề nan giải của em chính là bài đây ạ:
Đề:Đề: Cho xâu S (độ dài không quá 10) chỉ gồm các kí tự 'A' đến 'Z' (các kí tự trong xâu S không nhất thiết phải giống nhau). Hãy liệt kê tất cả các hoán vị khác nhau của xâu S.
Ví dụ:
s='aba'
CÁc hoán vị là:
aab
aba
baa
​Và lập trình như sau:
const
fi='xau.inp';
fo='xau.out';
var
f:text;
s:string[10];
a:array[1..10] of integer;
procedure inputdata;
begin
assign(f,'xau.inp');reset(f);
readln(f,s);
close(f);
end;
procedure init;
var
i:integer;
begin
for i:=1 to length(s) do a_:=i;
end;
procedure xuat;
var
i:integer;
begin
for i:=1 to length(s) do write(f,b);
writeln(f);
end;
procedure xuli(i:integer);
var
j:integer;
begin
for j:=a[i-1]+1 to length(s) do
begin
s:=s[j];
if (i=length(s)) then xuat
else xuli(i+1);
end;
end;
begin
assign(f,fo);rewrite(f);
inputdata;
init;
xuli(1);
close(f);
end.Và em gặp lỗi giống như bài trên kia vậy. Mong các anh chị giúp đỡ em.
​_

----------


## Thinhquang75

[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) sr bạn, đúng là mình không chú ý về code của mình lắm. Bạn xóa dòng if n-t>... đi là ok. Lỗi bạn mắc phải là lỗi tràn mảng, lỗi này mắc phải khi bạn động tới vị trí 0 của mảng và vì bạn chỉ khai báo mảng 1->... nên bị lỗi. Bạn sửa lại code của bạn, khai báo thêm vị trí 0 xem đúng chưa.

----------


## niemdamme23

xin cảm ơn sự giúp đỡ của anh Ginta_ITFam.

----------


## dunghoang

Mình giúp nhưng liệu bạn đã hoàn thiện được bài của mình chưa? Nếu chưa thì mình không dám nhận lời cảm ơn đâu [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Bạn có thể lên google search bảng mã exit code free hoặc bảng lỗi runtime để tìm hiểu các lỗi mà trong free bạn có thể gặp phải, như thế sẽ chủ động hơn trong khi làm bài.

----------


## benjamin239

a, bài của anh Ginta_ITFam em đã hoàn thiện, cùng với giải thuật của anh binhnguyenLQD-kg em cũng bổ sung thêm rồi ạ. Còn về lỗi thì thật em chẳng nghĩ ra phải làm sao, xin cảm ơn sự giúp đỡ của anh lần nữa!

----------

