Thuật toán "Đệ Quy"

[Nguyễn Duy Tuân]

Thuật toán đệ quy đã có nhiều sách vở nói đến, có thể dễ dàng google là ra rất nhiều. Trên GPE cũng có thể nhiều bạn chưa biết hay đã biết. Tôi xin đưa ra để mọi người hiểu và cùng thảo luận thêm.

Có nhiều khái niệm về Đệ quy. Tôi xin nói theo cách hiểu của mình như thế này. Đệ quy là việc chạy lại một hàm hay thủ tục trong chính nó.

Ví dụ: Tinh giai thừa của một số bất kỳ
Cách dùng vòng lặp

Function GiaiThua2(ByVal SoNguyen As Long) As Long
    Dim I As Long
    GiaiThua2 = 1
    For I = SoNguyen To 1 Step -1
        GiaiThua2 = GiaiThua2 * I
    Next I
End Function

GiaiThua2 = GiaiThua2 * I. GiaiThua2 trong dòng lệnh này đóng vai trò như một biến .

Dùng Đệ quy

Function [B]GiaiThua[/B](ByVal SoNguyen As Long) As Long
[COLOR="SeaGreen"]    'GiaiThua(5) = 5*4*3*2*1
    'SoNguyen! = SoNguyen * (SoNguyen-1) * (SoNguyen-2)*...*1[/COLOR]
    If SoNguyen = 1 Or SoNguyen = 0 Then
        GiaiThua = 1
    Else
        GiaiThua = SoNguyen * [B]GiaiThua[/B](SoNguyen - 1)
    End If
    
End Function

GiaiThua = SoNguyen * GiaiThua(SoNguyen - 1). GiaiThua(SoNguyen - 1) được gọi lại với một tham số mới. Đây chính là thuật Đệ quy!
Ví dụ 2: Nhập số. Yếu cầu nhập số, nếu nhập sai thì nhập lại.
Dùng vòng lặp

Sub NhanSo2()
    Dim vSo As Variant
    vSo = "ABC"
    Do While True
        If Not IsNumeric(vSo) Then
            vSo = InputBox("Hay nhap mot so. Neu nhap sai chuong trinh yeu cau nhap lai!", "Nhan So")
        Else
            MsgBox "Ban da nhap dung!"
            Exit Do
        End If
    Loop
    
End Sub

Dùng Đệ quy

Sub [B]NhanSo[/B]()
    Dim vSo As Variant
    vSo = InputBox("Hay nhap mot so. Neu nhap sai chuong trinh yeu cau nhap lai!", "Nhan So")
    If Not IsNumeric(vSo) Then
        [B]NhanSo[/B]
    Else
        MsgBox "Ban da nhap dung!"
    End If
End Sub

Mình đang viết dở thì bận rồi, xin viết tiếp bài sau.

 

[Po_Pikachu]

Cái này em thấy nó cũng quen quen, nhưng mình thường làm nó ở 1 vài lần thôi! Ví dụ như nhập password sai thì nhập lại và nếu quá 3 lần thì không cho nhập nữa. Đại khái là như vậy! Nay mới biết nó là "Đệ quy" và còn được mở rộng ra nữa chứ! Cảm ơn bác nhiều nha! Thân.

 

[ndu96081631]

Xem như "lảnh hội" được phần nào về đệ quy
Tôi phát hiện cốt lổi vấn đề ở đây là phải "mồi" cho nó 1 giá trị ban đầu, chẳng hạn với code:

Function GiaiThua(ByVal SoNguyen As Long) As Long
    If SoNguyen = 1 Or SoNguyen = 0 Then
        GiaiThua = 1
    Else
        GiaiThua = SoNguyen * GiaiThua(SoNguyen - 1)
    End If
End Function

thì giá trị được "mồi" ở đây là đoạn:

If SoNguyen = 1 Or SoNguyen = 0 Then
GiaiThua = 1

Có thể mình nghĩ đơn giãn rằng: Dử liệu của ta không có giá trị nào < 2 nên bỏ luôn đoạn đặt điều kiện ấy... Ẹc.. Ẹc... Bỏ thử cái, dù nhập giá trị nào cũng sẽ báo lổi! Vì với công thức:

GiaiThua = SoNguyen * GiaiThua(SoNguyen - 1)

thì GiaiThua(SoNguyen - 1) sẽ "lùi" dần đến khi "đụng" số 0 mới thôi (gần giống vòng lập)
Tạm hiểu thế, không biết có đúng không?
Xin các cao thủ chỉ thêm!

 

[rollover79]

Function [B]GiaiThua[/B](ByVal SoNguyen As Long) As Long
[COLOR=SeaGreen]    'GiaiThua(5) = 5*4*3*2*1
    'SoNguyen! = SoNguyen * (SoNguyen-1) * (SoNguyen-2)*...*1[/COLOR]
    [COLOR=Red]If SoNguyen = 1 Or SoNguyen = 0 Then[/COLOR]
        GiaiThua = 1
    Else
        GiaiThua = SoNguyen * [B]GiaiThua[/B](SoNguyen - 1)
    End If
    
End Function

Dòng đánh dấu trên chỉ cần thay bằng

  IF SoNguyen = 0 Then

To Po_Picachu: Ví dụ nhập Password chỉ là ví dụ thôi, thực tế người ta thường không dùng đệ quy cho trường hợp này mà thường dùng vòng lặp.

 

[ptm0412]

cốt lổi vấn đề ở đây là phải "mồi" cho nó 1 giá trị ban đầu

Khi tính toán nhiều lần mới cần "mồi", còn không thì chả cần. Thí dụ 1 câu lệnh bất kỳ:

Sub AddR()
Cells(1, 1).EntireRow.Insert
Cells(1, 1) = "I love you"
AddR
End Sub

Thí dụ thôi, đừng chạy thử nếu không biết stop nó.

Một thí dụ khác: file yeu.bat

@echo on
echo I love you so much!
yeu

 

[rollover79]

Đệ quy là việc chạy lại một hàm hay thủ tục trong chính nó.

Tôi thì không đồng ý với định nghĩa về Đệ quy như vậy. Và trong 2 ví dụ của bác Tuân thì chỉ có ví dụ về tính giai thừa được gọi là đệ quy, còn ví dụ về nhanso thì đấy không phải là đệ quy. Đệ quy là khái niệm không phải của riêng Tin học, mà rất nhiều lĩnh vực khác cũng có. Tôi xin được trích 1 khái niệm về đệ quy như sau

Các tính chất (hoặc cấu trúc) được gọi là đệ quy nếu trong đó một lớp các đối tượng hoặc phương pháp được xác định bằng việc xác định một số rất ít các trường hợp hoặc phương pháp đơn giản (thông thường chỉ một) và sau đó xác định quy tắc đưa các trường hợp phức tạp về các trường hợp đơn giản.

Định nghĩa trên có vẻ hơi phức tạp, nhưng có thể tóm tắt là: Việc định nghĩa 1 đối tượng phức tạp nào đó thông qua 1 định nghĩa của chính đối tượng đó ở dạng cơ bản.
Ví dụ:
Định nghĩa về số tự nhiên
- Số 0 là số tự nhiên (Định nghĩa cơ bản)
- Số N là số tự nhiên nếu N-1 là số tự nhiên (Định nghĩa Đệ quy)
Định nghĩa về giai thừa
- Giai thừa của 0 bằng 1 (Định nghĩa cơ bản)
- Giai thừa của N bằng N nhân với Giai thừa của N-1(Định nghĩa Đệ quy)

 

[ptm0412]

Định nghĩa của Rollover chắc là đúng, nhưng cao siêu quá (nếu trích nguyên văn), và rộng quá (dù đã tóm tắt)
Còn chủ đề của TuanVNUNI hẹp hơn, chỉ gói lại trong 4 chữ (đậm): Thuật toán (áp dụng) Đệ quy, không phải nguyên cái khái niệm đệ quy.
Vậy định nghĩa hẹp của TuanVNUNI có lẽ tạm đủ. Nhưng tôi thích cách giải thích này hơn:
Áp dụng thuật toán đệ quy, là dùng lệnh gọi lại chính mình thi hành lần nữa.

 

[Lệnh Hồ Đại Hiệp]

Ví dụ:
Định nghĩa về số tự nhiên
- Số 0 là số tự nhiên (Định nghĩa cơ bản)
- Số N là số tự nhiên nếu N-1 là số tự nhiên (Định nghĩa Đệ quy)
Định nghĩa về giai thừa
- Giai thừa của 0 bằng 1 (Định nghĩa cơ bản)
- Giai thừa của N bằng N nhân với Giai thừa của N-1(Định nghĩa Đệ quy)

Sao thấy giống quy nạp quá vậy bác. Hay Toán thì gọi là Quy nạp, còn Tin thì gọi là Đệ quy ???

Kính!

 

[ptm0412]

Sao thấy giống quy nạp quá vậy bác. Hay Toán thì gọi là Quy nạp, còn Tin thì gọi là Đệ quy ???

Quy nạp, nói rộng là 1 phương pháp suy luận, khác với diễn dịch (hình như trong triết học), trong viết văn là 1 cách nhập đề, nói trong toán thì là 1 phương pháp chứng minh.
Đệ quy: theo định nghĩa tóm tắt của Rollover (đoạn mà bạn trích), thì là 1 phương pháp định nghĩa. Nếu dùng trong "tin" như bạn nói, thì là 1 loại thuật toán.

Kết luận: không giống.

 

[rollover79]

Theo tôi thì Đệ quy và Quy nạp hay Diễn dịch là hoàn toàn khác nhau. Quy nạp là từ những kết luận riêng rẽ để chứng minh nó đúng với mọi trường hợp chung, diễn dịch thì ngược lại, dùng kết luận chung để đi chứng minh cho 1 trường hợp riêng cụ thể. Còn Đệ quy là đi định nghĩa 1 vấn đề chung dựa vào 1 định nghĩa cụ thể về 1 vấn đề.
Dĩ nhiên là tùy mỗi người hiểu thế nào thì hiểu, tuy nhiên đây không phải là khái niệm mới và nó không chỉ được bàn ở 4R này, do đó chúng ta nên hiểu về nó tường tận hơn, để mỗi khi sử dụng hay có thể là lại gặp những buổi tranh luận ở đâu đó sẽ có cách nhìn nhận chính xác hơn. Nếu định nghĩa Đệ quy là trong 1 hàm gọi lại chính nó thì sẽ chẳng còn gì phải bàn. Nói thực là khi mới được chỉ bảo về Đệ quy thì phải mất 1 năm sau tôi mới hiểu thế nào là Đệ quy, thông qua các bài toán mà mình gặp phải. Nên tôi không cho rằng Đệ quy nó đơn giản đến vậy, và không phải bài toán nào cũng có thể dùng Đệ quy để giải. Khi hiểu rõ về nó ta sẽ thấy là đọc 1 bài toán nên ta có thể biết nó có thể giải bằng Đệ quy hay không. Và nếu tìm hiểu 1 chút về Đệ quy các bạn sẽ thấy, trong thực tế người ta sẽ cố gắng để dùng vòng lặp thay cho Đệ quy(Khử đệ quy), vì số lượng các phép toán và bộ nhớ sử dụng trong các bài toán giải bằng Đệ quy là cực kỳ lớn. Các bạn có thể test lại bài toán tính giai thừa với số giai thừa cực lớn sẽ thấy sự khác nhau rõ rệt. Lý giải cho việc tốn bộ nhớ và tốc độ xử lý của Đệ quy, trước tiên chúng ta phải xem Đệ quy làm việc như thế nào. Tôi lấy ví dụ về bài tính Giai thừa
- Giả sử ta tính giai thừa của N, khi đó nó sẽ lấy N nhân với giai thừa của N-1(lúc này chưa biết kết quả), cứ liên tiếp nhân cho giai thừa của N-2(cũng chưa biết kết quả) cho tới khi nhân với giai thừa của 0(N-N), lúc này nó mới có kết quả là 1. Như vậy là những bước liền trước đó nó phải lưu trạng thái vào bộ nhớ, đến khi nó tính được giai thừa của 0 rồi mới lần lượt quay lại nhân với các trạng thái trước đó(cái này liên quan đến thuật toán quay lui), (tôi giải thích chỗ này có vẻ hơi khó hiểu, mong các bạn thông cảm vì tôi không biết giải thích thế nào dễ hiểu hơn)
- Về bài toán cụ thể thì hôm trước tôi có post 1 bài về chuyển 1 số nguyên sang số thứ tự bằng chữ cái.http://www.giaiphapexcel.com/forum/showthread.php?t=14990
- Ngoài ra bài toán chuyển 1 số hệ thập phân sang hệ nhị phân cũng có thể dùng Đệ quy được. Trong Excel cũng có hàm Dec2Bin để làm rồi, tuy nhiên tôi xin xây dựng lại thử thế này
* Trước hết nói về định nghĩa:
- Số D thập phân nhỏ hơn 2 thì số Nhị phân N=D(0 và 1)
- Số D thập phân không nhỏ hơn 2 thì số Nhị phân N sẽ là số nhị phân của phần dư D chia cho 2 nối với phần dư của D chia cho 2
Từ định nghĩa trên có thể viết như sau

Function D2B(n As Long) As String
    If n < 2 Then
        D2B = n
    Else
        D2B = D2B(n \ 2) & (n Mod 2)
    End If
End Function

Còn đây là vòng lặp

Function D2B(ByVal n As Long) As String
    Dim strRet As String
    Do
        strRet = (n Mod 2) & strRet
        n = n \ 2
    Loop Until n < 2
    If n > 0 Then strRet = n & strRet
    D2B = strRet
End Function

 

[Nguyễn Duy Tuân]

Có thể nói, một bài toán đệ quy bao giờ cũng phải có:
+ Thực hiện lại một khối việc tương tự (bằng cách gọi lại chính nó là hàm hay thủ tục).
+ Phải có điểm kết thúc. Nếu không có điều này thì bài toán dẫn tới vòng lặp luân hồi.

Bây giờ chúng ta tiếp tục làm một số ví dụ nhé!

1) Viết một hàm tính thưởng theo doanh số.
Doanh số Thưởng
10,000,000 0.5
20,000,000 1
30,000,000 1.5
50,000,000 2.5
70,000,000 4
100,000,000 2.5
150,000,000 9
200,000,000 13
300,000,000 20
400,000,000 27
500,000,000 40

Viết một hàm để tính thưởng theo doanh số bất kỳ?
Ví dụ:
Thuong(540,000,000) = 42 =(40 + 1.5 + 0.5)
2) Viết một thủ tục gọi tất cả các thư mục, thư mục con trong một đường dẫn bất kỳ.
Ví dụ

NhanTenThuMuc("C:")

Thủ tục sẽ liệt kê tất cả các thư mục trong ổ C: và các thư mục con trong C: và tiếp tục đến ngọn của nó.

 

[Nguyễn Duy Tuân]

1) Thưởng theo doanh số

Để làm yêu cầu 1) Thưởng theo doanh số, cần thực hiện trình tự sau
Đặt tên:
DOANHSO = C2:C12 (chỉ là cột doanh số)
10,000,000
20,000,000
30,000,000
50,000,000
70,000,000
100,000,000
150,000,000
200,000,000
300,000,000
400,000,000
500,000,000

THUONG = C212 (gồm có cột doanh số và cột thưởng)

Doanh số Thưởng
10,000,000 0.5
20,000,000 1
30,000,000 1.5
50,000,000 2.5
70,000,000 4
100,000,000 2.5
150,000,000 9
200,000,000 13
300,000,000 20
400,000,000 27
500,000,000 40



Phân tích bài toán:
+ Với một khoản doanh số bất kỳ (DS), ví dụ DS = 540,000,000
+ Tìm DS trong bảng DOANHSO. Mục đích để tìm mức doanh số bằng hoặc gần bằng.

DS1 = LOOKUP(DS, DOANHSO) =500,000,000

Như vậy DS1 <= DS.

+ Dùng VLOOKUP để tìm DS1 trong bảng THUONG, nếu tìm được cho ra giá trị ở cột thưởng (cột thứ 2).

ThuongDS = VLOOKUP(DS1,oVung, 2, 0)

+ Cộng lũy kế các khoản thưởng
NhanThuong = NhanThuong + ThuongDS

+ Tính tiếp giá trị của phần còn lại

DS2 = DS - DS1 = 540,000,000 - 500,000,000 = 40,000,000

DS2 lại là một mức doanh số cần được tìm và tính thưởng giống như đã làm trình tự với DS. Nếu toàn bộ mã lệnh trên ta đặt một hàm là NhanThuong(DS) thì ở bước này ta gọi lại nó để thực hiện lại quy trình cho danh số mới.

    If DS2 > 0 Then 'Neu co tiep tuc tinh
        NhanThuong = NhanThuong + NhanThuong(DS2)
    End If

Như vậy bài toán này ta vận dụng kỹ thuật Đệ quy!

Toàn bộ mã nguồn của hàm NhanThuong(DS) như sau:

Function [B]NhanThuong[/B](DS As Variant)
    Dim ofn As WorksheetFunction
    Dim oVungThuong As Range, oVungDS As Range
    Dim DS1, DS2, ThuongDS
    
    Set oVungDS = Application.Range("DOANHSO")[COLOR="SeaGreen"] '(chỉ là cột doanh số)[/COLOR]
    Set oVungThuong = Application.Range("THUONG") [COLOR="SeaGreen"]'(gồm có cột doanh số và cột thưởng)[/COLOR]
    
    Set ofn = Application.WorksheetFunction
    
[COLOR="SeaGreen"]    'Tim gia tri doanh so thap nhat trong bang doanh so
    'Neu muc DS < muc doanh so thap nhat thi thoat khongtinh nua.[/COLOR]
    If DS < ofn.Min(oVungDS) Then Exit Function
    
    DS1 = ofn.Lookup(DS, oVungDS) [COLOR="SeaGreen"]'DS1 <= DS[/COLOR]
    ThuongDS = ofn.VLookup(DS1, oVungThuong, 2, 0)
      
    NhanThuong = NhanThuong + ThuongDS
    
[COLOR="SeaGreen"]    'Lay phan du (phan con lai cua DS)[/COLOR]
    DS2 = DS - DS1
    
    If DS2 > 0 Then [COLOR="SeaGreen"]'Nếu còn doanh số thì tiếp tục tính thưởng. Phép Đệ quy[/COLOR]
        NhanThuong = NhanThuong +[B] NhanThuong(DS2)[/B]
    End If
     
    Set ofn = Nothing
    Set oThuongDS = Nothing
    Set oVungThuong = Nothing
End Function

Những bài toán có kiểu Đệ quy, nếu dùng công thức Excel thuần túy (không dùng VBA + lặp, Đệ quy) sẽ rất khó làm, thậm chí là không thể làm được.

 

[rollover79]

Function [B]NhanThuong[/B](DS As Variant)
[COLOR=Blue]     [COLOR=Black]Dim ofn As WorksheetFunction[/COLOR]
[/COLOR]    Dim oVungThuong As Range, oVungDS As Range
    Dim DS1, DS2, ThuongDS
    
    Set oVungDS = Application.Range("DOANHSO")[COLOR=SeaGreen] '(chỉ là cột doanh số)[/COLOR]
    Set oVungThuong = Application.Range("THUONG") [COLOR=SeaGreen]'(gồm có cột doanh số và cột thưởng)[/COLOR]
    
    Set ofn = Application.WorksheetFunction
    
[COLOR=SeaGreen]    'Tim gia tri doanh so thap nhat trong bang doanh so
    'Neu muc DS < muc doanh so thap nhat thi thoat khongtinh nua.[/COLOR]
    If DS < ofn.Min(oVungDS) Then Exit Function
    
    DS1 = ofn.Lookup(DS, oVungDS) [COLOR=SeaGreen]'DS1 <= DS[/COLOR]
    ThuongDS = ofn.VLookup(DS1, oVungThuong, 2, 0)
      
    NhanThuong = NhanThuong + ThuongDS
    
[COLOR=SeaGreen]    'Lay phan du (phan con lai cua DS)[/COLOR]
    DS2 = DS - DS1
    
    If DS2 > 0 Then [COLOR=SeaGreen]'Nếu còn doanh số thì tiếp tục tính thưởng. Phép Đệ quy[/COLOR]
        NhanThuong = NhanThuong +[B] NhanThuong(DS2)[/B]
    End If
     
    Set ofn = Nothing
    Set oThuongDS = Nothing
    Set oVungThuong = Nothing
End Function

Đây đúng là 1 hàm đệ quy, nhưng có 1 vấn đề như sau, khi tôi nhập vào công thức

=nhanthuong(5,000,000,000,000)

Thì sẽ trả về lỗi #VALUE, tại sao thế. Tôi xin phép được giải thích 1 chút về bài toán này.
Trước hết ta cần xem tại sao trường hợp trên bị lỗi, để biết được lỗi cụ thể các bạn hãy sửa code lại thành như sau:

Function NhanThuong(DS As Variant)
[COLOR=Blue]     On Error GoTo loi
[/COLOR]    Dim ofn As WorksheetFunction
    Dim oVungThuong As Range, oVungDS As Range
    Dim DS1, DS2, ThuongDS
    
    Set oVungDS = Application.Range("DOANHSO") '(chi? là co^.t doanh so^')
    Set oVungThuong = Application.Range("THUONG") '(go^`m có co^.t doanh so^' và co^.t thu+o+?ng)
    
    Set ofn = Application.WorksheetFunction
    
    'Tim gia tri doanh so thap nhat trong bang doanh so
    'Neu muc DS < muc doanh so thap nhat thi thoat khongtinh nua.
    If DS < ofn.Min(oVungDS) Then Exit Function
    
    DS1 = ofn.Lookup(DS, oVungDS) 'DS1 <= DS
    ThuongDS = ofn.VLookup(DS1, oVungThuong, 2, 0)
      
    NhanThuong = NhanThuong + ThuongDS
    
    'Lay phan du (phan con lai cua DS)
    DS2 = DS - DS1
    
    If DS2 > 0 Then 'Ne^'u còn doanh so^' thì tie^'p tu.c tính thu+o+?ng. Phép ?e^. quy
        NhanThuong = NhanThuong + NhanThuong(DS2)
    End If
     
    Set ofn = Nothing
    Set oThuongDS = Nothing
    Set oVungThuong = Nothing
[COLOR=Blue]    Exit Function
[/COLOR][COLOR=Blue]loi:
    MsgBox Err.Description
[/COLOR]End Function

Chú ý phần màu xanh là phần tôi thêm vào. Giờ về Sheet và nhập lại công thức trên bạn sẽ thấy có 1 thông báo là Out of stack space. Thông báo lỗi này đại loại là bị tràn bộ nhớ stack(bác nào quan tâm thì tìm hiểu thêm bộ nhớ Stack này nhé), như bài trước tôi đã có giải thích cách 1 hàm đệ quy chạy như thế nào, nó sẽ lùi dần về hàm cơ sở để chạy trước để tính ra kết quả cơ sở rồi mới tính ngược trở lại, khi lùi dần thì các trạng thái trung gian đó sẽ được lưu vào bộ nhớ(chính là bộ nhớ Stack), do đó khi hàm Đệ quy quá lớn như trường hợp này sẽ bị tràn bộ nhớ Stack.
- Giờ tôi xin bàn 1 chút về bài toán này: Đây thực chất là 1 bài toán đệ quy không đầy đủ, nó chỉ đệ quy với những giá trị nhỏ hơn 500,000,000(Max doanh số) mà thôi, còn những giá trị lớn hơn hoặc bằng 500,000,000 thì nó không còn tuân theo quy luật nữa, khi đó chỉ cần lấy phần nguyên của Doanh số cần tính chia cho 500,000,000 rồi nhân với mức thưởng tương ứng của 500,000,000 là xong. Để thể hiện chỗ này tôi xin được sửa code 1 chút như sau:

Function NhanThuong(DS As Variant)
    On Error GoTo loi
    Dim ofn As WorksheetFunction
    Dim oVungThuong As Range, oVungDS As Range
    Dim DS1, DS2, ThuongDS
    
    Set oVungDS = Application.Range("DOANHSO") '(chi? là co^.t doanh so^')
    Set oVungThuong = Application.Range("THUONG") '(go^`m có co^.t doanh so^' và co^.t thu+o+?ng)
    
    Set ofn = Application.WorksheetFunction
    
[COLOR=Blue]    ' Add by Rollover
    Dim maxDS
    maxDS = ofn.Max(oVungDS)
    If DS > maxDS Then
        NhanThuong = ofn.Floor(DS / maxDS, 1) * ofn.VLookup(maxDS, oVungThuong, 2, 0)
        DS = DS - (ofn.Floor(DS / maxDS, 1) * maxDS)
    End If
    ' End add------------------------------
[/COLOR]    'Tim gia tri doanh so thap nhat trong bang doanh so
    'Neu muc DS < muc doanh so thap nhat thi thoat khongtinh nua.
    If DS < ofn.Min(oVungDS) Then Exit Function
    
    DS1 = ofn.Lookup(DS, oVungDS) 'DS1 <= DS
    ThuongDS = ofn.VLookup(DS1, oVungThuong, 2, 0)
      
    NhanThuong = NhanThuong + ThuongDS
    
    'Lay phan du (phan con lai cua DS)
    DS2 = DS - DS1
    
    If DS2 > 0 Then 'Ne^'u còn doanh so^' thì tie^'p tu.c tính thu+o+?ng. Phép ?e^. quy
        NhanThuong = NhanThuong + NhanThuong(DS2)
    End If
     
    Set ofn = Nothing
    Set oThuongDS = Nothing
    Set oVungThuong = Nothing
    Exit Function
loi:
    MsgBox Err.Description
End Function

Phần tôi diễn giải bên trên được thể hiện trong những dòng màu xanh.
Bài toán này cũng có thể dùng công thức trực tiếp mà không cần dùng VBA, khi đó cần phải bố trí lại dữ liệu và dùng các ô tạm. Tôi xin gửi 1 file dùng công thức để khử đệ quy cho bài này như sau:

 

[rollover79]

Còn đây là lời giải cho bài toán thứ 2, tất nhiên là dùng đệ quy(không đảm bảo là nó sẽ không bị lỗi tràn bộ nhớ), bác nào có thời gian làm ơn khử đệ quy giúp em bài này với.

 

[ThuNghi]

C
1) Viết một hàm tính thưởng theo doanh số.
Doanh số Thưởng
10,000,000 0.5
20,000,000 1
30,000,000 1.5
50,000,000 2.5
70,000,000 4
100,000,000 2.5
150,000,000 9
200,000,000 13
300,000,000 20
400,000,000 27
500,000,000 40
Thuong(540,000,000) = 42 =(40 + 1.5 + 0.5)

Cái số màu đỏ có sai không. Đang là 4 lại xuống 2.5

 

[manhhung12]

Cái số màu đỏ có sai không. Đang là 4 lại xuống 2.5

Theo tôi hiểu không có gì là sai cả, vì đơn thuần là data.
Đệ quy là 1 thuật toán đẻ giải quyết các bài toán phức tạp. Đưa vấn đề phức tạp về đơn giản, và có những bài toán chỉ giải quyết được bằng thuật toán đẹ quy.

 

[lypt]

Những bài toán có kiểu Đệ quy, nếu dùng công thức Excel thuần túy (không dùng VBA + lặp, Đệ quy) sẽ rất khó làm, thậm chí là không thể làm được.

Các bài khác thì chưa biết, riêng bài thưởng doanh số này thì dựa vào thuật toán anh TuanVNUNI đưa ra, Excel xử lý đâu có khó. Các anh xem thử có thiếu sót ở đâu không?

 

[ptm0412]

Theo tôi, chủ đề của anh TuanVNUNI là thuật toán đệ quy, từ dễ đến khó. Dễ thì công thức làm được, nhưng vẫn cần thí dụ đệ quy cho trường hợp dễ để người chưa biết học từ từ.
Vậy mình đề nghị chỉ bàn về đệ quy trong topic này.

 

[lypt]

Vậy mình đề nghị chỉ bàn về đệ quy trong topic này.

Đồng ý. Chưa tìm ra đệ quy khó. Tạm lấy một cái dễ nữa vậy. Ai cũng biết dãy số Fibonacci 1, 1, 2, 3, 5, 8, 13, ...tức là số sau = tổng 2 số trước. Có phải giải như thế nãy là đệ quy :

Function Fibonacci(ByVal n As Long) As Variant
    If n = 1 Or n = 2 Then
        Fibonacci = 1
    Else
        Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
    End If
End Function

 

[Nguyễn Duy Tuân]

Cái số màu đỏ có sai không. Đang là 4 lại xuống 2.5

Vâng, cũng có thể con số chưa thực tế lắm, chúng ta coi nó là data để thực hiện mục đích anh ạ.

Các bài khác thì chưa biết, riêng bài thưởng doanh số này thì dựa vào thuật toán anh TuanVNUNI đưa ra, Excel xử lý đâu có khó. Các anh xem thử có thiếu sót ở đâu không?

Sự phối hợp thức của bạn cũng sáng tạo. Cách của bạn là tạo ra các cột phụ và các dòng phụ, kết quả tính được lại vận dụng để tính tiếp ở kết quả sau. Nếu xét về mặt kỹ thuật lập công thức thì nó chưa phải là tốt, vì chưa gói lại thành một và chưa có cơ sở để tin rằng nó bao quát hết các trường hợp. Giả sử còn có nhiều mức thưởng được chia nhỏ và có một danh sách danh sách nhân viên cỡ 200 người với cột doanh số đạt của từng người, bây giờ cần tạo cột để tính thưởng cho từng người. Nếu dùng công thức như của bạn thì có copy cho cả 200 người không được? Bạn có thể phát triển thêm công thức của bạn nhé! Có thể sẽ làm được nhưng bạn sẽ thấy vấn đề thực sự phức tạp.

Chúng ta lại quay trở về vấn đề "Đệ quy".

Cảm ơn bạn rollover79 đã đưa ra cách gải của ví dụ 2) liệt kê các thư mục con trong một thư mục xác định, cách làm rất ngắn gọn nhờ vào Shell.Application.

Tôi xin gửi mã nguồn trong file bạn rollover79 đã gửi để chúng ta đem phân tích. Bạn rollover79 hay ai đó có thể giải thích từng dòng lệnh để tất cả các bạn đang quan tâm đến Đệ quy có thể hiểu sâu hơn.

Dim objFSO As New FileSystemObject
Dim TotalFiles As Double

Public Sub LoadAllFolder()
    Dim Path As String
    
    Dim ShellApp As Object
    Set ShellApp = CreateObject("Shell.Application").BrowseForFolder(0, "Please choose a folder", 0, OpenAt)
    On Error Resume Next
    Path = ShellApp.self.Path
    On Error GoTo 0
    Set ShellApp = Nothing
    
    If Not objFSO.FolderExists(Path) Then Exit Sub
    TotalFiles = 0
    Application.Cursor = xlWait
    ActiveSheet.UsedRange = ""
    Call LoadFolder(Path, 1)
    Application.Cursor = xlDefault
End Sub

Private Sub [B]LoadFolder[/B](strPath As String, Dept As Double)
    If Not objFSO.FolderExists(strPath) Then Exit Sub
    Dim objFolder As Folder
    TotalFiles = TotalFiles + 1
    Cells(TotalFiles, Dept) = objFSO.GetFolder(strPath).Name
    For Each objFolder In objFSO.GetFolder(strPath).SubFolders
        Call [B]LoadFolder[/B](objFolder.Path, Dept + 1)
    Next
End Sub

Các bạn khác có thể lục lại các tình huống tính toán nào có dạnh Đệ quy không? Nếu có chúng ta đem lên để thực hiện.