问题

已知，，求

这是小朋友问我的一个题目，第一感觉就是用求根公式解方程组，分别求出和的解，然后代入，然后解决完毕，呵呵！

解法一：粗暴解法

先给出一个定理: 设一元二次方程的两个根和，
由求根公式可以得到

根据条件可以得到和是一元二次方程的两个根。由一元二次方程的求根公式可知
然后

问题如果用计算器计算无理数，可能会丢失精度，更何况没有计算器，对于这种无理数的高次幂运算需要用到二项式定理，太费CPU了，这不是正解。

解法二：迭代法

先求解根的低次幂和




然后惊奇地发现,这不是斐波那契额数列Fibonacci sequence的特性吗？

于是就直接得出

所以，解决完毕，但是这毕竟是猜想，结果虽然是正确的，但是不严谨！而且如果题目的条件变化了，是不是都满足Fibonacci sequence的特性呢？由此引出了这样的问题：如果我们知道了两个未知数的和以及乘积，是否可以知道所有根的任意次幂的和呢？是不是可以更加泛化一下呢？

泛化问题

已知，，
求

解：

令，则

于是得到了以下的递推公式:

那么对于原始问题已知
可以得到
由此验证了解法二的严谨性。

延拓新的问题

如果没有实数解，以上方法是否适用?

看一个例子,对于泛化的公式,如果，
即
显然
那么
按照递推公式









貌似也ok，待证明

总结一下泛化问题

对于已知，，
求

就会有

最后用python代码实现一下

# 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)

运行结果

>>> 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))
# 等了好久都没算出来
# 容易理解的算法性能差，性能好的算法不容易理解，这就是生活！！！！

经典优化方案，空间换时间:

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
# 计算结果秒出了