Trang 5 của 5 Đầu tiênĐầu tiên ... 345
Kết quả 41 đến 47 của 47
  1. #41
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    cam ơn bạn mình cũng hiểu cách đánh dãy nhị phân trong mảng x để được tờ tiền cần lấy nhưng thật sự mình ko hiểu thủ tục đệ quy quay lui này hoặt động như thế nào
    procedure backTrack(i:longint);
    var j :longint;
    begin
    for j:=0 to 1 do begin
    x[i]:=j;
    sum:=sum + x[i]*t[i];
    if (i=n) then check(x)
    else if sum<=s then backTrack(i+1);
    if ok then exit; {nếu ñã tìm ñược nghiệm thì không duyệt nữa}
    sum:=sum - x[i]*t[i];
    mong bạn giải thích giải thuật này cho mình với ak..
    end;
    end;

  2. #42
    Ngày tham gia
    Jan 2016
    Bài viết
    0
    Trích dẫn Gửi bởi vansonqtqb
    cam ơn bạn mình cũng hiểu cách đánh dãy nhị phân trong mảng x để được tờ tiền cần lấy nhưng thật sự mình ko hiểu thủ tục đệ quy quay lui này hoặt động như thế nào
    procedure backTrack(i:longint);
    var j :longint;
    begin
    for j:=0 to 1 do begin
    x[i]:=j;
    sum:=sum + x[i]*t[i];
    if (i=n) then check(x)
    else if sum<=s then backTrack(i+1);
    if ok then exit; {nếu ñã tìm ñược nghiệm thì không duyệt nữa}
    sum:=sum - x[i]*t[i];
    mong bạn giải thích giải thuật này cho mình với ak..
    end;
    end;
    - Tại mỗi 1 tờ tiền thứ i thì chỉ có 2 khả năng: chọn (x[i] = 1) và không chọn (x[i] = 0). Dòng loop 'for' là duyệt 2 lựa chọn này. Cụ thể, x[i] := j có nghĩa là chọn hoặc không chọn tờ tiền thứ i tùy theo giá trị của j (0 hoặc 1).

    - Cho dù là chọn hay không thì mình cũng phải tính lại tổng của mấy tờ tiền cho tới hiện tại. Biến 'sum' sẽ làm điều này.
    Giả sử ko chọn tờ i, tức là x[i] = 0, như vậy sum ko đổi phải không bạn? Khi đó x[i] * t[i] = 0.
    Giả sử mình chọn tờ i, tức là x[i] = 1, như vậy sum này phải cộng vào cho giá trị của tờ tiền thứ i, tức là sum + t[i] (vì khi đó x[i] * t[i] = t[i]).

    - Sau khi đã duyệt hết n tờ tiền (i = n) thì kiểm tra xem đã lấy đủ số cần thiết chưa. Nếu vẫn chưa duyệt hết n tờ và cũng chưa lấy đủ tiền thì duyệt tiếp tờ tiền tiếp theo i + 1.

    - Giả sử mình duyệt hết n tờ nhưng chưa tìm đc kết quả, như vậy là có mấy tờ mình chọn sai. Bởi vậy, mình phải "quay lui". Khi quay lui thì phải trừ cho biến 'sum' vì hồi nãy mình cộng vào x[i]*t[i] rồi. Biến 'sum' là tổng tiền hiện tại tới bước i, khi quay lui thì phải trừ biến này đi cho giá trị tiền thứ i (nếu ko chọn thì nó là trừ 0, chẳng sao cả).

    Mình nghĩ bạn nên dùng debug, đem mấy biến bỏ vào watch để xem giá trị của nó theo mỗi bước như thế nào. Lâu rồi mình ko còn dùng Pascal nữa, quên hết mấy menu với thao tác chính. Bạn có thể hỏi thầy xem làm thế nào nhé. Cách này sẽ giúp cho bạn hiểu thêm về thuật toán. Đệ quy này đưa giá trị làm ví dụ cụ thể sẽ dài lắm, nên tốt nhất bạn nên xem ngay trên máy.

  3. #43
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    mình thử lấy 1 ví dụ như thế này.
    Vd
    5 15
    10 10 5 5 5
    atm.out
    5 5 5
    NHỜ BẠN CÓ THỂ PHÂN TÍCH CÁI VD NÀY CHO MÌNH DK KO AK
    MÌNH MỚI HOC QUAY LUI NÊN THÂT SỰ LÀ LANG MANG QUÁ.MONG BAN GIÚP ĐỠ..

  4. #44
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    lên top nhé bạn hiền ơi

  5. #45
    Ngày tham gia
    Aug 2015
    Bài viết
    23
    Lượt đầu i từ 1 tới 5 sẽ không có thay đổi vì ko chọn tờ tiền nào cả.
    i = 1
    Mã:
    t     10  10   5   5   5
    x      0   0   0   0   0
    sum = 0
    ...
    i = 5
    Mã:
    t     10  10   5   5   5
    x      0   0   0   0   0
    sum = 0
    Tiếp theo là quay lui; khi quay lui thì tờ tiền thứ 5 sẽ được chọn lại (hồi nãy là ko chọn).
    i = 5
    Mã:
    t     10  10   5   5   5
    x      0   0   0   0   1
    sum = 0 - 0 + 5 = 5
    Vì check fails nên chúng ta phải quay lui tới tờ tiền thứ 4
    i = 4
    Mã:
    t     10  10   5   5   5
    x      0   0   0   1   0
    sum = 5 - 5 + 5 = 5
    i = 5
    Mã:
    t     10  10   5   5   5
    x      0   0   0   1   0
    sum = 5
    Một lần nữa, sum vẫn ko bằng s (check vẫn fail), nên phải quay lui về tờ thứ 5.
    i = 5
    Mã:
    t     10  10   5   5   5
    x      0   0   0   1   1
    sum = 5 - 0 + 5 = 10
    Vì check fails nên phải lui tới tờ thứ 3.
    i = 3
    Mã:
    t     10  10   5   5   5
    x      0   0   1   0   0
    sum = 10 - 5 - 5 + 5 = 5
    Tương tự, bạn có thể quan sát giá trị của mảng x ở các bước sau:
    Mã:
    i = 4: x      0    0   1   0   0
    i = 5: x      0    0   1   0   0
    Quay lui
    Mã:
    i = 5: x      0    0   1   0   1
    Quay lui
    Mã:
    i = 4: x      0    0   1   1   0
    i = 5: x      0    0   1   1   0
    Quay lui
    Mã:
    i = 5: x      0    0   1   1   1
    Đây chính là kết quả vì đã bằng s.

    PS:
    1) Mình quên mất một điều quan trọng. Khi quay lui, nếu gặp x[i] = 1 thì phải lui thêm một lần nữa nhé bởi vi khi đó hết vòng lặp j, function sẽ ngưng luôn với giá trị của i tại đó.
    2) Nhận xét: bạn lưu ý mảng x, tưởng tượng nó là dãy nhị phân của 1 số thì sẽ thấy cách duyệt này chẳng qua là đọc dãy nhị phân tăng dần từ số 0. Ví dụ:
    00000 -> 0
    00001 -> 1
    00010 -> 2
    00011 -> 3
    00100 -> 4
    00101 -> 5
    00110 -> 6
    ......
    Như vậy có thể ko cần tới đệ quy (dùng 2 vòng loop) vẫn xét được tổ hợp các tờ tiền.

  6. #46
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    cảm ơn bạn...thuật toán này nếu sử dùng vong loop for chắc sẽ đễ hiểu hơn nhiểu. vì bài này họ làm bằng đệ quy quay lui nên do mình mới làm quen.thật khó để hình dung.Khi quay lui, nếu gặp x[i] = 1 thì phải lui thêm một lần nữa bạn có thể lấy ví dụ minh họa cho đoạn này được ko bạn..

  7. #47
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi vansonqtqb
    cảm ơn bạn...thuật toán này nếu sử dùng vong loop for chắc sẽ đễ hiểu hơn nhiểu. vì bài này họ làm bằng đệ quy quay lui nên do mình mới làm quen.thật khó để hình dung.Khi quay lui, nếu gặp x[i] = 1 thì phải lui thêm một lần nữa bạn có thể lấy ví dụ minh họa cho đoạn này được ko bạn..
    Được chứ bạn. Ví dụ nằm ngay phía trên; cụ thể là ở bước này:
    Mã:
    t     10  10   5   5   5
    x      0   0   0   0   1
    sum = 0 - 0 + 5 = 5
    Khi đó sum <> s, bởi vậy phải "quay lui". Tuy nhiên, lúc đó x[5] = 1 rồi, vòng loop lúc đó đã hết, bởi vậy "đệ quy" phải lui ra ngoài 1 tầng nữa, tức là i = 4. Bởi vậy bạn thấy bước tiếp theo là
    Mã:
    t     10  10   5   5   5
    x      0   0   0   1   1
    sum = 5 - 5 + 5 = 5
    Số 1 ở vị trí x[5] (in đậm, gạch chân) là vẫn còn trong bộ nhớ nhé, nhưng nó ko đc xét vì i của chúng ta hiện giờ chỉ là 4 thôi (xem như mảng x có 4 phần tử). Mình ghi 0 ở bài trước cho dễ nhìn, chứ thật ra nó là 1 đấy.

    - Để tránh đệ quy, viết vòng loop cho nhanh thì phải xử lý bit mới được. Đoạn code của nó sẽ như thế này. Ko cần mảng x hay xs gì cả.


    Mã:
    k := 1 shl n;     // Tập hợp gồm n phần tử sẽ có 2^n tập con.
    for i := 0 to k-1 do
       begin
          sum := 0;
          for j := 0 to n-1 do
             if ((i shr j) and 1) = 1 then
                sum := sum + t[j + 1];
          if sum = s then
             begin
                for j := 0 to n-1 do
                   if ((i shr j) and 1) = 1 then write(t[j + 1],' ');
                exit;
             end;
       end;
    shl = shift left, có sẵn trong Pascal.
    shr = shift right, có sẵn trong Pascal.
    and = bitwise and.
    Quy tắc của nó là với mỗi số i (tượng trưng cho 1 sự lựa chọn), mình kiểm tra xem bit thứ j của nó có bằng 1 hay không; nếu có tức là tờ thứ j đc chọn nên phải cộng vào 'sum'.
    Khuyết điểm của cách này là ở biến k (và biến i một cách gián tiếp). Vì k=2^n, chí có trong C/C++ hay chương trình có số lớn mới tình đc biến k này mà ko bị tràn biến. Trong Pascal, nếu dùng số nguyên chỉ chịu được n = 31 - 32 là hết cỡ. Tuy nhiên, khi đó thời gian chạy lâu lắm (phải chạy tới hơn 20 tỉ lần, bởi cái cách duyệt từng tổ hợp này chỉ là giải pháp cuối cùng.

 

 
Trang 5 của 5 Đầu tiênĐầu tiên ... 345

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
Múi giờ GMT +7. Bây giờ là 10:20 AM.
Diễn đàn sử dụng vBulletin® Phiên bản 4.2.5.
Bản quyền của 2021 vBulletin Solutions, Inc. Tất cả quyền được bảo lưu.
Ban quản trị không chịu trách nhiệm về nội dung do thành viên đăng.