PDA

View Full Version : Dung stack bai nay nhu nao



nuilua3
22-04-2005, 22:20
Hi.hien toi dang co mot bai toan tuong doi kho ma chua nghi ra giai thuat toi uu,nho cac cao thu chi dum nhe.Ta co mot file chua cac so nguyen co the rat rat nhieu vi du
123=m.
23
50
30
20
10
10
5
5
7
100
...
Ta cần tìm tất cả các bộ số sao cho tổng của chúng bằng m ví dụ 23+50+20+30 hoặc 100+23...
yêu cầu của giáo viên là dùng stack.Các huynh nêu thử thuật toán hoạc có tài liệu liên quan nào thì chỉ dùm nhé.Thank

bete
24-04-2005, 18:41
Thân gửi nuilua3: bạn làm như vầy có được không:

Lần lượt thử n số; với mỗi số có 2 lựa chọn: thêm số đó vô tổng hoặc bỏ qua (không thêm vô tổng) => xài stack để quay lui thử lựa chọn thứ hai => cần m bước (và sẽ là O(2^m))

(có gì sai sót xin các chỉ giúp, cám ơn nhiều)

-thân

echcoms
25-04-2005, 10:49
tìm tất cả các tập con của n phần tử,sau đó liệt kê các tập có tổng bằng m.dùng stack lưu các tập hợp có số thứ nhất,thứ hai... cho đến số thứ n,cứ vậy là vét được hết các tập con.cái này có vẻ giống với bete

nuilua3
25-04-2005, 20:18
ý t­­­­ưởng của tui thế naỵLúc đầu ta sẽ sắp xếp các số đó lại theo chiều tăng dần,và lưu vào một mảng a[i]
B1ta push lần luợt các số từ số có giá trị từ nhỏ nhất sau đó tăng dần lên vào stack.Cho tới khi nào tổng của chúng lớn hơn m thì dừng.Giả sử khi đó stack có n phần tử.Vì đây là n phần tử nhỏ nhất =>tập hợp các số có tổng là m chỉ có tối đa là n-1 phần tử.
B2 ta thử lần luợt các tập hợp có 1...n-1 phần tử. Để tạo ra mỗi tập hợp ta sẽ dùng một stack.Giả sử đang xét tập hợp có N phần tử.Đầu tiên push a[1],a[2] ...a[N] vào stack.từ dãy này ta lần lượt bỏ đi một s.Mỗi lần như thế ta lại thêm vào một số lớn hơn a[N] nếu tổng các phần tử của stack nhỏ hơn m pop(lấy a[i]sau cùng ra) và push a[i+1]vào.Nếu vẫn nhỏ hơn ta lại pop a[i+1],và push a[i+2]...cứ làm như thế cho tới khi tổng stack lớn hơn m thì dừng(vì các phần tử tiếp theo làm tổng của stack lớn hơn nữa).
Hiển nhiên khi tìm được tập hợp có tổng là m thì cout chúng ra.
Bây giờ tui muốn hỏi là cách làm này so với cách của echcoms độ phức tạp của nó có lớn hơn hay nhỏ hơn.Các huynh cho ý kiến luôn về thuật giải của nó

mapleleaf
26-04-2005, 06:48
Tôi có làm 1 bài gần giống, yêu cầu tìm tổng số các bộ số, không yêu cầu phải liệt kê ra những số nào.


//backtrack
public int backtrack(){
int count = 0;

//sort array, increasing order
mergesort(arr, 0, arr.length-1);

//return number of M-subsets
for(int i=0; i<arr.length; i++) count += construct(i, 0);
return count;
}


private int construct(int ind, int sum){
int count = 0;
int num = arr[ind];

//should be the last element in the subset
if(m == (sum + num)) return 1;

//if next element is smaller than num
if(m - (sum + num) <= num) return 0;

//else
for(int i=ind+1; i<arr.length; i++) count += construct(i, sum + num);

return count;
}

Tôi nghĩ, chưa thử, nếu sử dụng stack thì có thể thay đổi 1 chút để ghi nhớ các số trong 1 bộ số. Các huynh tham khảo rồi cho ý kiến nhé.

nuilua3
26-04-2005, 10:19
you nói cụ thể đề bài và giải thích đoạn code trên đi.Có gì chúng ta cùng trao đổi nhé

mapleleaf
26-04-2005, 15:25
Đây là requirement của bài đó. Chịu khó đọc tiếng Anh nhé, tôi lười dịch ra tiếng Việt quá.

[I]Submit a SubSets.java implementing a SubSets class that creats
an object that does the following: the object takes an array A of
positive integers and a positive integer M, it returns an integer
giving the number of M-subsets of the given array (treated as a set).
An M-subset is a subset of integers of A whose members sum to M. This
should be done with backtracking.

---------------------------------

Trong method backtrack():

Đầu tiên là sort array theo thứ tự tăng dần.
Gọi method construct(ind, sum)

Trong method construct(int ind, sum)
ind là index của number kế tiếp.
sum là tổng của các số được xét trước đó.

Nếu (m == sum + num) nghĩa là đã tìm được 1 M-Subset, return 1.
Nêu (m - (sum + num) < num) nghĩa là số kế tiếp phải nhỏ hơn num. Array theo increasing order do đó M-subset không tồn tại, return 0
Else, gọi đệ qui, xét các số kế tiếp.

---------------------------------
TẠm vậy đã nhé. Giờ phải học bài tiếp.

echcoms
27-04-2005, 10:05
to nuilua3: mình chưa xem kĩ cách của bạn nhưng nếu làm cách của bạn thì mình thấy nên đọc các số nhỏ hơn N,sau push vào stack như thế sẽ tiết kiệm bộ nhớ hơn.cách làm của tôi tôi cũng chưa thử,nhưng có lẽ nó làm theo kiểu vét cạnvaf khá trâu bò.

nuilua3
28-04-2005, 20:30
Tui cũng chưa cài đặt thuật giải.Hiện đang mắc một vấn đề là cài cái stack này bằng mảng hay DSLK bởi nếu dùng DSLK sẽ tốn bộ nhớ hơn do phải chứa con trỏ.Bây giờ tôi về cài đặt chương trình đây.Ai biết cách tính thời gian chạy của một chương trình không?chỉ cho tôi với

echcoms
29-04-2005, 18:12
không phải là tính thời gian chạy chương trình đâu bạn mà là tính độ khó giải thuật thôi.có thể nói rằng đấy là tính toán số lần máy tính thực hiện các thao tác,cái này tính toán dựa trên dữ liệu vào và thuật giải,mình nhớ là trên web của đại học cần thơ có viết về vấn đề này rồi đấy.ko nhớ link bạn thử tìm xem.
theo mình thì cài đặt bằng mảng hay bằng con trỏ thì cũng không hơn gì nhau trong việc tiết kiệm bộ nhớ.cả hai đều ok.
bài này là bài toán knapsack,bạn len google tìm xem mình thấy có khá nhiều.