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

Thống kê

Chủ đề
100,752
Bài viết
467,582
Thành viên
339,851
Thành viên mới nhất
Đông Âu

Bài viết được quan tâm nhiều

Top