1 bài toán nhờ mọi người giúp

[kurama02]

Em đang bí một bài toán
Bài toán như sau : Có bao nhiêu cách phân tích 1 số tụ nhiên ( liệt kê tất cả các cách ) thành tổng của một số số tự nhiên cho trước
Ví dụ : Số tự nhiên cần phân tích là 30
Các số cho trước là {8,9,10,11,12}
Thì nhận đựoc kết quả như sau
30 = 8 + 11 + 11
30 = 8 + 10 + 12
30 = 9 + 10 + 11
30 = 9 + 9 + 12
30 = 10+ 10 + 10
mong được các anh chị giúp đỡ

[ninhpk]

Em dùng đệ qui giải quyết như sau (code VB):
- giả sử a là chuỗi số cho trước, n là số cần phân tích. Gọi thủ tục Phantich(30,"30 = ")

sub Phantich(n as integer, s as string) as string
dim i as int
if n=0 then
'hiển thị chuỗi s là kết quả ra màn hình
exit sub
end if

for i =0 to a.Length
if n >= a(i) then
Phantich(n-a(i), s + "+" + a(i) )
end if
next
end sub

[Rikku]

Cho cái giới hạn đi ...

Cho cái giới hạn đi ...

[kurama02]

Giới hạn phần nào hả anh Rikku
Nếu giới hạn số cần phân tích thì cho nó <= 4000, và các số tự nhiên trong tập hợp cho trước thì giới hạn là <=400
@ninkpk Rất cảm ơn anh nhưng đọc đoạn code em không rõ lắm giải thuật của anh,theo em đoán thì đoạn code này chỉ xuất kết quả là 1 cách phân tích thui,vả lại đoạn code của anh không xét đến trường hợp n>0 và n <a[i] với i=1 to a.length,không biết em nói như vậy có đúng kô,anh giải thích thêm cho em đựoc kô

[noname.cpp]

Bài toán này nếu dùng giải thuật quay lui vét cạn thì có độ phức tạp hàm mũ nên nếu kích thước của tập lớn thì không chạy được.Theo tôi thì nếu muốn tìm tất cả các nghiệm thì chỉ có cách dùng thuật toán đệ quy như trên thôi.

[kurama02]

Giới hạn lại bài toán
Số cần phân tích <=4000
Tập cho trước chỉ bao gồm các số sau {9, 16 , 25, ... ,361, 400} ,tức là gồm các số chính phương từ 3^2 đến 20^2
Em cũng đoán là dùng đệ quy và đã cố làm thử nhưng do giải thuật hạn chế nên kô tìm được đầy đủ nghiệm

Giới hạn lại bài toán
Số cần phân tích <=4000
Tập cho trước chỉ bao gồm các số sau {9, 16 , 25, ... ,361, 400} ,tức là gồm các số chính phương từ 3^2 đến 20^2
Em cũng đoán là dùng đệ quy và đã cố làm thử nhưng do giải thuật hạn chế nên kô tìm được đầy đủ nghiệm

[ninhpk]

@kurama02 Không cần xét n>0 vì đã xét n>a[i] và a[i] dĩ nhiên lớn hơn 0. Trường hợp n<a[i] và n <>0 không cần làm gì cả vì nó không phải là nghiệm và không thể phân tích tiếp được.
Giải thuật trên cho tất cả các nghiệm có thể có vì nó duyệt qua tất cả các phần tử của mảng nhưng kết quả trùng lặp nhau khá nhiều. Một cải tiến giảm bớt trùng lặp như bằng cách cho vòng for không kiểm tra lại những số trong dãy đã được kiểm tra:

sub Phantich(n as integer, s as string, index as integer) as string
dim i as int
if n=0 then
'hiển thị chuỗi s là kết quả ra màn hình
exit sub
end if

for i =index to a.Length
if n >= a(i) then
Phantich(n-a(i), s + "+" + a(i), i)
end if
next
end sub

Khi chay goi Phantich(n, "",1). (Hình như trong VB index của mảng bắt đầu từ 1 thì phải, không nhớ kỹ :-)

Tuy vậy giải thuật vẫn chạy khá chậm khi mà n tăng lên. Một cách cải tiến hiệu quả là ghi nhớ lại những kết quả trung gian đã phân tích để dùng trong lần lặp khác.

@noname.cpp Mình không biết giải thuật quay lui vét cạn là gì. Hồi trước có học môn Phân tích thiết kế giải thuật nhưng đến bây giờ quên hết nên không biết cách tính độ phức tạp. Bạn có thể nói rõ hơn không?

[noname.cpp]

@noname.cpp Mình không biết giải thuật quay lui vét cạn là gì. Hồi trước có học môn Phân tích thiết kế giải thuật nhưng đến bây giờ quên hết nên không biết cách tính độ phức tạp. Bạn có thể nói rõ hơn không?

Chương trình trên của bạn chính là một ví dụ cho giải thuật quay lui vét cạn đấy.Nó đơn giản là một thuật toán sử dụng thủ tục đệ quy để xét tất cả các trường hợp có thể để tìm nghiệm của bài toán.

Còn về độ phức tạp của giải thuật này.Bài toán yêu cầu tìm tất cả các bộ số {ai1,ai2,...aik} trong tập {a1,a2,...,an} có tổng bằng s cho trước.Do không quy định các số phải khác nhau nên số lượng các bộ số phải xét là : n^1 + n^2 + ... n^t , độ lớn của t tùy thuộc vào s ,nói chung thuật toán có độ phức tạp hàm mũ.

Một bài toán tương tự nhưng dễ hơn của bài toán này là tìm tập con của một dãy có tổng cho trước(chỉ xét các nghiệm gồm các số khác nhau) đã thuộc vào lớp NP-Problem ,bài này cón có độ phức tạp lớn hơn.
Không tin ,cứ thử chạy với s lớn một chút, ngồi chờ dài cổ.

[liquid89]

uh` em nghĩ bài này dùng quay lui là thích hợp ,ai giỏi thì cho thêm cái nhánh cận tốt tốt vào