ai giải thích giúp mình đoạn code quay lui voi

HTML:
program Combination; 
const 
InputFile = 'SUBSET.INP'; OutputFile = 'SUBSET.OUT'; 
max = 30; 
var 
x: array[0..max] of Integer; 
n, k: Integer; 
f: Text; 
 
procedure PrintResult; (*In ra tập con {x[1], x[2], ¼, x[k]}*) 
var 
i: Integer; 
begin 
Write(f, '{'); 
for i := 1 to k - 1 do Write(f, x[i], ', '); 
WriteLn(f, x[k], '}'); 
end; 
 
procedure Try(i: Integer); {Thử các cách chọn giá trị cho x[i]} 
var 
j: Integer; 
begin 
for j := x[i - 1] + 1 to n - k + i do 
begin 
x[i] := j; 
if i = k then PrintResult 
else Try(i + 1); 
end; 
end; 
 
begin 
Assign(f, InputFile); Reset(F); 
ReadLn(f, n, k); 
Close(f); 
Assign(f, OutputFile); Rewrite(f); 
x[0] := 0; 
Try(1); 
Close(f); 
end.
 

tengiday

Happy life
Bài này in ra tất cả các cách chọn C(n, k). Procedure 'try' sẽ điền số ở từng vị trí 'i' (1 <= i <= k), khi đã điền đủ k số rồi thì xem như có được 1 cách chọn. Số cần điền tại mỗi vị trí i sẽ được chọn trong những số còn lại chưa được chọn. Bạn lưu ý vì cách chọn luôn đc sắp xếp theo thứ tự tăng dần, cho nên những số còn lại chưa đc chọn sẽ đi từ x[i - 1] + 1. Giới hạn trên n - k + i là để tránh duyệt lặp lại, nhưng có thể để chạy tới n cũng được.
 
Bạn giải thích cụ thể hơn chỗ thử các trường hợp cho j mình với
VD
4 2
1 2
1 3
1 4
2 3
2 4
3 4
 

tengiday

Happy life
Biến j chỉ là xét hết các giá trị có thể của x mà thôi. Ví dụ: n = 9, k = 5, giả sử đã có đc:
x = {1, 3, _ , _ , _ }
Bây giờ cần điền vị trí tiếp theo, tức là i = 3. Như vậy, những số đc chọn chỉ có thể từ 4 tới 7 mà thôi (vì x phải tăng dần và còn phải chừa chỗ cho 2 số sau nữa). Vậy j chạy từ 4 tới 7.

Hope it helps.
 
procedure Try(i: Integer); {Thử các cách chọn giá trị cho x}
var
j: Integer;
begin
for j := x[i - 1] + 1 to n - k + i do
begin
x := j;
if i = k then PrintResult
else Try(i + 1);
end;
mình chạy đoạn mã trên với bộ text 4 2 sai chỗ nào bạn chỉnh giup mình nhé
j : = 1 -> 3
x[1] := 1
thử x[2]:= 2.
in ra 1 2
ngang tới đây mình không hiểu nó sẽ thử như thế nào bạn giúp hộ
 

tengiday

Happy life
Khi đã ra tới {1, 2} rồi (khi đó i = 2 và j = 2) thì chương trình "quay lui", sau đó j tăng lên 3 rồi in ra {1, 3} (lưu ý bạn vẫn còn nằm trong vòng for của j khi quay lui cho nên vẫn phải tăng j lên). Bạn nên in ra màn hình từng giá trị i, j, và mảng x; sau đó chạy từng bước một cho dễ thấy (bạn biết dùng debug mode chứ?).
 
procedure Try(i: Integer); {Thử các cách chọn giá trị cho x}
var
j: Integer;
begin
for j := x[i - 1] + 1 to n - k + i do
begin
x := j;
if i = k then PrintResult
else Try(i + 1);
end;
mình chạy đoạn mã trên với bộ text 4 2 sai chỗ nào bạn chỉnh giup mình nhé
j : = 1 -> 3
x[1] := 1
thử x[2]:= 2.
in ra 1 2
tiếp tục j:=3
thử x[2]:= 3
in ra 1 3
bây giờ làm thế nào để lấy được 1 4 hả bạn
khi lấy được 1 4 xong thì nó quay lui về 2
rồi thứ 3.4 ...
 

tengiday

Happy life
Bạn đừng quên còn biến i nữa (vị trí điền số); range của j phụ thuộc vào i. Khi điền x[2] thì i = 2, như vậy n - k + i = 4, tức là j từ 2 tới 4.
Ví dụ: n = 4, k = 2, x = {_ , _}
Mã:
[U][B]i = 1:
[/B][/U]- x = {_ , _}
- j từ 1 tới 3: Lúc này j = 1.
x = {1 , _}
Sau đó ct gọi Try(i + 1) tức là nhảy sang i = 2.
Mã:
[U][B]i = 2:[/B][/U]
- x = {1 , _}
- j từ 2 tới 4.
x = {1 , 2}
Sau đó ct in ra cấu hình {1 , 2}. Rồi j nhảy sang 3 (lưu ý là i vẫn là 2 nhé).
x = {1 , 3}
Sau đó ct in ra cấu hình {1 , 3}. Rồi j nhảy sang 4 (lưu ý là i vẫn là 2 nhé).
x = {1 , 4}
Sau đó ct in ra cấu hình {1 , 4}. Tới đây thì j ko chạy đc nữa. Ct sẽ "quay lui" về [U]giá trị i[/U] trước đó, tức là về i = 1.
Mã:
[U][B]i = 1:[/B][/U]
Bạn xem lại sẽ thấy lúc trc j chỉ chạy tới 1 thôi, sau đó i nhảy sang vị trí khác. Cho nên, bây giờ khi quay lui thì j phải chạy tiếp tới 2. Bởi vậy,
x = {2 , _}
Sau đó ct lại gọi Try(i + 1), tức là i nhảy sang 2.
Tương tự các bc như thế.
 
Top