代码之家 › 专栏 › 技术社区 › Marcus.Aurelianus

从未知多项式函数求系数的最优解

polynomials polynomial-math algorithm python-3.x python

-3

Marcus.Aurelianus · 技术社区 · 7 年前

假设我有一个多项式f(x),其中所有系数a(i)都是函数f形式的整数,实现一个函数find_多项式,它取f并返回系数a(i)作为该形式的列表:

[A(0),A[1]…A[N]](N<=15)

其中a[n]是f(x)的最后一个非零系数。关于f(x)的唯一其他信息是它是有限度的(<=15)。解决方案不得导入任何模块。

我的方法是尝试使用 Lagrange polynomial 这是一种更为数学化的求解方法,但是 对于大于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)

1 回复 | 直到 7 年前

MBo 7 年前

chapter 3.5

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]