読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.53 悪の漸化式

問題はこちら
No.53 悪の漸化式 - yukicoder

三項間漸化式なので高校数学を思い出して一般項を求める

特性方程式
4λ^2=19λ-12
なので
λ=3,3/4
一般項は a[n]=p*3^n+q*(3/4)^n の形になる
n=0,1を代入してp=0,q=4
つまり一般項はa[n]=4*(3/4)^n

これはn→∞で0に収束するので、漸化式を愚直に計算していくとn十分大で誤差死する
(真値が正確に保存されなくなった瞬間にpがずれ、最終的にはO(3^n)で増加or減少していく)

int main(){
	int n;
	scanf("%d",n);
	printf("%.9f",pow(0.75,n)*4);
	return 0;
}

圧縮

n;main(){n=!printf("%.9f",4*pow(.75,atoi(gets(&n))));}

54B