假设我有一个多项式 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]
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句