UVa 326 Extrapolation Using a Difference Table

题目描述外推序列的一种古老技术是基于差分表的使用。给定一个包含444个值的序列例如3,6,10,153, 6, 10, 153,6,10,15其差分表如下所示3 3 1 0 6 4 1 10 5 15第一列是原始序列值第二列是第一阶差分相邻项的差第三列是第二阶差分最后一列是第n−1n-1n−1阶差分nnn为序列长度对于n4n4n4的序列差分表有444列最后一列只有一个值表示第333阶差分。为了外推我们假设第n−1n-1n−1阶差分是常数。基于这个假设可以反向计算先计算第n−1n-1n−1阶差分的下一个值与之前相同然后计算第n−2n-2n−2阶差分的下一个值依此类推直到计算出序列的下一个值输入格式输入包含多个外推请求。每个请求的第一行是一个整数nnn0n≤100 n \leq 100n≤10指定要扩展的序列长度。当n0n 0n0时程序终止。如果nnn非零接下来是nnn个整数表示给定的序列元素。每个外推请求的最后一项是kkkk≥1k \geq 1k≥1表示要执行的外推次数。要求计算原序列经过kkk次外推后的第nknknk项值。输出格式对于每个请求输出一行格式如样例所示。样例输入4 3 6 10 15 1 4 3 6 10 15 2 3 2 4 6 20 6 3 9 12 5 18 -4 10 0样例输出Term 5 of the sequence is 21 Term 6 of the sequence is 28 Term 23 of the sequence is 46 Term 16 of the sequence is -319268题目分析问题的本质这是一个差分表外推问题。给定一个长度为nnn的序列通过构造差分表假设最高阶差分为常数然后反向计算外推值。差分表的数学原理设原序列为a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​。定义一阶差分Δaiai1−ai\Delta a_i a_{i1} - a_iΔai​ai1​−ai​二阶差分Δ2aiΔai1−Δai\Delta^2 a_i \Delta a_{i1} - \Delta a_iΔ2ai​Δai1​−Δai​…\dots…n−1n-1n−1阶差分Δn−1ai\Delta^{n-1} a_iΔn−1ai​只有一个值在差分表中我们通常用压缩存储的方式只保留每个差分序列中可用于外推的部分。外推算法假设Δn−1ai\Delta^{n-1} a_iΔn−1ai​为常数ccc。那么Δn−2an−1Δn−2an−2c\Delta^{n-2} a_{n-1} \Delta^{n-2} a_{n-2} cΔn−2an−1​Δn−2an−2​c依此类推可以逐步计算出Δan\Delta a_nΔan​然后计算出an1a_{n1}an1​重复kkk次即可得到anka_{nk}ank​。参考代码// Extraploation Using a Difference Table// UVa ID: 326// Verdict: Accepted// Submission Date: 2016-06-28// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){intn;while(cinn,n){vectorlonglongintnumber;// 读取原序列的 n 个值for(inti1;in;i){intvalue;cinvalue;number.push_back(value);}// 构建差分表的压缩形式// 经过此循环后// number[0] 存储最高阶差分第 n-1 阶差分// number[1] 存储第 n-2 阶差分的第一个值// ...// number[n-1] 存储原序列的第一个值for(intin-1;i1;i--)for(intj0;ji-1;j)number[j]number[j1]-number[j];intk;cink;// 进行 k 次外推// 每次外推从最高阶差分开始累加计算出新的序列值for(inti1;ik;i)for(intj1;jn-1;j)number[j]number[j-1];// 输出结果number.back() 即为第 nk 项的值coutTerm (nk) of the sequence is number.back()endl;}return0;}