Mình xin chia sẻ lời giải cho bài này như sau:

Gọi \(u_n\) là mực nước biển ngày thứ \(n\). Khi đó, theo đề ta có công thức sau: \(u_n=\frac{u_{n-1}+u_{n+1}}{2}\iff u_{n+1}=2u_n-u_{n-1}\rightarrow (1)\) với \(u_1=a,u_2=b\)

Dưới đây mình sẽ trình bày 3 cách có thể tiếp cận bài này như sau:

Cách 1: Biến đổi thông thường:

Từ $(1)\implies u_{n+1}-u_{n}=u_n-u_{n-1}=...=u_2-u_1 $
\(\implies u_{n+1}-u_n=u_2-u_1\iff u_{n+1}=u_{n}+(b-a)=u_{n-1}+2*(b-a)=...=u_1+n*(b-a)=a+n*(b-a)\)

Từ đây ta suy ra được: \(u_{n}=a+(n-1) * (b-a)\). Đến đây ta chỉ cần thế số \(a,b,n\) là bài toán đã được giải quyết.

Độ phức tạp là \(O(1)\).

Cách 2: Sử dụng phương trình đặc trưng:

Ta xét phương trình đặc trưng sau: \(\lambda^2 = 2\lambda -1\iff \lambda^2-2\lambda+1=0\iff (\lambda-1)^2=0\iff \lambda=1\)

Do đó: Phương trình \((1)\) sẽ có dạng như sau: \(u_n = (P*n+Q)*1^{n}=P*n+Q\rightarrow (2)\) với \(P,Q\) là một số nào đó, và bây giờ ta cần phải đi tìm.

Đơn giản, ta chỉ lần lượt thay \(u_1=a,u_2=b\) để tìm \(P,Q\). Và ta làm như sau:

Từ \((2)\) ta suy ra được:

\(\left\{\begin{matrix} u_1 = P+Q\rightarrow (3) \\ u_2 = 2*P+Q\rightarrow (4) \end{matrix}\right.\)

Lấy \((4)-(3)\) vế theo vế ta được: \(P=u_2-u_1=b-a\). Và từ đây ta dễ dàng suy ra được: \(Q=u_1-P=a-(b-a)=b\)

Vậy \(u_n=(b-a)*n+b =a+ (n-1)*(b-a)\). Và đến đây công việc còn lại chỉ là thế số.

Cách 3: Sử dụng nhân ma trận.

Ý tưởng của nhân ma trận như sau:

Từ phương trình \((1)\) đã cho, ta đưa về một phương trình liên quan đến ma trận có dạng như sau:

\(\begin{pmatrix} a_{n-1} & a_{n} \end{pmatrix} . \begin{pmatrix} u_1 & u_2 \\ u_3 & u_4 \end{pmatrix} = \begin{pmatrix} a_{n} & a_{n+1} \end{pmatrix}\) , trong đó \(u_1,u_2,u_3,u_4\) là các số nào đó .

Vậy việc đưa về phương trình ma trận trên có ý nghĩa gì ? Để hiểu rõ hơn, các bạn cùng theo dõi nhé, vì kĩ thuật này rất hay được sử dụng đối với những dãy truy hồi tuyến tính như vầy !

Giả sử tồn tại \(u_1,u_2,u_3,u_4\) thoả mãn: \(\begin{pmatrix} a_{n-1} & a_{n} \end{pmatrix} . \begin{pmatrix} u_1 & u_2 \\ u_3 & u_4 \end{pmatrix} = \begin{pmatrix} a_{n} & a_{n+1} \end{pmatrix}\rightarrow (I)\)

Và nhiệm vụ của ta là đi tìm các số \(u_1,u_2,u_3,u_4\). Chúng được thực hiện như sau:

Gọi \(L(I),R(I)\) lần lượt là về trái và vế phải của phương trình \((I)\).

Ta có: \(L(I) = \begin{pmatrix} a_{n-1} & a_{n} \end{pmatrix} . \begin{pmatrix} u_1 & u_2 \\ u_3 & u_4 \end{pmatrix} = \begin{pmatrix} a_{n-1}u_1+a_nu_3 & a_{n-1}u_3+a_{n}u_4 \end{pmatrix}=R(I)=\begin{pmatrix} a_{n} & a_{n+1} \end{pmatrix}\)

Từ đây ta suy ra được:

\(\left\{\begin{matrix} a_{n-1}u_1+a_nu_3=a_n\rightarrow (5) \\ a_{n-1}u_2+a_{n}u_4=a_{n+1}\rightarrow (6) \end{matrix}\right.\)

Từ \((1),(5),(6)\), sử dụng đồng nhất thức ta suy ra được:\((u_1,u_2,u_3,u_4)=(0,-1,1,2)\)

hay \(\begin{pmatrix} u_1 & u_2 \\ u_3 & u_4 \end{pmatrix}=\begin{pmatrix} 0 & -1 \\ 1 & 2 \end{pmatrix} \rightarrow M\) (và ta gán ma trận này là ma trận \(M\))

Gọi \(p_n=\begin{pmatrix} a_{n} & a_{n+1} \end{pmatrix}\)

Khi đó \((I)\iff p_n=p_{n-1}*M = p_{n-2}*M^2=...=p_1*M^{n-1}\), trong đó \(p_1=\begin{pmatrix} a & b \end{pmatrix}\)

Và nhiệm vụ của ta đơn giản là nhân ma trận. Để tính được \(M^n\), ta tiếp tục sử dụng luỹ thừa nhị phân.

Độ phức tạp của bài này là : \(O(log(n))\)

Vì cách \(1\), cách \(2\) khá đơn giản nền mình chỉ trình bày code của bài \(3\) tại đây

Như vậy là mình đã trình bày xong 3 cách để giải quyết bài toán này !

Ps: Nếu có gì thắc mắc, các bạn cứ cmt nhé !