Yukicoder053 悪の漸化式

問題概要

以下の漸化式で定義される無限数級 $A[k]$ の第 $N$ 項 $A[N]$ を求めるプログラムを書け。
$A[0]=4,$
$A[1]=3,$
$4A[k]=19A[k-1]−12A[k−2],(k≥2)$

$N\leqq10^2$

yukicoder053

解法

†計算の際に起きる誤差死を意図的に引き起こす†
という問題。普通に計算するとダメになる。
高校で習った算数をすると二項間漸化式を求めることができて、
$A_k = 4*( \frac{3}{4})^{k}$

計算量:$O(1)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    
    LL N;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        //vector<long double> a(N+1, 0);
        //a[0] = 4;
        //a[1] = 3;
        //FOR(i, 2, N + 1) {
        // a[i] = (19*a[i-1] -12*a[i-2]) / 4.0;
        //}
        //long double ans = a[N];
        //cout <<fixed<<setprecision(100)<< ans << "\n";
    
        cout << fixed << setprecision(20) << 4.0*pow(3.0 / 4.0, N) << endl;
    
        return 0;
    }