假设我有一个多项式f(x(，其中所有系数a(I(都是函数f形式的整数，实现一个函数find_polynomial，它取f并返回系数a(I(作为形式的列表：
[a(0(，a[1]。。。。a[n]](n<=15(
其中a[n]是f(x(的最后一个非零系数。关于f(x(的唯一其他信息是它具有有限度(<＝15(。并且该解决方案不应导入任何模块。
我的方法是尝试使用拉格朗日多项式，这是一种更具数学意义的求解方法，但它对大于10**10的系数不起作用，所以我想知道一个更稳定的解，可以求解所有未知系数。希望看到社会对解决难题的热情。欢迎任何帮助：(
未知函数：
def f(x):
return 5 * x**3
def g(x):
return 6 * x**6 - 2 * x**5 + 3*x + 5 * x**3
def h(x):
return 5 + 3 * x**2 - 2 * x**11 + x + 3 * x**15
def z(x):
return 5 + 3 * x**2 - 2 * x**11 + x + 3 * x**15-2*x**8
def p(x):
return 5 + 3 * x**2 -31 * x**10 + x + 3 * x**15+13*x**8+14*x**9
def wrong(x):
return 5 + 3 * x**2 -1 * x**10 + x + 10000000000 * x**15+13*x**8+14*x**9
测试用例：
print(find_polynomial(f))
print(find_polynomial(g))
print(find_polynomial(h))
print(find_polynomial(z))
print(find_polynomial(p))
print(find_polynomial(wrong))
结果：
(0, 0, 0, 5)
(0, 3, 0, 5, 0, -2, 6)
(5, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 3)
(5, 1, 3, 0, 0, 0, 0, 0, -2, 0, 0, -2, 0, 0, 0, 3)
(5, 1, 3, 0, 0, 0, 0, 0, 13, 14, -31, 0, 0, 0, 0, 3)
'''This ouput is wrong''' (5, 348713164801, -1133862589437, 1568627191296, -1243957041600, 638886422720, -226653467040, 57637291712, -10725815087, 1473646474, -149249101, 10998988, -573300, 20020, -420, 10000000004)
我的方法：
def fact(num):
if num==0:
return 1
else:
return num*fact(num-1)
def poly(x):
result=[]
for i in range(x+1):
y=fact(i)*fact(x-i)*((-1)**(x-i))
result.append(y)
return result
def find_polynomial(func):
result=[0]*16
def helper(len1,func,result):
if len1==0 or func(1)==0:
result[15-len1]=func(0)
return result
else:
sum1=0
polyx=poly(len1)
for i in range(len1+1):
j=(func(i)/polyx[i])
sum1+=j
result[15-len1]=int(round(sum1))
return helper(len1-1,lambda x:func(x)-result[15-len1]*(x**len1),result)
lst1=helper(15,func,result)
def finalize(lst):
if lst[0]!=0:
return tuple(reversed(lst))
else:
return finalize(lst[1:])
return finalize(lst1)
我使用了《C中的数值公式》一书第3.5章中的POLCOE算法，将其翻译成Python，然后将其修改为纯整数算法，以避免舍入问题。
def f(x):
return 1 - 2 * x + 3 * x**2 - 4 * x**3
def g(x):
return 6 * x**6 - 2 * x**5 + 3*x + 5 * x**3
def h(x):
return 5 + 3 * x**2 - 2 * x**11 + x + 3 * x**15
def z(x):
return 5 + 3 * x**2 - 2 * x**11 + x + 3 * x**15-2*x**8
def p(x):
return 5 + 3 * x**2 -31 * x**10 + x + 3 * x**15+13*x**8+14*x**9
def wrong(x):
return 5 - 3 * x**2 -1 * x**10 + x + 10000000000 * x**15+13*x**8+14*x**9
def gcd(a,b):
while b > 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
def find_polynomial(func):
n = 15
m = (n + 1) // 2
result = [0]*(n+1)
s = [0]*(n+1)
phi = [0]*(n+1)
s[n] = m
for i in range(1, n + 1):
for j in range(n-i, n):
s[j] -= (i - m) * s[j+1]
s[n] -= (i - m)
lc = 1
for j in range(n+1):
phi[j] = n + 1
for k in range(n, 0, -1):
phi[j] = k * s[k]+(j-m)*phi[j]
lc = lcm(lc, phi[j])
for j in range(n+1):
ff = func(j-m)
mul = lc // phi[j]
b = 1
for k in range(n, -1, -1):
result[k] += b * ff * mul
b = s[k] + (j-m) * b;
for j in range(n+1):
result[j] = result[j] // lc
return result
print(find_polynomial(f))
print(find_polynomial(g))
print(find_polynomial(h))
print(find_polynomial(z))
print(find_polynomial(p))
print(find_polynomial(wrong))
结果(注意，我在调试期间更改了您的一些多项式(
[1, -2, 3, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 3, 0, 5, 0, -2, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[5, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 3]
[5, 1, 3, 0, 0, 0, 0, 0, -2, 0, 0, -2, 0, 0, 0, 3]
[5, 1, 3, 0, 0, 0, 0, 0, 13, 14, -31, 0, 0, 0, 0, 3]
[5, 1, -3, 0, 0, 0, 0, 0, 13, 14, -1, 0, 0, 0, 0, 10000000000]
大功率：
def wronga(x):
return 5 - 3 * x ** 2 -77777 * x ** 100 + x + 333333333 * x ** 15+13*x ** 8+14*x ** 9
dont't forget to set proper max power:
n = 100
result:
[5, 1, -3, 0, 0, 0, 0, 0, 13, 14, 0, 0, 0, 0, 0, 333333333, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, -77777]