TÌM SỐ FIBONACCI THỨ N

haond về một chủ đề khá là thú vị, đó là bài toán: Tính tổng những số Fibonacci từ 1 tới 4 triệu

Giải pháp đơn giản

Để tính một trong những Fibonacci thì cực kỳ đơn giản, chỉ cần làm theo công thức:

$F_n=F_n-1+F_n-2$Code thì khá là đối chọi giản bằng cách dùng đệ quy:

func Fibonacci(n: Int) -> Int { if n Hoặc sử dụng vòng lặp để khử đệ quy:

func Fibonacci(n: Int) -> Int { var a = 0 var b = 1 var next = 0 for i in 0..Quay lại vấn đề tính tổng những số Fibonacci, ta hoàn toàn có thể implement một hàm tính tổng đơn giản dễ dàng như sau:

func Sum(n: Int) -> Int { var sum = 0 for i in 0..Tuy nhiên thì với thuật toán như vậy, chúng ta có gặp phải vấn đề gì không?

Câu vấn đáp là có, vụ việc rất lớn!

Đầu tiên hãy nhìn vào thứ thị biểu diễn thời gian cần để tính Fibonacci dưới đây:

Dễ dìm thấy, cùng với số n càng lớn, thì thời hạn để tính Fibonacci của số đó càng lâu.

Bạn đang xem: Tìm số fibonacci thứ n

Cho nên đối với bài toán ở đấy là tính tổng những số Fibonacci từ một tới 4 triệu, thì xét về nguyên tố thời gian, điều này cũng biến đổi một vấn đề bất khả thi rồi. Để xử lý bài toán này, họ cần phải vứt bỏ được vấn đề thời hạn do chạy đệ quy hoặc vấn đề lặp khiến ra.

Vì mọi vấn đề liên quan mang lại số học tập đều, hiển nhiên, hoàn toàn có thể biểu diễn được bằng toán học, vậy đây cũng chưa hẳn là nước ngoài lệ, hãy xem bạn cũng có thể mượn được gì tự toán nào.

Công thức tính tổng n số Fibonacci

Chúng ta có công thức tính tổng n số Fibonacci với đa số số n >= 2 như sau:

$$mboxS_n;=;sum_i=1^nF_i=;F_n+2; -; 1$$Nếu không tin tưởng tưởng vào công thức, thì các bạn có thể tham khảo chứng minh công thức tại đây

Vậy nhằm tính tổng các số Fibonacci từ 1 tới 4 triệu, bạn cũng có thể tìm số Fibonacci trang bị 4 triệu lẻ 2 (4,000,002) rồi trừ giá trị này đi mang đến 1. Bài xích toán trở lại tìm một trong những Fibonacci bất kì.

Tuy nhiên, 4 triệu lẻ 2 vẫn là một trong những con số quá lớn để hoàn toàn có thể tính toán thông thường trên một đồ vật tính cá nhân (với những yếu tố như: tốc độ xử lý, giới hạn bộ nhớ, giới hạn của loại dữ liệu,...). Bọn họ cần tra cứu một giải pháp khác ít tốn kém hơn.

Xem thêm: Văn Hóa Đọc Sách Của Người Nhật Bản Bắt Nguồn Từ Đâu, Nét Văn Hóa Đẹp Của Người Nhật

Công thức tìm một số trong những Fibonacci bất kì

Sử dụng phương pháp Binet

Chúng ta tất cả thêm công thức Binet để tìm một số Fibonacci bất cứ như sau:

$$F_n;=;fracphi ^n; -; left( -phi ight)^-nsqrt5$$Chi tiết về kí hiệu $phi$ (phi): Xem tỉ lệ vàng

Công thức trên hoàn toàn có thể được triển khai thành:

$$F_n;=;fracleft( 1; +; sqrt5 ight)^^n; -; left( 1; -; sqrt5 ight)^^n2^^nsqrt5$$Áp dụng 2 bí quyết trên, bạn có thể loại bỏ hoàn toàn việc áp dụng đệ quy hoặc vòng lặp, và điều này sẽ cải thiện tốc độ đo lường và tính toán một biện pháp đáng kể.

Cách implement thì rất là đơn giản:

import Foundationfunc Fibonacci(n: Double) -> Double return (pow((1.0 + sqrt(5.0)), n) - pow((1.0 - sqrt(5.0)), n)) / (pow(2.0, n) * sqrt(5.0))func Sum(n: Double) -> Double return Fibonacci(n: n + 2.0) - 1.0Một điểm yếu kém duy duy nhất của biện pháp này là việc tính toán với căn bậc 2 trên máy tính sẽ dẫn tới chứng trạng làm tròn số và sẽ mở ra sai số tốt nhất định làm cho giá trị ko thực sự chủ yếu xác.

Sử dụng ma trận

Sau khi viết bài bác này thì được a
kiennt reviews thêm một cách khác, đó là sử dụng ma trận.

Quay trở lại công thức tính một trong những Fibonacci:

$$F_n=F_n-1; +; F_n-2$$Đồng nghĩa với:

$$F_n+2=F_n+1+F_n$$Vì vậy ta hoàn toàn có thể biểu diễn dưới dạng ma trận như sau:

$$left< eginarrayc F_n+2 \ F_n+1 endarray ight>; =; left< eginarrayc F_n+1; +; F_n \ F_n+1 endarray ight>; =; left< eginarraycc 1 và 1 \ 1 & 0 endarray ight>; left< eginarrayc F_n+1 \ F_n endarray ight>$$Nếu thiếu tín nhiệm thì các bạn cứ test tự minh chứng đi :3, tiếp, ta cũng có thể viết lại biểu thức trên thành:

$$left< eginarrayc F_n+1 \ F_n endarray ight>; =; left< eginarraycc 1 & 1 \ 1 và 0 endarray ight>; left< eginarrayc F_n \ F_n-1 endarray ight>$$Và sau thời điểm thực hiện tại một vài ba phép tính toán dễ dàng và đơn giản trên ma trận chúng ta thu được tác dụng sau:

$$left< eginarrayc F_n+1 \ F_n endarray ight>; =; left< eginarraycc 1 và 1 \ 1 và 0 endarray ight>^n; left< eginarrayc F_1 \ F_0 endarray ight>$$Với F(1) = 1 cùng F(0) = 0. Bài bác toán trở lại dạng câu hỏi nhân 2 ma trận 2x2 và nhân một ma trận 2x2 với cùng 1 ma trận 2x1.

Xem thêm: Hướng Dẫn Cách Buộc Dây Giày Thể Thao Nữ Đẹp Đơn Giản Mà Độc Đáo

Dưới đây là đoạn implement bằng Python của a
kiennt:

def mul_metrix_1(m1, m2): return ( m1<0><0> * m2<0> + m1<0><1> * m2<1>, m1<1><0> * m2<0> + m1<1><1> * m2<1> )def mul_matrix(m1, m2): """ matrix m1, m2 is 2x2 matrix which is respresend lượt thích ((r00, r01), (r10, r11)) """ return ( (m1<0><0> * m2<0><0> + m1<0><1> * m2<1><0>, m1<0><0> * m2<0><1> + m1<0><1> * m2<1><1>), (m1<1><0> * m2<0><0> + m1<1><1> * m2<1><0>, m1<1><0> * m2<0><1> + m1<1><1> * m2<1><1>) )def pow_matrix(m, n): """ m is 2x2 matrix """ if n == 1: return m elif n % 2 == 0: a = pow_matrix(m, n / 2) return mul_matrix(a, a) else: return mul_matrix(pow_matrix(m, n - 1), m)def fibo(n): if n == 0: return 1 if n == 1: return 1 a = ((1, 1), (1, 0)) an = pow_matrix(a, n) pair_0 = (1, 1) pair_n = mul_metrix_1(an, pair_0) return pair_n<1>for i in xrange(2, 10): print fibo(i)Xin rất cảm ơn ae nhóm #hardcore của cộng đồng Ruby vn đã tích cực luận bàn để tổng vừa lòng thành bài viết này.

Hy vọng nội dung bài viết phần nào góp cho chúng ta nhận ra sự quan trọng đặc biệt của việc ứng dụng toán học, nhất là việc sử dụng ma trận vào xử lý các bài toán phức tạp. Viết kết thúc bài tổng hòa hợp này mình vẫn còn đó ngồi rứa tay lên trán nhưng mà suy nghĩ, giá nhưng hồi đó mình chuyên học toán rộng thì tốt biết mấy