Bài tập đệ quy trong VBA

tuhocvba

Administrator
Thành viên BQT
Trong các sách lập trình đã nói nhiều, mình xin nhắc lại:
Một đối tượng được gọi là đệ quy nếu nó được mô tả thông qua định nghĩa của chính nó. Nghĩa là, các đối tượng này được định nghĩa một cách quy nạp từ những khái niệm đơn giản nhất cùng dạng với nó. Trong toán học và tin học có rất nhiều đối tượng như thế.

Ví dụ:
0! = 1
1! = 1
2! = 1! * 2
3! = 2! *3
4! = 3! *4
Thuật toán đệ quy được sử dụng nhiều trong lập trình, ưu điểm cho tốc độ thực thi rất nhanh, code gọn gàng. Những người có thể code đệ quy thường được đánh giá cao.
Bài toán liệt kê các subfolder trong một folder cũng phải sử dụng thuật toán đệ quy. Cứ trong mỗi folder tìm được, ta lại sử dụng chính nó để tìm kiếm tiếp bên trong folder tìm được ấy có folder nào nữa không,...

Trong topic này sẽ liệt kê các bài toán đệ quy từ dễ tới phức tạp để mọi người cùng làm quen và luyện tập.

Bài tập 1:
Cho n là số tự nhiên. Hãy xây dựng hàm tính tổng: F ( n ) = 0+1+2+...+n
Lời giải:
Mã:
Sub test()
Dim i As Long
i = 10
MsgBox tinhtong(i)
End Sub
Function tinhtong(ByVal n) As Long
    If n = 0 Then
        tinhtong = 0
        Exit Function
    End If
    tinhtong = tinhtong(n - 1) + n
End Function
Bài tập 2: Cho n là số tự nhiên. Tính tổng:
\[ F ( n ) = 0^2 + 1^2 + 2^2+...+n^2 \]

Bài tập 3: Cho n là số tự nhiên. Tính tổng F ( n ) = 0! + 1! + 2! + ... + n!
 
Bài tập 2:
Lời giải:

Mã:
Sub test2()
    Dim i As Long
    i = 3
    MsgBox tinhtongbinhphuong(i)
End Sub
Function tinhtongbinhphuong(ByVal n As Long) As Long
    If n <= 0 Then
        tinhtongbinhphuong = 0
        Exit Function
    End If
    tinhtongbinhphuong = tinhtongbinhphuong(n - 1) + (n ^ 2)
    
End Function
Bài tập 3:
Lời giải:

Mã:
Sub test3()
    Dim i As Long
    i = 1
    If i < 0 Then Exit Sub
    MsgBox tinhtongiaithua(i)
End Sub
Function tinhtongiaithua(ByVal n As Long) As Long
    If n = 0 Then
        tinhtongiaithua = 1
        Exit Function
    End If
    tinhtongiaithua = tinhtongiaithua(n - 1) + giaithua(n)
    
End Function
Function giaithua(ByVal n As Long) As Long
    If n = 0 Then
        giaithua = 1
        Exit Function
    End If
    giaithua = n * giaithua(n - 1)
End Function
Bài tập 4: Cho dãy Fibonacci:
\[ F(0)=0, F(1)=1,F\: n = F\: (n-1) + F\: (n-2) \]
Hãy in số F(100)
 

tuhocvba

Administrator
Thành viên BQT
Bài tập 4:
Lời giải:

Dãy có giá trị khá lớn khi n tăng dần.
Thay vì in F(100) thì ở đây in F(30) :
Mã:
Sub test()
    Dim i As Long
    i = 30
    If i < 0 Then Exit Sub
    MsgBox fibonacci(i)
End Sub
Function fibonacci(ByVal n As Long) As Long
    If n = 0 Or n = 1 Then
        fibonacci = 1
        Exit Function
    End If
    fibonacci = fibonacci(n - 1) + fibonacci(n - 2)
End Function
Bài tập 5: Tính số hạng n của dãy:

\[ x(0) = 1; y(0) = 0;x( n ) = x(n-1)+ y( n-1);y( n ) = 3*x( n-1)+2*y( n-1) \]
 

NhanSu

SMod
Thành viên BQT
Mình giải bài 5, code sử dụng gọi thủ tục bằng ByRef để nhận giá trị x, y trả về qua tham số.
Mã:
Sub Recursive(n As Long, x As Long, y As Long)
    If n > 0 Then
        Recursive n - 1, x, y
        x = x + y
        y = 3 * x - y
    Else
        x = 1
        y = 0
    End If
End Sub
Sub test()
    Dim n&, x&, y&
    n = 10
    Recursive n, x, y
    Debug.Print n, x, y
End Sub
 

NhanSu

SMod
Thành viên BQT
Đệ quy nói chung là chậm, mình code thử tìm dãy Fibonacci trên C# tối đa được F(93) do giới hạn của số ulong là khoảng 18 tỷ tỷ. Nếu dùng vòng lặp thì ra kết quả ngay còn đệ quy thì 5 phút không ra.
 
B

bvtvba

Guest
Bạn @NhanSu kiên nhẫn thật. Dãy fibonacci thì khủng khiếp rồi.
Mình cũng xin góp vui lời giải bài toán 5:
Lời giải:
Mã:
Function tinhX(ByVal n As Long) As Long
    If n = 0 Then
        tinhX = 1
        Exit Function
    End If
    tinhX = tinhX(n - 1) + tinhY(n - 1)
End Function
Function tinhY(ByVal n As Long) As Long
    If n = 0 Then
        tinhY = 0
        Exit Function
    End If
    tinhY = (3 * tinhX(n - 1)) + (2 * tinhY(n - 1))
End Function
Sub test2()
    Dim n&, x&, y&
    n = 10
    
    Debug.Print n, tinhX(n), tinhY(n)
End Sub
Đệ quy hay dùng trong các bài thi học sinh giỏi tin ngày xưa.
Bài toán 6: Giả sử chúng ta có n đồng xu nặng lần lượt là W1, W2, ..., Wn, và bài toán đặt ra là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị A. Tất nhiên, số lượng đồng xu là không giới hạn.

Ví dụ:
n = 5
W1 = 1
W2 = 1
W3 = 1
W4 = 2
W5 = 3
A = 5
Thì số lượng đồng xu nhỏ nhất là 2. Ta sử dụng đồng xu W4 và W5, chúng có tổng khối lượng bằng A.
 

NhanSu

SMod
Thành viên BQT
Mình thử bài 6 với điều kiện các đồng xu có khối lượng là số tự nhiên sắp thứ tự từ nhỏ đến lớn:
Mã:
Private ArrXu()
Function SoXuNhoNhat(ByVal n As Long) As Long
    Dim Min As Long, i As Long, tmp As Long
    Min = 0
    If n < ArrXu(1, 1) Then
        SoXuNhoNhat = 0
        Exit Function
    End If
    For i = UBound(ArrXu) To LBound(ArrXu) Step -1
        If n = ArrXu(i, 1) Then
            SoXuNhoNhat = 1
            Exit Function
        ElseIf n > ArrXu(i, 1) Then
            tmp = SoXuNhoNhat(n - ArrXu(i, 1)) + 1
            If (tmp > 1) And ((tmp < Min) Or (Min = 0)) Then Min = tmp
        End If
    Next
    SoXuNhoNhat = Min
End Function
Sub Bai6()
    Dim i&, n&
    ArrXu = Range("A1", Range("A" & Rows.Count).End(xlUp))
    n = 5
    Debug.Print SoXuNhoNhat(n)
End Sub
 
Sửa lần cuối:
B

bvtvba

Guest
@NhanSu : Bài giải 6 của bạn, mình chạy với dữ liệu có đáp án thì có vẻ ổn.
Mình cho n = 100. Với dữ liệu này chạy cả tiếng không có thông báo gì. Mong muốn nhận thông báo là = 0. (Không tìm được đáp án phù hợp).
Bạn cần đăng nhập để thấy hình ảnh
 

NhanSu

SMod
Thành viên BQT
Khi n=100 dễ thấy đáp số là 20, mình chạy thử thấy quay rất lâu không ra kết quả, code mình chậm do phải gọi đệ quy nhiều lần, không biết các bạn dùng đệ quy có nhanh hơn không. Nếu không dùng đệ quy thì code nhanh hơn nhiều, n=10^6 chưa đến 2 giây, mình không post ở đây vì không đúng chủ đề.
 
Top