Tìm các con số có tổng bằng 1 con số cho trước

[Quang_Hải]

Các anh chị vui lòng hướng dẫn cách viết code để tìm ra những con số có tổng bằng 1 con số cho trước. Mình đã mày mò cả buổi mà chưa tìm ra cách giải.
Vui lòng xem file đính kèm có kết quả tạm làm thủ công.

 

[huuthang_bd]

Code ở bài 13 dùng thuật toán đệ qui. Tổng cộng dồn được kế thừa để kiểm tra tiếp nên tốc độ sẽ nhanh hơn là đương nhiên. Ví dụ tập hợp có 10 số, code đang xét bộ 4 số. Tổng cộng dồn là tổng của 3 số thứ 1, 2, 3. Sau đó cho vòng lặp duyệt từ 4 đến 10, lấy tổng cộng dồn 3 số kia cộng với từng số để so sánh với tổng đã cho ban đầu mà không phải cộng lần lượt các bộ 4 số như s1 + s2 + s3 + s4; s1 + s2 + s3 + s5; s1 + s2 + s3 + s6;... Ngoài ra, code này sử lý số trực tiếp không qua các bước trung gian nên tốc độ cũng sẽ được cải thiện hơn.

Tuy nhiên, code có một số chỗ thừa không cần thiết có thể lượt bỏ và còn có thể chỉnh sửa để cải thiện tốc độ:
- Giảm bớt 1/2 số vòng lặp
- Đưa vào mảng và nhập vào bảng tính 1 lần.

Tôi sửa lại code bài 13 một chút để cải thiện tốc độ và hy vọng người đọc sẽ thấy dễ hiểu hơn.

Dim n As Long, Tong As Double, MgNguon(), MgKQ(), c As Long

Sub KiemTra()
Dim k As Long, KQi() As Double
Tong = [A1].Value
MgNguon = Range([B1], [B65536].End(3)).Value
[D1].CurrentRegion.ClearContents
n = UBound(MgNguon, 1)
ReDim MgKQ(1 To n, 1 To 1)
   For k = 1 To n
      ReDim KQi(1 To k, 1 To 1) As Double
      Main k, KQi, 0, 1, 1
   Next
[D1].Resize(n, c).Value = MgKQ
c = 0:  Erase MgNguon:  Erase MgKQ
End Sub

Sub Main(k As Long, KQi, CongDon As Double, PhanTu As Long, SoDem As Long)
Dim i As Long, j As Long
If SoDem <= k Then
   For j = PhanTu To n - k + SoDem '' Sửa chỗ này sẽ giảm được 1/2 số lần gọi Sub này
      KQi(SoDem, 1) = MgNguon(j, 1)
      Main k, KQi, CongDon + KQi(SoDem, 1), j + 1, SoDem + 1
   Next j
Else
   If CongDon = Tong Then
      c = c + 1
      ReDim Preserve MgKQ(1 To n, 1 To c)
      For i = 1 To k
         MgKQ(i, c) = KQi(i, 1)
      Next
   End If
End If
End Sub

 

[Quang_Hải]

Code ở bài 13 dùng thuật toán đệ qui. Tổng cộng dồn được kế thừa để kiểm tra tiếp nên tốc độ sẽ nhanh hơn là đương nhiên. Ví dụ tập hợp có 10 số, code đang xét bộ 4 số. Tổng cộng dồn là tổng của 3 số thứ 1, 2, 3. Sau đó cho vòng lặp duyệt từ 4 đến 10, lấy tổng cộng dồn 3 số kia cộng với từng số để so sánh với tổng đã cho ban đầu mà không phải cộng lần lượt các bộ 4 số như s1 + s2 + s3 + s4; s1 + s2 + s3 + s5; s1 + s2 + s3 + s6;... Ngoài ra, code này sử lý số trực tiếp không qua các bước trung gian nên tốc độ cũng sẽ được cải thiện hơn.

Tuy nhiên, code có một số chỗ thừa không cần thiết có thể lượt bỏ và còn có thể chỉnh sửa để cải thiện tốc độ:
- Giảm bớt 1/2 số vòng lặp
- Đưa vào mảng và nhập vào bảng tính 1 lần.

Tôi sửa lại code bài 13 một chút để cải thiện tốc độ và hy vọng người đọc sẽ thấy dễ hiểu hơn.

Code của bạn huuthang sau khi sửa lại đã chạy nhanh hơn code gốc gấp 10 lần. Hay thật!

 

[Hong.Van]

Code ở bài 13 dùng thuật toán đệ qui. Tổng cộng dồn được kế thừa để kiểm tra tiếp nên tốc độ sẽ nhanh hơn là đương nhiên. Ví dụ tập hợp có 10 số, code đang xét bộ 4 số. Tổng cộng dồn là tổng của 3 số thứ 1, 2, 3. Sau đó cho vòng lặp duyệt từ 4 đến 10, lấy tổng cộng dồn 3 số kia cộng với từng số để so sánh với tổng đã cho ban đầu mà không phải cộng lần lượt các bộ 4 số như s1 + s2 + s3 + s4; s1 + s2 + s3 + s5; s1 + s2 + s3 + s6;... Ngoài ra, code này sử lý số trực tiếp không qua các bước trung gian nên tốc độ cũng sẽ được cải thiện hơn.

Tuy nhiên, code có một số chỗ thừa không cần thiết có thể lượt bỏ và còn có thể chỉnh sửa để cải thiện tốc độ:
- Giảm bớt 1/2 số vòng lặp
- Đưa vào mảng và nhập vào bảng tính 1 lần.

Tôi sửa lại code bài 13 một chút để cải thiện tốc độ và hy vọng người đọc sẽ thấy dễ hiểu hơn.

Dim n As Long, Tong As Double, MgNguon(), MgKQ(), c As Long

Sub KiemTra()
Dim k As Long, KQi() As Double
Tong = [A1].Value
MgNguon = Range([B1], [B65536].End(3)).Value
[D1].CurrentRegion.ClearContents
n = UBound(MgNguon, 1)
ReDim MgKQ(1 To n, 1 To 1)
   For k = 1 To n
      ReDim KQi(1 To k, 1 To 1) As Double
      Main k, KQi, 0, 1, 1
   Next
[D1].Resize(n, c).Value = MgKQ
c = 0:  Erase MgNguon:  Erase MgKQ
End Sub

Sub Main(k As Long, KQi, CongDon As Double, PhanTu As Long, SoDem As Long)
Dim i As Long, j As Long
If SoDem <= k Then
   For j = PhanTu To n - k + SoDem '' Sửa chỗ này sẽ giảm được 1/2 số lần gọi Sub này
      KQi(SoDem, 1) = MgNguon(j, 1)
      Main k, KQi, CongDon + KQi(SoDem, 1), j + 1, SoDem + 1
   Next j
Else
   If CongDon = Tong Then
      c = c + 1
      ReDim Preserve MgKQ(1 To n, 1 To c)
      For i = 1 To k
         MgKQ(i, c) = KQi(i, 1)
      Next
   End If
End If
End Sub

Anh huuthang_bd và các Thầy Cô, anh chị cho em hỏi
Code trên khi không có kết quả thỏa với điều kiện thì code báo lỗi, vậy làm sao không có kết quả nào thì hiện thông báo "không có kết quả nào!"
Em cảm ơn!

 

[domitory]

Thuật toán của tôi đơn giản thôi.
Giả sử ta có N số khác nhau: a1, a2, ..., aN. Có thể lập được 2^N - 1 chuỗi khác nhau có N ký tự "0" hoặc "1" - ít nhất 1 ký tự = "1". Đó chẳng qua là (2^N - 1) số từ 1 tới (2^N - 1) được viết ở dạng bít. Vd. N = 2 (a1, a2) thì ta có 3 chuỗi ứng với 3 số từ 1 tới 2^2 - 1 = 3 là "01", "10" và "11"
Với mỗi chuỗi kể trên ta tính tổng các số ở dãy cho trước mà ứng với chúng ký tự trong chuỗi là 1. Nếu con số này = số cho trước thì ta lấy các con số ứng với chuỗi.
VD. ta có dãy 9 số cho trước (N = 9): 1, 2, 3, 4, 5, 6, 7, 8, 9
=> với chuỗi "001000110" ta tính số = 3 + 7 + 8 = 18
--------------
Xin nhờ test hộ cả tốc độ của code.

Em xin phép ké chủ đề. Em cũng đang có vấn đề gần giống với bác chủ thớt.
Em có dãy các con số: 0,1,2,3. Em muốn liệt kê các dãy số có n(4<n<10) số sao cho tổng các số trong dãy số bằng 1 số m(1<m<4) cho trước.