Tính dãy Fibonacci?



  • Ví dụ kinh điển

    Khi mới học một ngôn ngữ, ta sẽ thường thấy một example có tên là Hello world, hay các tên khác ngầu hơn, chẳng hạn như hello, Hello world! Hello, world!... 😂

    Nhưng mặt hạn chế của Hello world là chỉ test được mỗi string, các syntax đơn giản hay gán biến, nối chuỗi... Từ đó người ta mới tìm ra thêm nhiều example khác giúp cho người mới đến có cái nhìn thân thiện hơn về ngôn ngữ 😂

    Và tất nhiên, code tính dãy fibonacci cũng được đưa vào example cho beginer vì nó có rất nhiều cách để tính, vừa show được các thành phần, tính năng của ngôn ngữ mà còn tăng thêm cảm giác thú dzị 😂

    Trong post này, mình sẽ nói đến 2 phương pháp thường gặp nhất.

    Sử dụng loop

    Có lẽ cách này ai cũng từng biết hoặc đã xem qua các example của @admin rồi nên mình không nói thêm.

    Sử dụng đệ quy

    Code:

    func fib(n int) uint64 {
        if (n == 0) {
            return 0
        }
        if (n == 1) {
            return 1
        }
        return fib(n - 1) + fib(n - 2)
    }
    

    Tại sao khi sử dụng cách này, số thứ N càng lớn thì càng tốn nhiều thời gian?

    Mời bạn xem qua run code thủ công 😂

    Ví dụ fib(5):

    • 5 != 0; 5 != 1; return fib(4) + fib(3)
      • 4 != 0; 4 != 1; return fib(3) + fib(2)
        • 3 != 0; 3 != 1; trả về fib(2) + fib(1)
          • 2 != 0; 2 != 1; return fib(1) + fib(0)
            • return 1 (còn fib(0) -> 0 mà lười quá, thôi end luôn 😂 )
          • return 1
        • 2 != 0; 2 != 1; return fib(1) + fib(0)
          • return 1
      • 3 != 0; 3 != 1; trả về fib(2) + fib(1)
        • 2 != 0; 2 != 1; return fib(1) + fib(0)
          • return 1
        • return 1

    Okê, cộng các return X với nhau, ta sẽ được kết quả 5, tức là fib(5) == 5.

    Nếu nhìn kỹ hàm sẽ thấy nó tiếp tục tách số ra thành hai số hạng trước nó và đi tìm, cứ lặp đi lặp lại cho đến khi tắt đường (N = 0) 😂

    Dính stack overflow! Từ này không phải là tên của trang hỏi đáp về lập trình hay công nghệ mà là tràn stack, tức là khi gọi hàm các giá trị cứ đẩy liên tục lên stack. Nếu hàm thoát (return) thì stack sẽ được dọn sạch sẽ, nhưng đối với hàm đệ quy thì nó cứ push lên cho đến khi end.

    Tốn nhiều thời gian là do các đệ quy cứ lặp đi lặp lại cho đến số nhỏ nhất, chẳng hạn 50 -> 0, 49 cũng -> 0, 48 cũng -> 0...

    Vì vậy ta cần một thứ gì đó để trữ chúng lại, tức là thằng nào đã tính rồi thì không cần tính nữa, tất nhiên là 50 -> 0 ngay và luôn.

    Optimize

    Đầu tiên là trữ các số đã tính và một mảng, mình sẽ chọn mảng 2 chiều.

    • arr[N][X] : N là số hạng, X là kết quả của nó.

    Nhưng trong Go không cho phép tạo lập mảng bằng một non-constant hay thay đổi kích thước mảng. Vì vậy mình sẽ sử dụng make (nó tựa như cấp phát động thôi).

    func fib(n int, cache *[]uint64) uint64 {
        if n == 0 {
            return 0
        }
        if n == 1 {
            return 1
        }
        if (*cache)[n] == 0 { // check nếu chưa tính
            // lưu lại kq
            (*cache)[n] = fib(n-2, cache) + fib(n-1, cache)
        }
        return (*cache)[n] // trả về số đã tính
    }
    
    func calc_fib(n int) uint64 {
    	cache := make([]uint64, n+1, n+1) // kích thước mảng
    	cache[0] = 1 // bắt đầu bằng 1
    	cache[1] = 1
    	return fib(n, &cache)
    }
    

    Ok, test thử nào!

    func main() {
        fmt.Println(calc_fib(40))
        fmt.Println(calc_fib(45))
        fmt.Println(calc_fib(50))
    }
    
    > $ go run main.go
    102334155
    1134903170
    12586269025
    

    Links


  • Trùm cuối

    @wuuyi awesome example bro 😉


Hãy đăng nhập để trả lời
 

Có thể bạn cũng quan tâm

.
DMCA.com Protection Status