保存されている過去のバージョンの一覧

2014年11月06日13時04分44秒
2014年10月31日00時27分31秒

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: 2024年03月29日09時34分54秒
Last modified: 2014年11月06日13時04分44秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: