某初中數(shù)學題的解法

問題

已知 $x_1+x_2=1$ ， $x_1x_2=-1$ 饥追，求 $x_1^7+x_2^7=?$

這是小朋友問我的一個題目图仓，第一感覺就是用求根公式解方程組，分別求出 $x_1$ 和 $x_2$ 的解但绕，然后代入 $x_1^7+x_2^7$ 救崔，然后解決完畢，呵呵捏顺！

解法一：粗暴解法

先給出一個定理: 設(shè)一元二次方程 $ax^2+bx+c=0(a,b,c\in R, a \ne 0)$ 的兩個根 $x_1$ 和 $x_2$ 帚豪，
由求根公式可以得到
$x_{1,2}=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$

根據(jù)條件可以得到 $x_1$ 和 $x_2$ 是一元二次方程 $x^2-x-1=0$ 的兩個根。由一元二次方程的求根公式可知 $x_{1,2}=\frac{1 \pm \sqrt5}{2}$
然后
$x_1^7+x_2^7=(\frac{1+\sqrt5}{2})^7+(\frac{1-\sqrt5}{2})^7 = 29$

問題如果用計算器計算無理數(shù)草丧，可能會丟失精度狸臣，更何況沒有計算器，對于這種無理數(shù)的高次冪運算需要用到二項式定理昌执，太費CPU了烛亦，這不是正解诈泼。

解法二：迭代法

先求解根的低次冪和
$s_1=x_1+x_2=1$
$s_2=x_1^2+x_2^2=(x_1+x_2)^2-2x_1x_2=3$
$s_3=x_1^3+x_2^3=(x_1+x_2)^3-3x_1x_2(x_1+x_2)=4$
$s_4=x_1^4+x_2^4=(x_1^2+x_2^2)^2-2(x_1^2x_2^2)^2=7$
然后驚奇地發(fā)現(xiàn) $s_2=s_1+0,s3=s1+s2,s4=s3+s2$ ,這不是斐波那契額數(shù)列Fibonacci sequence的特性嗎？

于是就直接得出
$s_5=s_4+s_3=11$
$s_6=s_5+s_4=18$
$s_7=s_6+s_5=29$

所以 $x_1^7+x_2^7=29$ 煤禽，解決完畢铐达，但是這畢竟是猜想，結(jié)果雖然是正確的檬果，但是不嚴謹瓮孙！而且如果題目的條件變化了，是不是都滿足Fibonacci sequence的特性呢选脊？由此引出了這樣的問題：如果我們知道了兩個未知數(shù)的和以及乘積杭抠，是否可以知道所有根的任意次冪的和呢？是不是可以更加泛化一下呢恳啥？

泛化問題

已知 $x_1+x_2=a$ 偏灿， $x_1x_2=b$ ，
求 $x_1^n+x_2^n=? 其中a,b都是常數(shù)钝的，n \in N$

解：

令 $s_n=x_1^n+x_2^n$ 翁垂，則

$s_n=x_1^{n-1}x_1+x_2^{n-1}x_2$
$s_n=x_1^{n-1}(a-x_2)+x_2^{n-1}(a-x_1)$
$s_n=ax_1^{n-1}-x_1^{n-1}x_2+ax_2^{n-1}-x_1x_2^{n-1}$
$s_n=a(x_1^{n-1}+x_2^{n-1})-x_1x_2(x_1^{n-2}+x_2^{n-2})$
$s_n=a(x_1^{n-1}+x_2^{n-1})-b(x_1^{n-2}+x_2^{n-2})$
于是得到了以下的遞推公式:
$s_n=as_{n-1}-bs_{n-2}$

那么對于原始問題已知 $a=1,b=-1$
可以得到 $s_n=s_{n-1}+s_{n-2}$
由此驗證了解法二的嚴謹性。

延拓新的問題

如果 $x_1,x_2$ 沒有實數(shù)解硝桩，以上方法是否適用?

看一個例子,對于泛化的公式,如果 $a=b=2$ 沿猜，
即 $s_1=x_1+x_2=2, x_1x_2=2$
顯然 $x_{1,2}=1 \pm i$
那么 $s_2=x_1^2+x_2^2=(1+i)^2+(1-i)^2=0$
按照遞推公式
$s_3=2s_2-2s_1=-4$
$s_4=2s_3-2s_2=-8$
$s_5=2s_4-2s_3=-8$
$s_6=2s_5-2s_4=0$
$s_7=2s_6-2s_5=16$
$s_8=2s_7-2s_6=32$
$s_9=2s_8-2s_7=32$
$s_{10}=2s_9-2s_8=0$
$s_{11}=2s_{10}-2s_9=-64$
貌似也ok，待證明

總結(jié)一下泛化問題

對于已知 $x_1+x_2=a$ 碗脊， $x_1x_2=b$ 邢疙，
求 $s_n =x_1^n+x_2^n=? 其中a,b都是常數(shù)，n \in N$

就會有 $s_n=as_{n-1}-bs_{n-2}, 其中s_0=2,s_1=a$

最后用python代碼實現(xiàn)一下

# a是和, b是積, n是冪
def solution(a,b,n):
    if(n == 0):
        return 2
    if(n == 1):
        return a
    return a*solution(a,b,n-1)- b*solution(a,b,n-2)

運行結(jié)果

>>> print(solution(1,-1,0))
2
>>> print(solution(1,-1,1))
1
>>> print(solution(1,-1,2))
3
>>> print(solution(1,-1,3))
4
>>> print(solution(1,-1,4))
7
>>> print(solution(1,-1,5))
11
>>> print(solution(1,-1,6))
18
>>> print(solution(1,-1,7))
29

然后

>>> print(solution(1,-1,100))
# 等了好久都沒算出來
# 容易理解的算法性能差望薄，性能好的算法不容易理解疟游，這就是生活！：壑А０渑啊！

經(jīng)典優(yōu)化方案卧须，空間換時間:

def solution(a,b,n):
    sn,s0,s1 = 0, 2, a
    for i in range(1, n):
        sn = a*s1 - b*s0
        s0 = s1
        s1 = sn
    return sn

測試100

>>> print(solution(1,-1,100))
792070839848372253127
# 計算結(jié)果秒出了

最后編輯于：2019.03.10 23:08:20

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者