Weird Fib"onanci

[m2mpro]

Các bạn thử giải bài này hén :)

Cho biết định nghĩ của xâu Fib"onanci như sau : F[i] = F[i-1] + F[i-2].
Bây giờ, ta cho trước hai số F[m] và F[n], các bạn hãy tính F[k].(m <> n <> k)

Giới hạn : trị tuyệt đối m,n,k <= 10; trị tuyệt đối F[i] <= 10^5.

P/S: phải viết Fib"onanci chứ ko sẽ biến thành ****nanci

[quangtq]

Tính luôn F[k] từ đầu. Haha.
Nhưng thế lại không đúng yêu cầu mặc dù k<=10 nên tính vậy cũng được

[m2mpro]

Đọc kĩ lại đề nhé em, chưa chắc cho m với n liền nhau đâu mà tính thẳng đc F[k]

[quangtq]

Em tính từ F[1] thì ko là tính thẳng à?
:D

[m2mpro]

Anh đã bảo dọc kĩ đề đi rồi nói.

Đề chỉ cho 2 cái F[m] và F[n], ở đâu cho em ra mấy cái giá trị khác mà tính

Ví dụ này
m = 1
F[1] = 2
n = 4
F[4] = 1
k = 5

Ta có thể nghĩ đến bảng sau
i = 1 2 3 4 5
F[i] = 2 1 3 4 7

=> F[k] = F[5] = 7

Nhớ đọc đề trc khi nói, đừng có quơ quơ qua rồi reply cho vui :)

[quangtq]

Sorry. Em tưởng F i b o naci thường là F[1]=F[2]=1.
Chẳng nhẽ vét chăng

[linhhahaduc]

đệ quy có nhớ:D .
hàm tinh(k :longint) là số ****naci thứ k nhá ;
tinh(k) := tinh(k-1) + tinh(k-2);
hàm sẽ dừng khi mà có tồn tại F[k] trc đó rùi :D
Để tránh TH k < n hoặc < m thì cứ tính hẳn từ số ****naci 1 đến 10

[=========> Bổ sung bài viết <=========]

P/s : ặc ko hiểu cái f i b o nó có cái nghĩa gì mà lại bị **** nhỉ :(( . Mình trong sáng mà :P

[quangtq]

Thứ nhất: Ko đọc những gì mình + anh m2m nói à?
Thứ hai: Nếu chưa đọc thì là đây ko phải f i b o naci thường (F[1]=F[2]=1) mà là chỉ có dạng F[i]+F[i+1]=F[i+2] thôi. Không cho trước F[1] và F[2] mà chỉ cho trước F[m] và F[n]. Chứ ko thì quá dễ.

[khonggiannet]

F[k] = a*F[m] + b*F[n] với a, b là 2 tham số cần tìm

Đa thức đặc trưng theo công thức truy hồi trên là x^k - a*x^m - b*x^n sẽ chia hết cho đa thức đặc trưng của dãy x^2 - x - 1 nên nếu gọi x1, x2 là 2 nghiệm của x^2 - x - 1 thì x1, x2 cũng là nghiệm của x^k - a*x^m - b*x^n

Vì vậy ta có:
a*x1^m + b*x1^n = x1^k
a*x2^m + b*x2^n = x2^k

Giải hệ 2 pt trên tìm được a và b. Sau khi có a và b thì F[k] = a*F[m] + b*F[n] là giá trị cần tìm.

[m2mpro]

Đúng rồi, nhưng vẫn còn 1 thuật toán khác ( 1 thuật toán đúng chính nghĩa bên Tin ), các bạn thử suy nghĩ xem nào

[linhhahaduc]

Thứ nhất: Ko đọc những gì mình + anh m2m nói à?
Thứ hai: Nếu chưa đọc thì là đây ko phải f i b o naci thường (F[1]=F[2]=1) mà là chỉ có dạng F[i]+F[i+1]=F[i+2] thôi. Không cho trước F[1] và F[2] mà chỉ cho trước F[m] và F[n]. Chứ ko thì quá dễ.

Bạn mới là người nên đọc lại , thử nghĩ kĩ lại xem mình có nói sai ko?

[quangtq]

1. Em ko hiểu chỗ nào thì bác cứ nói. Em xin lỗi.
2. Đệ quy kiểu gì vậy bác? Nếu m và n ko liền nhau thì sao ra được F[k]

[lehang_gb1]

Anh đã bảo dọc kĩ đề đi rồi nói.

Đề chỉ cho 2 cái F[m] và F[n], ở đâu cho em ra mấy cái giá trị khác mà tính

Ví dụ này
m = 1
F[1] = 2
n = 4
F[4] = 1
k = 5

Ta có thể nghĩ đến bảng sau
i = 1 2 3 4 5
F[i] = 2 1 3 4 7

=> F[k] = F[5] = 7

Nhớ đọc đề trc khi nói, đừng có quơ quơ qua rồi reply cho vui :)

F4=1 cơ mà như bạn viết thế kia thì F2=1 ah nhầm rồi.
Bài toán bạn cho ko phải **** thông thường có nghĩa là F1 và F2 ban đầu ko phải lúc nào cũng bằng 1

[=========> Bổ sung bài viết <=========]

Fi có thể là số âm ah


Ví dụ F2=5
F5=7
i 1 2 3 4 5
Fi -4 5 1 6 7

[m2mpro]

Uhm, đúng là ví dụ có sai.

Thật ra cách của linhhahaduc ko đúng đâu.

Xét thử nhé k = 4, m = 1, n=3

F[4]=F[3]+F[2]
F[3]=F[2]+F[1]
F[2]=F[1]+F[0]

Bạn chưa biết F[0] => coi như vẫn chưa biết gì cả, ko thể nào đệ quy đc :)

[khonggiannet]

Một cách làm khác không phải thông qua 2 nghiệm căn thức của pt x^2 - x - 1 (và vì vậy có ý nghĩa hơn trong việc tính toán thực tế):

Bằng qui nạp theo i, có ngay:
F[i+1] = f[i]*F[1] + f[i-1]*F[0]
trong đó f[i] là dãy Fi-bonacci thông thường, nghĩa là f[0]=f[1]=1

Dãy f[i] này tính được dễ dàng rồi nhé. Giới hạn <10 chắc để giúp dễ dàng tính toán.

Thay i lần lượt bằng m-1, n-1, k-1 được 3 phương trình. Từ 2 pt đầu tìm được F[0], F[1], thay vào pt thứ 3 ra ngay F[k]

[quangtq]

Pro quá. Anh khonggiannet lớp mấy mà giỏi toán vậy ta?

[khonggiannet]

Anh già rồi. Lớp 18 lận lol

[quangtq]

:D
Ông anh 24 hả? Thảo nào giỏi thế

[hang_vt]

cho mình hỏi tí :theo như sgk Đại 11 thì F1 = F2= 1 mà . Quang cũng có ý đúng .

[m2mpro]

Đây là Weird F i b o nanci chứ ko phải F i b o nanci bình thường, vì vậy yêu cầu mọi người đọc kĩ đề và không nên nói những cái không thuộc về đề :)

[lehang_gb1]

có truowngf hợp không tìm được dãy chứ
Ví dụ mình nhâpk F2=3
F5=6
thì không thể nàog tìm được F3,F4


i 1 2 3 4 5
Fi 3 ? ? 6

Các bạn thử tìm xem. Mình nhẩm mãi không ra

[m2mpro]

Đúng là vẫn có th ko thể tìm ra :D

[khonggiannet]

có truowngf hợp không tìm được dãy chứ
Ví dụ mình nhâpk F2=3
F5=6
thì không thể nàog tìm được F3,F4


i 1 2 3 4 5
Fi 3 ? ? 6

Các bạn thử tìm xem. Mình nhẩm mãi không ra



i 1 2 3 4 5
Fi -3/2 3 3/2 9/2 6


Trường hợp nào ko tính được?

[lehang_gb1]

uh đúng rồi mình cứ nghĩa Fi phải là số nguyên cơ. Fi là số thực. Thế thì cũng khó tìm nhỉ. Thế trong trường hợp Fi là phân số vô tỉ thì khó tính và đưa ra Fi nhỉ ví dụ 13/7 12/9 ....
ĐỂ viết được chương trình đưa ra Fi dạng phân số thì phải dùng mảng 2 chiều hay bản ghi cơ à
Các bạn viết chương trình đi để mọi người cùng tham khảo