HomeOur Team
Dãy số Fibonacci
Others
[Code Vui] Fibonacci và những cách tính biểu thức?
anh.pham
anh.pham
March 25, 2021
2 min

Hẳn là các anh/chị/em đã từng học qua/nghe qua về dãy số Fibonacci , khỏi cần phải bàn về độ hot của nó. Nói qua một chút về Fibonacci: là một dãy số kinh điển trong toán học được tìm thấy cách đây hơn 800 năm. Dù đã có lịch sử 800 năm nhưng đến ngày nay, dãy số Fibonacci vẫn đem đến cho các nhà khoa học nhiều bất ngờ. Bất ngờ gì thì thôi e để link google cho mọi người tìm hiểu ( https://tuoitre.vn/day-so-fibonacci-va-nhung-bi-an-trong-tu-nhien-20180313151043875.htm ).

Nội dung chính của bài viết này, đó là có những cách nào để có thể tính được dãy số Fibonacci trên.

Theo kết quả tìm kiếm lục lọi, lê lết trên các diễn đàn thì em mới ngợ ra được rằng có nhiều cách làm vừa hay mà còn tăng được khả năng so sánh và tối ưu cho từng cách làm.

  • Cách 1: Đệ quy thần thánh\ Đây là cách làm phổ thông nhất, hồi đi học em hay làm như thế, vừa nhanh mà còn đúng… nhưng lẽ đời là thế: Cái gì rẻ và nhanh thì sẽ không ngon.

cach1
Cách 1 so deep :))

Kết quả: Cách này khá là easy =)) nhưng tốc độ lại chậm như rùa vậy, nếu như phần tử dãy số nhỏ thì không sao, khoảng đến 40 phần tử là mất khoảng 1s mới xong rồi.

  • Cách 2: Cũng dùng đệ quy nhưng cải biên chút.

    Thay vì việc phải tính lại các giá trị đã từng tính qua, chúng ra lưu trữ nó lại để sử dụng cho lần sau. Từ cách 1 sang cách này, cảm thấy bản thân có thể sẵn sàng làm việc cho “Gút gồ” rồi :v.

cach2
Cách 2

Code thật tươi sáng, cơ mà “ối dời ơi: nhanh hơn chút đấy nhưng còn kém lắm. 41 phần tử là cũng thấy `hơi` lâu”.

  • Cách 3: Từ cách 2, cải biên chút nữa có được không???

    Câu trả lời là có thể: Vì sao lại phải tính fibonacci(n-1)fibonacci(n-2) trong khi có thể các giá trị đó đã có lưu trong thằng hashMap rồi. Vậy chúng ta sẽ có cách thứ 3, đó là cấp tiến, sử dụng giá trị được tính sẵn của số fibo đằng trước cho thằng sau còn nếu không có, thì ta lại đệ quy.

cach3
Cách 3

Có thể 40 phần tử không làm khó cách này, tuy nhiên, nếu số phần tử càng lên cao thì có khả năng MainThread cũng phải đình công sớm :3. Cho nên cách này vẫn chưa được cho lắm.

  • Cách 4: Loại bỏ đệ quy

    Khi chỉ số i tăng dần, cũng tức là trong hashMap cũng đã tồn tại các giá trị fibonacci trước đó rồi, vậy thì cần gì đệ quy nữa, bỏ nó đi, thay vào đó sử dụng vòng lặp lấy giá trị trong hashMap . Thử xem cuộc đời có tươi mới hơn không?

cach4

Chính xác!!! Sau khi loại bỏ đệ quy đi, cảm giác tốc độ nó nhanh hơn hẳn. Em đã thử trường hợp 81 phần tử, chưa đến 1s nó đã xuất hiện kết quả. Tuy nhiên, cái gì nhanh và ngon ấy thì nó sẽ có giá đắt. Và giá đắt ở đây: Tài nguyên bị chiếm đóng nhiều. Bởi vì đã dùng mảng quy hoạch động rồi, còn dùng thêm các vòng lặp for để tìm phần tử rồi gán phần tử nữa.

  • Cách 5: Bỏ quy hoạch động, quay về nguyên thủy: for

    Định nghĩa của Fibonacci là: Fn = Fn-1 + Fn-2 vậy thì thử dùng cách này xem sao?

cach5
Cách 5

Cách này khá dễ hiểu, gọn và đáp ứng được nhu cầu: Chi phí thấp và tốc độ nhanh.

Bài viết em thấy cũng dài rồi, thôi em xin phép dừng lại tại đây, còn nhiều cách để có thể tối ưu nhất về mặt tốc độ và chi phí tiêu hao..Và cũng như việc phát triển thêm 1 thuật toán sẽ rất có ích cho việc tư duy của bản thân.


Tags

202103algorithms
anh.pham

anh.pham

Developer

Related Posts

System operator: Những câu chuyện chưa từng được kể (Phần 1)
System operator: Những câu chuyện chưa từng được kể (Phần 1)
March 31, 2021
5 min
Why Protocol-Oriented Programming?
Articles
Why Protocol-Oriented Programming?
March 31, 2021
2 min
Nâng cao bảo mật ứng dụng bằng Android NDK
Tips / Tricks
Nâng cao bảo mật ứng dụng bằng Android NDK
March 26, 2021
4 min
© 2021, All Rights Reserved.

Quick Links

HomeOur Team

Social Media