Cần giúp đỡ bài tập khó về mảng 2 chiều
bạn đang gặp vấn đề gì ở bài toán này?
cách sử dụng mảng?
1 Like
Bài này có thể không cần dùng mảng.
Có gợi ý là đệ quy. Bài cũng tương tự cách tính dãy Fibonacci với đệ quy thôi.
Dãy số ngoài bìa chính là Fibonacci luôn mà.
Nhanh thì có công thức tính giá trị của số Fibonacci tại 1 vị trí.
4 Likes
-
E code kiểu đệ quy như công thức of đề và chạy >1s với x=13,y=13 . e thay x=100,y=100 thì chương trình không chạy nổi. Thuật toán hay hướng đi nào cải thiện điều đó ạ?
-
“lấy đồng dư với 10^9 +7” ?
=> là %(10^9+7) phải không a??
giả sử x=100000,y=100000 thì runtime liệu < 1s ?
với thể loại bài như thế này, bạn nên cho x = 100 và y = 100 rồi xem thử quy luật
mà cũng khỏi cần code, dùng excel show cái bảng ra thôi 
4 Likes
Đến 10^6 thì cũng khó để nhỏ hơn 1 giây, nếu lặp hoặc đệ quy.
Thế mới có câu cuối:
Công thức này có liên quan đến giá trị tỉ lệ vàng là số phi (Φφ).
3 Likes
Đưa code của bạn lên đi, để biết bạn đệ quy kiểu gì là với (x,y) = (13,13) mà đã quá hơn 1 giây.
4 Likes
int main()
{
int x, y;
cin >> x >> y;
cout << infinite2DArray(x, y)<<endl;
return 0;
}
xin chỉ giáo với ,cảm ơn bạn nhiều !
Đệ quy cái này là treo máy đấy.
Để cho đơn giản, thời gian tính Fibo(n) là T(n) vậy T(n) = T(n-1) + T(n-2) tức là xêm xêm số Fibo. Fibo tăng theo hàm mũ, vậy thời gian cũng tăng theo hàm mũ (!)
F(6) = 8 = \sqrt{2^6}
F(7) = 13 > \sqrt{2^7} = \sqrt{128}
F(n) = F(n-1) + F(n-2) \geq \sqrt{2^{n-2}} \cdot (1 + \sqrt{2}) \geq \sqrt{2^{n-2}} \cdot 2 = \sqrt{2^n}
4 Likes
vậy có cách nào khác giải bài này hk ạ?
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?