Một dãy số bắt đầu bằng số 0, sau đó là số 1 và các số tiếp theo
Một dãy số bắt đầu bằng số 0, sau đó là số 1 và các số tiếp theo đều là tổng của hai số trước đó, được gọi là dãy Fibonacci. Đây là dãy được tìm thấy từ những năm 1200 nhưng lại được đặt theo tên một nhà toán học người Ý, Fibonacci. Hãy phát biểu bài toán tìm số Fibonacci thứ n và tổng n số Fibonacci đầu tiên.
Giải SBT Tin học 9 Kết nối tri thức Bài 15: Bài toán tin học
Câu 15.4 trang 61 SBT Tin học 9: Một dãy số bắt đầu bằng số 0, sau đó là số 1 và các số tiếp theo đều là tổng của hai số trước đó, được gọi là dãy Fibonacci. Đây là dãy được tìm thấy từ những năm 1200 nhưng lại được đặt theo tên một nhà toán học người Ý, Fibonacci. Hãy phát biểu bài toán tìm số Fibonacci thứ n và tổng n số Fibonacci đầu tiên.
a) Hãy phát biểu bài toán tìm số Fibonacci thứ n và tổng n số Fibonacci đầu tiên.
b) Trình bày thuật toán tìm số Fibonacci thứ n và tổng n số Fibonacci đầu tiên.
Lời giải:
Đầu vào: số nguyên dương nnn.
Đầu ra: số Fibonacci thứ nnn và tổng của n số Fibonacci đầu tiên.
Ví dụ:
|
Đầu vào |
Đầu ra |
Giải thích |
|
3 |
2, 4 |
Những số Fibonacci đầu tiên là 0, 1, 1, 2, 3,... |
|
5 |
5, 12 |
Những số Fibonacci đầu tiên là 0, 1, 1, 2, 3,... |
b) Thuật toán tính số Fibonacci thứ n và tổng n số Fibonacci đầu tiên có thể được mô tả theo các bước như sau:
Nhập n
Nếu n = 1 thì
f 0; s 0
còn không thì
Nếu n = 2 thì
f 1; s 1
còn không thì
a 0; b 1; s 1
Lặp (n-2) bước
f a + b; s s + f; a b; b f;
Xuất f, s
Lời giải sách bài tập Tin học 9 Bài 15: Bài toán tin học hay khác: