kmjp's blog

競技プログラミング参加記です

yukicoder : No.53 悪の漸化式

若干悪意のある問題。
http://yukicoder.me/problems/80

問題

以下の漸化式で与えられる数列がある。

  •  A_0 = 4
  •  A_1 = 3
  •  A_k = 19A_{k-1} - 12A_{k-2} (k \ge 2)

Nが与えられるので、 A_Nを求めよ。

解法

特性方程式を立てて漸化式をまじめに解くか、最初の数項を実際に求めてみると A_N = (\frac{3}{4})^Nであることがわかるのでこれを答えればよい。
漸化式に沿ってそのまま計算すると誤差死するので注意。

double A[1000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>j;
	A[0]=4;
	A[1]=3;
	for(i=2;i<=100;i++) A[i]=A[i-1]*0.75;
	_P("%.12lf\n",A[j]);
}

まとめ

悪シリーズで一番悪意があるかもしれない。