Giải thích giúp mình thuật toán của bài này cho minh với( khó quá)

V

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:=j;
sum:=sum + x*t;
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*t;
mong bạn giải thích giải thuật này cho mình với ak..
end;
end;
 
T

tengiday

Happy life
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:=j;
sum:=sum + x*t;
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*t;
mong bạn giải thích giải thuật này cho mình với ak..
end;
end;
Nhấn để mở rộng...

- Tại mỗi 1 tờ tiền thứ i thì chỉ có 2 khả năng: chọn (x = 1) và không chọn (x = 0). Dòng loop 'for' là duyệt 2 lựa chọn này. Cụ thể, x := 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 = 0, như vậy sum ko đổi phải không bạn? Khi đó x * t = 0.
Giả sử mình chọn tờ i, tức là x = 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 (vì khi đó x * t = t).

- 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*t 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.
 
V

vansonqtqb

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 ĐỠ..
 
Sửa lần cuối:
T

tengiday

Happy life
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     [COLOR=#ff0000]10[/COLOR]  10   5   5   5
x      [COLOR=#ff0000]0[/COLOR]   0   0   0   0
sum = 0
...
i = 5
Mã: 
t     [COLOR=#ff0000]10  10   5   5   5[/COLOR]
x      [COLOR=#ff0000]0   0   0   0   0[/COLOR]
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     [COLOR=#ff0000]10  10   5   5   5[/COLOR]
x      [COLOR=#ff0000]0   0   0   0   1[/COLOR]
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     [COLOR=#ff0000]10  10   5   5[/COLOR]   5
x      [COLOR=#ff0000]0   0   0   1[/COLOR]   0
sum = 5 - 5 + 5 = 5
i = 5
Mã: 
t     [COLOR=#ff0000]10  10   5   5   5[/COLOR]
x      [COLOR=#ff0000]0   0   0   1   0[/COLOR]
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     [COLOR=#ff0000]10  10   5   5   5[/COLOR]
x     [COLOR=#ff0000] 0   0   0   1   1[/COLOR]
sum = 5 - 0 + 5 = 10

Vì check fails nên phải lui tới tờ thứ 3.
i = 3
Mã: 
t     [COLOR=#ff0000]10  10   5[/COLOR]   5   5
x      [COLOR=#ff0000]0   0   1[/COLOR]   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     [COLOR=#ff0000] 0    0   1   0[/COLOR]   0
i = 5: x      [COLOR=#ff0000]0    0   1   0   0[/COLOR]

Quay lui
Mã: 
i = 5: x      [COLOR=#ff0000]0    0   1   0   1[/COLOR]

Quay lui
Mã: 
i = 4: x      [COLOR=#ff0000]0    0   1   1[/COLOR]   0
i = 5: x      [COLOR=#ff0000]0    0   1   1   0[/COLOR]

Quay lui
Mã: 
i = 5: x      [COLOR=#ff0000]0    0   1   1   1[/COLOR]
Đâ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 = 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.
 
Sửa lần cuối:
V

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 = 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..
 
T

tengiday

Happy life
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 = 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..
Nhấn để mở rộng...

Được chứ bạn. Ví dụ nằm ngay phía trên; cụ thể là ở bước này:
Mã: 
t     [COLOR=#ff0000]10  10   5   5   5[/COLOR]
x      [COLOR=#ff0000]0   0   0   0   1[/COLOR]
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     [COLOR=#ff0000]10  10   5   5[/COLOR]   5
x      [COLOR=#ff0000]0   0   0   1[/COLOR]   [U][B]1[/B][/U]
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.
 
V

vansonqtqb

mình còn bài bài tập này nữa nhờ bạn chỉ giáo giúp luôn
Cho dãy số gồm n (n < = 10000) số nguyên a1, a2, … , an (|ai| <= 10^9), tìm số nguyên X bất kì ñể S = |a1 — X| + |a2 — X| + … + |an — X| ñạt giá trị nhỏ nhất, có bao nhiêu giá trị nguyên khác nhau thoả mãn.
Ví dụ 1: dãy gồm 5 số 3, 1, 5, 4, 5, ta có duy nhất một giá trị X = 4 ñể S ñạt giá trị nhỏ nhất bằng 6.
Ví dụ 2: dãy gồm 6 số 3, 1, 7, 2, 5, 7 ta có ba giá trị nguyên của X là 3, 4, 5 ñể S ñạt giá trị nhỏ nhất bằng 13.
 
Sửa lần cuối:
T

tengiday

Happy life
Bài đó thuộc về toán rồi bạn ạ. Nếu có 1 dãy số đc sắp xếp thì con số X để minimize the sum of the absolute differences chính là median của dãy số đó. Điều đó có nghĩa rằng:
1) Bạn sort lại dãy số đó, dùng quick sort (độ phức tạp trung bình là O(n log n)).
2) Tìm con số median, tức là a[(1 + n) div 2 + 1] nếu n là số lẻ.
3) Nếu n là số chẵn thì quét trong khoảng a[n div 2] tới a[n div 2 + 1].

PS: Bạn cứ post bài, sẽ có nhiều cao nhân khác giúp đỡ. Mình sắp vào trường lại rồi, phải vừa đi dạy vừa học nên sợ là không có thời gian để trả lời được.
 
V

vansonqtqb

uk cảm ơn bạn nhiều. cũng nhờ bạn mà mình học nhiều điều ở bạn.. làm phiền bạn nhiều quá...bạn thông cảm..
 
T

tengiday

Happy life
vansonqtqb:
uk cảm ơn bạn nhiều. cũng nhờ bạn mà mình học nhiều điều ở bạn.. làm phiền bạn nhiều quá...bạn thông cảm..
Nhấn để mở rộng...
Ko có gì bạn. Nếu mình có thời gian thì cũng sẽ trả lời giúp thôi. Mấy vấn đề này lâu lắm rồi mình ko dùng đến nữa, với lại chuyên ngành chính của mình là toán (partial differential equation), ko liên quan gì tới mấy cái này bởi vậy mình trả lời theo cái tốt nhất mình biết. Đôi khi nó vẫn chưa tối ưu đâu nhé.
 
V

vansonqtqb

uk dù sao vẫn cảm ơn bạn nhiều.. nếu mình còn vấn đề nào thắc mắc mình có thể liên lạc với bạn dk ko ak
 
T

tengiday

Happy life
vansonqtqb:
uk dù sao vẫn cảm ơn bạn nhiều.. nếu mình còn vấn đề nào thắc mắc mình có thể liên lạc với bạn dk ko ak
Nhấn để mở rộng...
Bạn cứ post câu hỏi lên 4rum thì sẽ nhận được nhiều sự giúp đỡ từ mọi người nhé. Nếu mình có thời gian cũng sẽ trả lời giúp bạn.
 
V

vansonqtqb

mình nhờ bạn một chút nữa thui nhé.với bài bày.sắp xêp thi mình đã sắp xếp. mình nhờ bạn chỉ rõ đoạn code tim x đó dk ko ak...làm phiền bạn làn này nữa....
 
T

tengiday

Happy life
vansonqtqb:
mình nhờ bạn một chút nữa thui nhé.với bài bày.sắp xêp thi mình đã sắp xếp. mình nhờ bạn chỉ rõ đoạn code tim x đó dk ko ak...làm phiền bạn làn này nữa....
Nhấn để mở rộng...
Sau khi bạn sắp xếp xong,
- nếu n là lẻ thì phần tử đó là a[n div 2 + 1];
- nếu n là chẵn thì mình lấy từ a[n div 2] tới a[n div 2 + 1].
 
Đăng nhập bằng tài khoản VFO hoặc Google

Bài viết mới nhất

Thống kê

Chủ đề
100,844
Bài viết
467,738
Thành viên
339,893
Thành viên mới nhất
Gia dụng Việt Anㅤ
Top