一道算法题的数学分析

时间:2021-11-16 11:17:33

题目:

一个实数序列: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各自的递推公式。

以下略。。。