kết quả từ 1 tới 8 trên 8

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

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

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

    HTML Code:
    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.
    Quick reply to this message Trả lời       

  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

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

    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

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Biến j chỉ là xét hết các giá trị có thể của x[i] 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.

  5. #5
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

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

    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;
    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ộ

  6. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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ứ?).

  7. #7
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

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

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

  8. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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ã:
    i = 1:
    - 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ã:
    i = 2:
    - 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ề giá trị i trước đó, tức là về i = 1.
    Mã:
    i = 1:
    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ế.