Một dãy số bắt đầu bằng số 0, sau đó là số 1 và các số tiếp theo

Trang trước Trang sau

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 $\leftarrow$ 0; s $\leftarrow$ 0

còn không thì

Nếu n = 2 thì

f $\leftarrow$ 1; s $\leftarrow$ 1

còn không thì

a $\leftarrow$ 0; b $\leftarrow$ 1; s $\leftarrow$ 1

Lặp (n-2) bước

f $\leftarrow$ a + b; s $\leftarrow$ s + f; a $\leftarrow$ b; b $\leftarrow$ 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:

Xem thêm các bài giải sách bài tập Tin học lớp 9 Kết nối tri thức hay, chi tiết khác:

Xem thêm các tài liệu học tốt lớp 9 hay khác:

Trang trước Trang sau

Giải bài tập lớp 9 Kết nối tri thức khác