Tính tổng dãy Fibonacci

#1

Viết chương trình tìm số Fibonaci thứ n.( không dùng đệ quy)
Dãy số Fibinaci gồm những số: 1, 1, 2, 3, 5, 8, 13, 21 … bắt đầu từ hai số 1 và 1,
tiếp sau đó các số Fibinaci sau bằng tổng của 2 số Fibinaci trước nó.
Dãy Fibinaci có thể định nghĩa như sau:
Fibinaci (1) = 1; Fibinaci (2) = 1;
Fibinaci (n) = Fibinaci (n-1) + Fibinaci (n-2) (n>2).
Viết chương trình tính tổng n số Fibonaci đầu tiên.
Tks all

#2

Không đệ quy đấy. Tổng 2 số trước bằng số sau.

2 Likes
#3

à mình quên copy các Viết chương trình tính tổng n số Fibonaci đầu tiên. tính tổng n số fib đầu tiên là sao nhỉ? tks nhé :3

#4

Thiếu F(0) = 0 đấy. Số này không bỏ được.

Viết công thức :smiley: (lưu ý là không phải tính ntn đâu, ghi vậy thôi)
S(n) = F(1) + F(2) + ... + F(n)

Cách 1

Xét:
F(3) = F(1) + F(2)
F(4) = F(1) + 2F(2)
F(5) = 2F(1) + 3F(2)
…
F(n) = F(n-2)F(1) + F(n-1)F(2).
thay F(1) và F(2): S(n) - 2 = S(n-2) + S(n-1) - 1 <=> S(n) = S(n-2) + S(n-1) + 1.
Vậy làm thế quái nào cho nó thuần nhất đây :smiley: Ta thêm 1 lượng v vào, vậy v = 2v + 1 <=> v = -1.
Đặt S(n) = s(n) - 1. Pt trở thành s(n) - 1 = s(n-1) + s(n-2) + (-1 -1 + 1)
<=> s(n) = s(n-1) + s(n-2) với s(1) = 2 và s(2) = 3, giống Fibo cơ bản. Vậy S(n) = F(n+2) - 1.

Cách 2

Tất nhiên viết “một dọc” sai phân sẽ nhanh hơn nhiều rồi :slight_smile:

do delta_F(i) = F(i+1) - F(i) = F(i-1) nên
sigma(i=1..n) delta_F(i+2) = F(n+2) - F(2) = F(n+2) - 1

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?