Tìm số fibonacci thứ n

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

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

Để tính một trong những Fibonacci thì rất là đơn giản, chỉ việc làm theo công thức:

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

func Fibonacci(n: Int) -> Int { if n Hoặc 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 bài toán tính tổng các số Fibonacci, ta có thể implement một hàm tính tổng đơn giản và 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 gỡ phải vụ việc gì không?

Câu trả lời là có, vụ việc rất lớn!

Đầu tiên hãy quan sát vào thứ thị biểu diễn thời hạn 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 các số Fibonacci từ 1 tới 4 triệu, thì xét về yếu tố thời gian, điều này cũng đổi thay một vụ việc bất khả thi rồi. Để xử lý bài toán này, họ cần phải loại bỏ được vấn đề thời gian do chạy đệ quy hoặc vấn đề lặp khiến ra.

Vì mọi sự việc liên quan mang đến 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 trên đây cũng chưa hẳn là nước ngoài lệ, hãy xem bạn có thể mượn được gì từ bỏ toán nào.

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

Chúng ta bao gồm 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ũng có thể tham khảo chứng tỏ công thức tại đây

Vậy để tính tổng các số Fibonacci từ là một tới 4 triệu, chúng ta cũng có thể tìm số Fibonacci máy 4 triệu lẻ 2 (4,000,002) rồi trừ quý giá này đi cho 1. Bài bác toán trở về tìm một số trong những Fibonacci bất kì.

Tuy nhiên, 4 triệu lẻ 2 vẫn là một trong con số quá to để có thể tính toán thông thường trên một máy tính cá nhân (với các yếu tố như: vận tốc xử lý, số lượng giới hạn bộ nhớ, giới hạn của hình trạng dữ liệu,...). Chúng ta cần kiếm tìm một chiến thuật khác ít tốn kém hơn.

Xem thêm: Phân Tích Đoạn Đầu Bài Thơ Vội Vàng Của Xuân Diệu Lớp 11, Phân Tích 13 Câu Đầu Bài Thơ Vội Vàng

Công thức tìm một vài Fibonacci bất kì

Sử dụng cách làm Binet

Chúng ta bao gồm thêm cách làm Binet nhằm tìm một số trong những Fibonacci bất kể như sau:

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

Công thức trê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 độ tính toán một giải pháp đáng kể.

Cách implement thì cực kỳ đơ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 yếu điểm duy tốt nhất của giải pháp này là việc đo lường và tính toán với căn bậc 2 trên laptop sẽ dẫn tới triệu chứng làm tròn số cùng sẽ lộ diện sai số tuyệt nhất định khiến cho giá trị không thực sự thiết 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 biện pháp khác, đó là dùng ma trận.

Quay trở về công thức tính một vài 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 có thể biểu diễn bê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 & 1 \ 1 và 0 endarray ight>; left< eginarrayc F_n+1 \ F_n endarray ight>$$Nếu không tin thì các bạn cứ thử tự chứng minh đi :3, tiếp, ta cũng hoàn toàn 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 và 1 \ 1 & 0 endarray ight>; left< eginarrayc F_n \ F_n-1 endarray ight>$$Và sau khi thực hiện nay một vài ba phép tính toán đơn giản dễ dàng trên ma trận họ thu được kết quả sau:

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

Xem thêm: Bài Giảng Ông Già Và Biển Cả (Hê Ming Uê), Bài Giảng Ông Già Và Biển Cả

Dưới đây là đoạn implement bởi 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, mét vuông 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 chân thành cảm ơn ae đội #hardcore của cộng đồng Ruby nước ta đã tích cực đàm đạo để tổng phù hợp thành nội dung bài viết này.

Hy vọng bài viết phần nào góp cho chúng ta nhận ra sự đặc trưng của việc ứng dụng toán học, nhất là việc áp dụng ma trận vào giải quyết các câu hỏi phức tạp. Viết ngừng bài tổng vừa lòng này mình vẫn tồn tại ngồi nuốm tay lên trán cơ mà suy nghĩ, giá mà lại hồi kia mình siêng học toán rộng thì giỏi biết mấy