問題はこちら
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