một bài toán nữa

[lang tu IT]

Ta co mot file chua cac so nguyen co n số. 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...
nếu ai cao thủ thì dùng stack thử xem

[lang tu IT]

a` quên, với bài trên để đơn giản đi thì mình giớ hạn lại n <=200 nhé

[graphiks]

Dùng stack là dùng theo kiểu nào ??
Có phải là Đặt vô stack sau và sau khi tỗng bằng 132 --> lôi nó ra hả
Theo teo cái này thì phải xét từng phần tử 1 và ghép với phần tử còn lại,nhung mà những phần tử xét rồi thì không xét lại để tránh trùng lặp

[lang tu IT]

mẹ ơi, nói như mày thì mọi chuyện dễ quá, phải tính đến dộ phức tạp của thuật toán chư.
Dùng stack cũng có 2 kiểu :
+ theo đệ quy(cái này đơn giản) - độ phức tạp là k dám tính.
+ khử đệ quy(cái này mới phải tính) - nếu khéo thì chương trình có thể chạy được với các test khó.
còn 1 cách nữa, nhưng để bàn sau : cách này dảm bảo n < 200 la chạy được

[graphiks]

Này !dùng stack có nghĩa là đã khử đệ quy rồi !!
Còn nếu mà đệ quy thì có nghĩa là mình không xài stack ,cái stack cái này dành máy làm ,nó có stack riêng

Nếu mà ko xét theo từng phần tử thì làm sao ,nếu ko xét từng phần tử có thể bỏ lỡ 1 tập nào đó
Xét 1 phần tử và kết hợp với tất cả còn lại để có đủ tất cả tập hợp ,nếu ko có thề là ko còn cách nào tao nghĩ thế

[lang tu IT]

ông tính cho tôi đọ phức tạp, và nêu cách viết sơ lược đi

[graphiks]

Teo ko biết tính độ phức tạp ,tại teo nghỉ học ĐH từ năm thứ 2 roài :dry: ,teo pót cái algorithm lên đây mày tính hộ teo nhé
Có cách nào khác nhanh hơn nữa ko
StackList đơn giản là cái Stack thế thôi ,không có gì phải giải thích cả Ok??? Mầy chỉ cần biết là nó Push Pop là OK

Nè cái df là cái tổng cần tìm nhé
Mày tét thử đi ,tao mới tét có 8 thằng àh
Nếu có cách khác ngắn hơn thì pot lên
Nó show 1 dòng 1 bộ số ,làm ơn mỗi bộ số mày đếm ngượic thứ tự nó post thì mới dễ theo dõi xem nó có làm triệt để ko
#include <stalist.cpp>
int t=0;
int df;
int c;
StackList<int> temp;
void Recur(int *a,int n,int i,StackList<int> &k)
{
for(;i<n;i++)
if(t+a[i]==df)
{
cout<<a[i]<<" ";
while(!k.IsEmpty())
{
if(!k.IsEmpty())
c=k.Pop();
temp.Push(c);
cout<<a[c]<<" ";
}
cout<<"\n";
while(!temp.IsEmpty())
k.Push(temp.Pop());
}
else
if(t+a[i]<df)
{
t+=a[i];
k.Push(i);
Recur(a,n,i+1,k);
t-=a[i];
}
if(!k.IsEmpty())
k.Pop();
}

void main()
{
StackList<int> k;
clrscr();
int *a=new int[8];
a[0]=4;
a[1]=5;
a[2]=1;
a[3]=2;
a[4]=3;
a[5]=7;
a[6]=10;
a[7]=5;

df=10;
Recur(a,8,0,k);
getch();
}

[graphiks]

Ý teo có ý kiến nè ,trước khi tìm bộ số hãy sắp xếp từ nhỏ đến lớn
Theo cách này khi duyệt đến phần tử nào mà nó cộng với mấy cái số đã tìm được trước đó lớn hơn tổng thì ngắt luôn và bắt đầu duyệt sang phần tử mới , bởi vì các phần tử tiếp theo sau cộng lại chắc chắn là lớn hơn nên ko cần xét ,đó cũng có thể là 1 cách Optimize nhưng mà chac là phải tốn tiền cho giải thuật sắp xếp nhỉ ,Nhưng mà dù sao cũng đỡ rất là nhiều tại vì nếu duyệt 1000 thằng , thì nếu làm theo cách của tao nó chạy tới cúp điện luôn wa1

[lang tu IT]

#include <stalist.cpp>
}

stalsih là 1 chương trình của mày a`, tao k co thì test làm sao hả. potay.com
Mà chương trình này chỉ chạy 100 thôi có lẽ cũng đến tết công rồi. Nhưng đây cũng là cách mà mình muốn các bạn khác nên viết thử vì nó sẽ rèn luyện kỹ năng duyệt của các bạn. còn 1 cách khác cho bài toán này là quy hoạch động.(cũng gần với cách graphics nói thôi, có chỉnh sửa 1 vài chỗ).

[graphiks]

Quên mất :D