Kết quả 41 đến 47 của 47
-
07-27-2016, 04:48 AM #41Junior Member
- 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;
-
07-27-2016, 04:48 AM #42Silver member
- Ngày tham gia
- Jan 2016
- Bài viết
- 0
Gửi bởi vansonqtqb
- 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.
-
07-27-2016, 04:48 AM #43Junior Member
- 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 ĐỠ..
-
07-27-2016, 04:48 AM #44Junior Member
- Ngày tham gia
- Aug 2015
- Bài viết
- 0
lên top nhé bạn hiền ơi
-
07-27-2016, 04:48 AM #45Junior Member
- 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
i = 5
Mã:t 10 10 5 5 5 x 0 0 0 0 1 sum = 0 - 0 + 5 = 5
i = 4
Mã:t 10 10 5 5 5 x 0 0 0 1 0 sum = 5 - 5 + 5 = 5
Mã:t 10 10 5 5 5 x 0 0 0 1 0 sum = 5
i = 5
Mã:t 10 10 5 5 5 x 0 0 0 1 1 sum = 5 - 0 + 5 = 10
i = 3
Mã:t 10 10 5 5 5 x 0 0 1 0 0 sum = 10 - 5 - 5 + 5 = 5
Mã:i = 4: x 0 0 1 0 0 i = 5: x 0 0 1 0 0
Mã:i = 5: x 0 0 1 0 1
Mã:i = 4: x 0 0 1 1 0 i = 5: x 0 0 1 1 0
Mã:i = 5: x 0 0 1 1 1
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.
-
07-27-2016, 04:48 AM #46Junior Member
- 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..
-
07-27-2016, 04:48 AM #47Junior Member
- Ngày tham gia
- Aug 2015
- Bài viết
- 0
Gửi bởi vansonqtqb
Mã:t 10 10 5 5 5 x 0 0 0 0 1 sum = 0 - 0 + 5 = 5
Mã:t 10 10 5 5 5 x 0 0 0 1 1 sum = 5 - 5 + 5 = 5
- Để 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;
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.
Giới thiệu về Dây Cáp Điện Cadivi Dây cáp điện Cadivi là sản phẩm chất lượng cao, được sản xuất bởi Tập đoàn Cadivi - một trong những công ty hàng đầu trong lĩnh vực sản xuất dây cáp điện tại Việt...
Dây Cáp Điện Cadivi - Giá Tốt Cho...