Trên thực tế, hai số Fibonacci đầu tiên được xác định trước. Số Fibonacci đầu tiên là 0 và số Fibonacci thứ hai là 1. Với lập chỉ mục dựa trên số 0 và giả sử các số Fibonacci nằm trong một mảng, thì:
tại chỉ mục 0 , số Fibonacci là 0 , ( xác định trước ) ;tại chỉ mục 1 , số Fibonacci là 1 , ( xác định trước ) ;
tại chỉ mục hai , số Fibonacci là 1 = 1 + 0 , ( theo định nghĩa ) ;
tại chỉ mục 3 , số Fibonacci là hai = 1 + 1 , ( theo định nghĩa ) ;
tại chỉ mục 4 , số Fibonacci là 3 = hai + 1 , ( theo định nghĩa ) ;
tại chỉ mục 5 , số Fibonacci là 5 = 3 + hai , ( theo định nghĩa ) ;
tại chỉ mục 6 , số Fibonacci là số 8 = 5 + 3 , ( theo định nghĩa ) ;
tại chỉ mục 7 , số Fibonacci là 13 = số 8 + 5 , ( theo định nghĩa ) ;
tại chỉ mục số 8 , số Fibonacci là hai mươi mốt = 13 + số 8 , ( theo định nghĩa ) ;
tại chỉ mục 9 , số Fibonacci là 3. 4 = hai mươi mốt + 13 , ( theo định nghĩa ) ;
và như thế.
Trong lập trình, biến n chứ không phải biến i được sử dụng cho các chỉ mục dựa trên 0 cho các số Fibonacci này. Và cùng với đó, mười hai số Fibonacci đầu tiên là:
| 0 | 1 | 1 | hai | 3 | 5 | số 8 | 13 | hai mươi mốt | 3. 4 | 55 | 89 |
| 0 | 1 | hai | 3 | 4 | 5 | 6 | 7 | số 8 | 9 | 10 | mười một |
Hàng thứ hai trong bảng cung cấp các chỉ mục dựa trên 0, mỗi chỉ mục sẽ có biến n trong lập trình. Hàng đầu tiên cho các số Fibonacci tương ứng. Vì vậy, số Fibonacci không chỉ là bất kỳ số nào. Định nghĩa cốt lõi bắt đầu bằng 0, cho số Fibonacci đầu tiên và 1 cho số Fibonacci thứ hai. Các số còn lại được sản xuất từ đó.
Số Fibonacci có thể được tạo ra trong thời gian O (n) và cũng trong thời gian O (1). Đối với thời gian O (n), nếu n là 12 chẳng hạn, thì mười hai số Fibonacci đầu tiên sẽ được tạo ra. Đối với thời gian O (1), chỉ có một số Fibonacci được tạo ra. Ví dụ, nếu n là 6, thì số Fibonacci 8 sẽ được tạo ra.
Bài viết này giải thích hai cách tạo số Fibonacci trong Java.
Công thức cho một số Fibonacci
Có một công thức toán học cho số Fibonacci. Công thức này có thể được viết trong ba dòng hoặc một dòng. Trong ba dòng, nó được viết là:
nơi F N là số Fibonacci tại n dựa trên 0 thứ tự mục lục. Đây là cách xác định số Fibonacci.
Sản xuất số Fibonacci trong thời gian O (n)
Nếu các số Fibonacci được tạo ra trong O (3) lần, các số 0, 1, 1 sẽ được tạo ra; đó là ba số Fibonacci đầu tiên. N dựa trên 0 cuối cùng thứ tự chỉ số ở đây, là 2. Nếu các số Fibonacci được tạo ra trong O (7) lần, các số 0, 1, 1, 2, 3, 5, 8 sẽ được tạo ra; đó là bảy số Fibonacci đầu tiên. N dựa trên 0 cuối cùng thứ tự chỉ số ở đây, là 6. Nếu các số Fibonacci được tạo ra trong O (n) lần, các số 0, 1, 1, 2, 3, 5, 8 - - -, sẽ được tạo ra; đó là n số Fibonacci đầu tiên. N dựa trên 0 cuối cùng thứ tự chỉ số ở đây là n-1.
Phương thức Java trong một lớp để tạo ra n số Fibonacci đầu tiên là:
lớp Fibonacci {vô hiệu fibonacci ( int [ ] P ) {
int N = P. chiều dài ;
nếu ( N > 0 )
P [ 0 ] = 0 ;
nếu ( N > 1 )
P [ 1 ] = 1 ;
vì ( int tôi = hai ; tôi < N ; tôi ++ ) { // n = 0 và n = 2 đã được xem xét
int currNo = P [ tôi - 1 ] + P [ tôi - hai ] ;
P [ tôi ] = currNo ;
}
}
}
Lớp học, Fibonacci là riêng tư. Các fibonacci () phương thức nhận mảng P và trả về giá trị void. Phương thức bắt đầu bằng cách xác định độ dài của mảng. Độ dài n này là số lượng Fibonacci cần thiết. Số Fibonacci đầu tiên và thứ hai được xác định rõ ràng và được đặt vào vị trí đầu tiên và thứ hai trong mảng.
Phần còn lại của các số Fibonacci bắt đầu từ số thứ ba (chỉ số, n = 2) được xác định trong một vòng lặp và đặt vào vị trí của chúng trong mảng. Vì vậy, hàm phải trả về giá trị void. Câu lệnh chính trong vòng lặp bổ sung thêm hai số trước đó.
Biến chỉ số, i, đã được sử dụng thay vì n, với mục đích rõ ràng.
Một lớp Java Main phù hợp (với phương thức Java main) là:
công cộng lớp Chính {công cộng tĩnh vô hiệu chính ( Sợi dây args [ ] ) {
int m = 12 ;
int [ ] arr = Mới int [ m ] ;
Fibonacci obj = Mới Fibonacci ( ) ;
phản đối. fibonacci ( arr ) ;
vì ( int tôi = 0 ; tôi < m ; tôi ++ )
Hệ thống . ngoài . in ( arr [ tôi ] + '' ) ;
Hệ thống . ngoài . println ( ) ;
}
}
Sau khi các số được tạo ra bởi phương thức fibonacci (), phương thức chính của Java sẽ đọc chúng ra.
Sản xuất một số Fibonacci trong thời gian không đổi
Có một công thức toán học có thể được sử dụng để tạo ra số Fibonacci, khi cho chỉ số dựa trên số 0 tương ứng, n. Công thức là:
trong đó n là chỉ số dựa trên 0 và Fib N là số Fibonacci tương ứng. Lưu ý rằng ở vế phải của phương trình, nó không phải là căn bậc hai của 5 được nâng lên lũy thừa n; nó là biểu thức trong ngoặc đơn được nâng lên lũy thừa n. Có hai trong số các biểu hiện như vậy.
Nếu n là 0, Fib N sẽ là 0. Nếu n là 1, Fib N sẽ là 1. Nếu n là 2, Fib N sẽ là 1. Nếu n là 3, Fib N sẽ là 2. Nếu n là 4, Fib N sẽ là 3 - và như vậy. Người đọc có thể xác minh công thức này bằng toán học, bằng cách thay thế các giá trị khác nhau cho n và đánh giá.
Khi được mã hóa, công thức này sẽ chỉ tạo ra một số Fibonacci cho n. Nếu yêu cầu nhiều hơn một số Fibonacci, mã cho công thức phải được gọi một lần cho mỗi chỉ mục tương ứng khác nhau.
Trong Java, phương pháp để tạo ra chỉ một số Fibonacci là:
nhập khẩu java.lang. * ;lớp Sợi {
kép fibNo ( int N ) {
kép FibN = ( môn Toán . pow ( ( 1 + môn Toán . sqrt ( 5 ) ) / hai , N ) - môn Toán . pow ( ( 1 - môn Toán . sqrt ( 5 ) ) / hai , N ) ) / môn Toán . sqrt ( 5 ) ;
trở về FibN ;
}
}
Gói java.lang. * Phải được nhập vào đầu chương trình. Điều này là do gói có lớp Math, có các phương thức lũy thừa (pow) và căn bậc hai (sqrt). Phương thức Java tùy chỉnh ở đây thực hiện trực tiếp công thức toán học.
Độ phức tạp về thời gian cho chức năng này là O (1), chế ngự không đổi của một hoạt động chính. Một lớp Java Main phù hợp, với phương thức Java main cho phương thức trên là:
công cộng lớp Chính {công cộng tĩnh vô hiệu chính ( Sợi dây args [ ] ) {
int N = mười một ;
Sợi obj = Mới Sợi ( ) ;
kép bên phải = phản đối. fibNo ( N ) ;
Hệ thống . ngoài . println ( bên phải ) ;
}
}
Chỉ số n = 11 được gửi đi và số Fibonacci, 89 được trả về. Đầu ra là:
89.00000000000003Các chữ số thập phân không cần thiết có thể được loại bỏ, nhưng đó là một cuộc thảo luận cho một số thời điểm khác.
Sự kết luận
Số Fibonacci là một dãy số nguyên cụ thể. Để có được số hiện tại, hãy thêm hai số tương ứng ngay trước đó. Hai số Fibonacci đầu tiên, 0 theo sau là 1, được khai báo trước, cho toàn bộ dãy số. Phần còn lại của các số Fibonacci được tạo ra từ đó.
Để tạo số Fibonacci từ chỉ số 2, tương ứng với chỉ số n-1, hãy sử dụng vòng lặp for với câu lệnh chính:
int currNo = P [ tôi - 1 ] + P [ tôi - hai ] ;trong đó currNo là số Fibonacci hiện tại và P là mảng lưu trữ n số.
Để chỉ tạo ra một số Fibonacci từ bất kỳ chỉ số n dựa trên 0 nào, hãy sử dụng công thức toán học:
