yukicoder No.53 - 悪の漸化式(writer担当)

Source

ニコニコミュニティ
問題文

問題概要

  \(A_0 = 4,\)
  \(A_1 = 3,\)
  \(4 A_k = 19 A_{k-1} - 12 A_{k-2}, \;\; k \geq 2\)
で漸化式で定義される数列 \(\{A_k\}_{k=0}^\infty\) の第 \(N\) 項 \(A_N\) を求める問題.

解法

漸化式を解くと,特性方程式は
$\quad \displaystyle 4 \lambda^2 - 19 \lambda + 12 = 4\left( \lambda - \frac{3}{4} \right) \left( \lambda - 4\right) = 0$
なので,一般解は,任意定数を $\alpha, \beta$ として,
$\quad \displaystyle A_k = \alpha \left(\frac{3}{4}\right)^k + \beta 4^k$
となる.ここで,初項 $A_0, A_1$ を代入することで,$\alpha = 4, \beta = 0$ であることがわかり,答えは
$\quad \displaystyle A_k = 4 \left(\frac{3}{4}\right)^k$
なので,これを適当な方法で計算すれば良い.
漸化式をそのまま用いると,途中で丸め誤差が入り,$\beta 4^k$ の項が増大し,計算が合わなくなる.(倍精度浮動小数点数を用いた場合)
多倍長精度などを用いれば漸化式をそのまま用いて計算することも可能.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

Current time: 2017年11月18日11時44分19秒
Last modified: 2014年11月06日13時04分44秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: