题目:
一个实数序列:ai = (ai-1–ai+1)/2 + d, (1<i<N) (N<60)。键盘输入N, d, a1, an, m,求am。
分析:
一看即知:这是一个数学味道极浓的算法题,首先需要一番推理分析才能编程,否则会无处下手。
1)首先,我们对数列的递推式进行一番变换:
ai+1 = ai-1 + 2d – 2 ai
ai = ai-2 - 2 ai-1 + 2d ①
a4 = a2 - 2 a3 + 2d = 5a2 - 2 a1 - 2d
2)数列中各元素间没有乘除运算,所以这是一个线性递推的数列,因此公式①中各项的系数一定存在一个线性规律,而且是各项系数本身的规律,与其它系数没有关系,因此如果能够找到这些规律,那么这道题也就应刃而解了。
递推如下:
a3 = a1 - 2 a2 + 2d
a4 = a2 - 2 a3 + 2d = 5a2 - 2 a1 - 2d
题目中a1已知,未知的是a2,
所以可以令:a2 = X, 各项系数为Pi, Qi, Ri, 则:
Ai -1= Pi-1*X+Qi-1*a1+Ri-1*d,
Ai = Pi*X+Qi*a1+Ri*d,
Ai+1 = Pi+1*X+Qi+1*a1+Ri+1*d,
再由公式①,可以求出Pi,Qi,Ri各自的递推公式。
以下略。。。