30/09/2018, 21:41
Về dãy Fibonacci. Cái này này theo mình thì không dễ
Đề bài: Viết chương trình nhập vào 2 số n và m. Hãy tính F(n)%m. Với F(n) là số Fibinacci thứ n.
Áp dụng chương trình của bạn để tính với trường hợp n = 999999999 và m = 100.
(Mình thi rồi nha, nên không có vụ hỏi bài tập ở đây, chỉ là để thảo luận đối với đề bài mang tính “giải trí” cao này thôi)
Một số ý kiến:
- Dãy Fibonacci với phần tử thứ 100 là khổng lồ rồi.
- Việc áp dụng BigNum là khá phức tạp và mất thời gian.
- Thay vì tính F(n) thì tính một vài số cuối của F(n) rồi chia lấy dư cho m có cho kết quả chính xác?
Hãy chia sẻ ý tưởng và code của bạn để mọi người cùng test. Hoặc có thể chia sẻ kết quả nếu bạn ngại chia sẻ code.
Bài liên quan
Bài này nếu là mình thì sẽ dùng ma trận . Độ phức tạp ~~ log(n)
p/s: bài này hình như có hỏi ở đây hồi trước rồi thì phải
lưu dãy fibo[1] = fibo[2] = 1 , fibo(n) = (fibo(n-1)+fibo(n-2)) mod m
xài công thức ma trận
Fi+j = Fi+1Fj+1 - Fi-1Fj-1
Fi+j+1 = Fi+1Fj+1 + FiFj
lấy của Fn % m để tính ra F2n % m cho kết quả chính xác:
giả sử
a = q1m + r1
b = q2m + r2
suy ra
a (mod m) = r1 (mod m)
b (mod m) = r2 (mod m)
suy ra
(ab) (mod m) = (r1r2) (mod m)
(a+b) (mod m) = (r1+r2) (mod m)
(a-b) (mod m) = (r1-r2+m) (mod m)
với phép trừ thì có thể r1-r2 cho số âm, nên ta chỉ cần cộng thêm m là được.
Với ví dụ n = 100, ta biểu diễn 100 dưới dạng số nhị phân:
100 = (1100100)2
như vậy F100 = F64+32+4
với bộ đôi F1 và F2 khởi điểm, tính:
F2 và F3
F4 và F5
F8 và F9
F16 và F17
F32 và F33
F64 và F65
(bằng công thức ma trận trên với i = j)
rồi kết hợp F64 với F32 và F4 cho ra F100. Nhớ lấy mod m hết.