POJ 1538 - Extrapolation Using a Difference Table

http://poj.org/problem?id=1538

概要

数列 \(a_n\) が与えられる。

長さ \(n\) の数列に対して、隣接する項の差によって新たに長さ \(n-1\) の数列を作ることができる。 この操作を長さ1の数列になるまで繰り返すと、問題文の上の図のような差分表ができる。 この \(n-1\) 番目の長さ1の数列の値を \(c\) とする。

ここから数列 \(a_n\) に新たに \(a_{n+1}\) を追加することを考える。 このとき、追加した後の差分表の \(n-1\) 番目の数列の要素が常に \(c\) になるように \(a_{n+1}\) の値を決めなければならない。

このようにして \(k\) 個要素を追加した後の \(a_{n+k}\) の値を答える。

制約

• \(1 \le n \le 10\)
• \(k\) についての制約はなく、\(k\) 個追加した後の完全な差分表を作ることはできないかもしれない

解法

差分表の各列の一番下の要素だけあれば「追加」の操作を行えるので、 最初に完全な差分表を作った後は \(k\) 回追加すればいい。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int N;
 7   while (cin >> N && N != 0) {
 8     int a[10][10];
 9     for (int i = 0; i < N; i++) {
10       cin >> a[N-1][i];
11     }
12     int K;
13     cin >> K;
14 
15     for (int i = N-2; i >= 0; i--) {
16       for (int j = 0; j <= i; j++) {
17         a[i][j] = a[i+1][j+1] - a[i+1][j];
18       }
19     }
20 
21     for (int i = 0; i < K; i++) {
22       for (int j = 0; j < N-1; j++) {
23         a[j+1][j+1] += a[j][j];
24       }
25     }
26     cout << "Term " << N+K << " of the sequence is " << a[N-1][N-1] << endl;
27   }
28   return 0;
29 }